Amazon Interview Question: Design an algorithm to take a... | Glassdoor

Interview Question

Software Development Engineer Intern Interview Seattle, WA

Design an algorithm to take a list of strings as well as a

single input string, and return the indices of the list which are anagrams of the input string, disregarding special characters. Given a binary tree which is a sum tree, write an algorithm to determine whether the tree is a valid sum tree or not. Then, write an algorithm that will fix the tree to make it a sum tree. Then, write an algorithm which will fix a tree to make it a sum tree by only using addition.

1

Question 1:

//
// NOTE: Since sort will clobber a value, inputs to this functioned
// were passed by value, so as not to affect caller's version. If
// that is not okay, it is easy enough to use temporaries as inputs
// to sort (sort is defined in std library ).
//
list getAnagramIndexes(list strList, string str)
{
list myIndexes;

sort(str.begin(),str.end());

int currIndex = 0;
for(list::iterator i = strList.begin(); i != strList.end(); ++i)
{
sort(i->begin(),i->end());
if(*i == str)
{
myIndexes.push_back(currIndex);
}
currIndex++;
}

return myIndexes;
}

JB on Oct 3, 2013