4.3 of 5 148 reviews San Francisco, CA 1000 to 5000 Employees

Twitter Software Engineer Intern Interview Question

I interviewed in Palo Alto, CA and was asked:
"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."
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Intern Interview Review - one of 203 Twitter Interview Reviews

Answers & Comments

of 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 Flag Response

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Twitter interview questions and advice. All interview reviews posted anonymously by Twitter employees and interview candidates.