You are given an array, and a number x. Determines whether or not there exist two elements in in the input array whose sum is exactly x, efficiently.

Question

You are given an array, and a number x.  Determines whether or not there exist two elements in in the input array whose sum is exactly x, efficiently.

Anónimo · Accepted Answer

If the array is initially unsorted:

-O(NlogN) runtime, no additional memory: Sort the array. For each element i, perform a binary search on the array for X-i.

-O(N) runtime, O(N) additional memory: Stick all of the elements in a HashSet. For each element i, check whether X-i is present in the set.

If the array is initially sorted:

Create two pointers, one originally to the first entry in the array and the other to the last. At each step, check how the sum of the two entries currently being considered compares to X. If it's too small, increment the first pointer. If it's too big, decrement the second. If it's equal, we are done.

This process will locate a pair summing to X, if such a pair exists. Otherwise, we will know that no such pair exists as soon as the pointers coincide.

Anónimo · Answer

Iterate through the array, and mod each element with x. Ex: If x = 6, and the array is [3, 7, 19, 12, 29], we would get [3, 1, 1, 0, 5]. For each of these, set the hash of it to 1. Ex: For our example, we now have the following hash table: 
H(0) = 1, 
H(1) = 1, 
H(2) = 0, 
H(3) = 1, 
H(4) = 0, 
H(5) = 1. 

This took linear time. Now, check H(0) == 1. If this is true, we are done. If not, iterate i: 1 to array.length/2,  and check if H(i) == 1 && H(array.length - i) == 1. If this is true for any i, then we are done and we return true. Otherwise, we return false.

Anonymous 2 · Answer

Oops, little error there:

change either the check or the insert  operation to work on X instead of X-CUR.

Anonymous 2 · Answer

Create a Set called S

For each element CUR in the array check to see if S.contains(X-CUR) if yes then return true else insert (X-CUR) into S.  After the loop quits return FALSE

Tower Research Capital

Pregunta de entrevista de Tower Research Capital

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo