Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Previous answer is O(n^2). This one is O(n*logn), assuming that find a number in a set takes logN.
void findPair(list<int> aList, int sum)
{
set<int> aSet;
for each (auto item in aList)
{
if (aSet.find(sum - item) != aSet.end())
{
cout << item << " " << (sum - item) << endl;
}
aSet.insert(item);
}
}
How about converting the array to a BST and then for a node(say root node) in the bst search for some other node(say target node) whose value when added with the reference node will give the desired sum. Now delete the reference node and target node . Continue this process untill last 2 nodes are present. Every search will happen in O(log m) where m is number of elements in BST. With each iteration value of m will decrease by a factor of 2 as we will delete the reference node. If space is not a constraint then we can improve the results further by using DP.
As mentioned by Ayush, if there are no space constraints, a "map/hashtable" can do the job in O(n) where "n" is the length of the list (in fact the number of distinct numbers on the list). I added a simple java function for that.
Example:
Output:
- Ehsan January 14, 2014