Amazon Interview Question: Find two integers in an unsor... | Glassdoor

Interview Question

Software Engineering Intern Interview

Find two integers in an unsorted array that produced a

  certain sum in linear time.
Answer

Interview Answer

2 Answers

2

This can be solved with a hash set. Loop through the array. At each index check if the number at the index exists in the hash set. If it does, return the number and the difference between it and the given sum. Otherwise, store the difference between it and the given sum in the hash set. In the worst case, time and space complexity is O(n).

Anonymous on Dec 15, 2015
0

Have two variables for the two different numbers. Initialize them to the first and second element of the array. Traverse the array starting from the third element and check each number. If the sum of the current number and the first saved number is the target, set the second saved number to the current number. If the sum of the current number and the second saved number is the target, set the first saved number to the current number. If the sum of the first and second saved number is the target, break out of the loop.

Anonymous on Jan 20, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.