Interview Question

Software Engineer Intern Interview Palo Alto, CA

given an array of numbers and a number k, find if two

  numbers in the array add up to k. Running time, space complexity, standard questions.
Answer

Interview Answer

1 Answer

0

Naive solution:
for i in range(len(array)):
   for j in range[i+1, len(array)]:
       if array[i] + a[j] == k: return true

but this is O(N^2)

we can do better if we hash the elements of the array so we can check in constant time if they are present.
map = { }
for i in array:
   map[i] = true;

for i in array:
   if map[k - i] then return true

this algorithm is O(N)

anon on Dec 16, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.