Amazon.com

  www.amazon.com
  www.amazon.com

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.
Answer

Interview Answer

1 Answer

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 <algorithm>).
//
list<int> getAnagramIndexes(list<string> strList, string str)
{
 list<int> myIndexes;

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

 int currIndex = 0;
 for(list<string>::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

Add Answers or Comments

To comment on this, Sign In or Sign Up.