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.

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