The Amazon.com Interview
It’s been almost a year since I had my interview for a summer internship at Amazon.com, but the memory is still fresh in my mind. I went in fairly tense, excepting a Microsoft-attack-style of interviewing, but I was pleasantly surprised to be greeted by a nonchalant employee with his feet up the table chewing on a pen. Over the rim of his framed glasses, he introduced himself and asked me to have a seat, which I did.
Little did I know that the first guy was actually one of a bar-raiser. Since the term is public knowledge, it can’t hurt to say that a bar-raiser is an Amazon interviewer dedicated to hiring only the best of the best candidates. A bar-raiser’s job is to go for those candidates that are somehow more special than even a “good” one.
We engaged in a little chit chat about my resume and life at Cornell before launching into the interesting part of the interview, which was the coding question. It was a basic one involving a special case of the subset sum problem (which is NP complete in the general case). It went like this:
Given an array of integers or other numbers (reals, doubles, etc), tell us if any two of the numbers in the array sum up to another given number.
There’s an n2 solution in which you compute all the possible pairs of numbers and then add them together to test the termination condition. Obviously, this is less than ideal. However, it is well known that integers can be sorted in O(n) time, where n is the number of integers to sort. Therefore, I proposed this additional precondition:
Allow the list of integers to be sorted in natural order before calling this method
The algorithm then is quite simple: keep an index at the far left side, and the far right side. If the indices become equal, or cross, we’ve failed to find a pair that works. To try to exhaustively find a matching pair, we try adding the numbers at our indices. If the sum too big, we decrement the right index. If the sum is too small, we increment the left index. If the sum is equal to what we’re looking for, we can return true. Pseudocode resembling Java might look like this:
public boolean inArr(int [] arr, int sought) {
int left = 0;
int right = arr.length - 1;
while(left < right) {
int test = arr[left] + arr[right] - sought;
if(test > 0) {
right--;
} else if(test < 0) {
left++;
} else {
return true;
}
}
return false;
}
Other questions would all be basic algorithms and OOP ones that simply want to establish that you can write decent code, think on your feet, and love what you're doing.
| This entry was posted on Saturday, December 31st, 2005 at 11:11 pm and is tagged with subset sum problem, summer internship, termination condition, chit chat, fresh in my mind, amazon, decrement, integers, public knowledge, precondition, interviewer, increment, interviewing, cornell, algorithm, rim, pairs, array, np, glasses. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback. |
Instead of using hash table, you can use a bit map which saves a lot of memory. You can use bit map instead of hash table because the number of occurrence is only important if it is zero or at least one.
One thing to mention is that we might need to check if there is two number value of $target/2 existing in the array. However, it can be done during the bit map construction.
This takes O(n) to finished but takes much less memory
what about negative numbers??? the code will fail if sum of two numbers add up to Zero
arr[] ={ -22, 19 22} and the sought number is 31
in the first iteration, it will fail because sum of -22 and +22 is zero and the function returns true
??
public static void main(String[] args) {
int sum = 18;
int[] arr = {2, 10, 7, 6, 9, 5, 1, 4, 9, 6, 5, 7, 8};
Set set1 = new HashSet();
for (int i: arr) {
set1.add(i);
}
boolean found = false;
Iterator itr = set1.iterator();
while (itr.hasNext()) {
int temp = itr.next();
int findThis = sum – temp;
if ((temp != findThis) && set1.contains(new Integer(findThis))) {
System.out.println(temp +”+”+ findThis+”=”+sum);
found = true;
break;
}
}
System.out.println(“Is the sum found: “+found);
}
I was just served this question when I went in for an interview at Amazon not too long ago (funnily enough, it wasn’t for a software dev position, but for a support position.)
Basically, you’re trying to find
1. a[i] + a[j] = c,
for some number c.
I did the O(n^2) solution initially, though they hinted at there being a faster solution, to which I scribbled the following equation:
2. a[i] = c – a[j]
If you set up the hash so that instead of array indices referring directly to the value that they hold, you flip the relation so that the value of a[i] refers to the array index:
3. a[i] => i vs. i => a[i]
Pick j = 0. Do a hash search for a[i] with (2). Increment j by one, then repeat, until you find the answer. If you’ve hit j > last array index, then the answer is obviously not there.
I think I got it in O(n)
For each integer in array
check a hash table if number exists as key
if it does return true
else push its complement (taget_sum – current_int) to hash
loop
return false
You have to be very careful about precision though. This code would likely only work with integers.
this is O(n)
Just my two cents. I believe that this can be done in O(n lg n) time using FFT. Use the values as exponents in your polynomial, square that polynomial using FFT. Then just search if any value in the result has the power of the target number.
Thanks Elliott. Great Code. Here i give the entire java code.
class A { public static void main(String args[]) { int [] inArr = {20,8,35,87,82,32,98,32,31,54,32,123,35,1,2,3,2313,5534,1231,123,53,23}; inArr = sortArray(inArr); for(int i =0 ;i < inArr.length; i++) System.out.println (inArr[i]); System.out.println (inArr(inArr,2333)); } public static int [] sortArray(int [] arr) { int temp; for(int i=0; i<arr.length;i++) for(int j=i; j arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } return arr; } public static boolean inArr(int [] arr, int sought) { int left = 0; int right = arr.length - 1; while(left 0) { right--; } else if(test < 0) { left++; } else { return true; } } return false; } }Great solution of using 2 pointers by Elliot. Its highly intuitive. I had reached the part where you have two pointers, but did not get the part where you increment only either the left or the right pointer …!
Hey Sridhar,
What was the complexity of your solution?
Hi,
I am soon to have my first phone interview with Amazon for a SDE position and I have 4 years of Software Development Experience. Are the questions(telephone and in-person) the same for an experienced developer like me and a fresh out of college grad ?
Thanks
Raj
I was asked the same question.
What i replied was this:
Go to each element store the (key,value) as (number, its hash).
For each element also check if key =(sum-element) is in the hash or not.
Thus it takes only o(n) and one iteration only. And I passed the interview so i suppose i was correct.
a slight variation of the solution which results in lesser addition operations:
1) keep two pointers one at start, one at end.
2) find sum – (number at start pointer), search for this backwards from end ptr. Stop when u reach a number less that what u are searching for or actually find the number.
3) advance start ptr and repeat 2, stop when ptrs are same or cross
Hi Chintan,Roy,
I have a phone interview next week with Amazon.Could you share some of the questions with me. I really appreciate your help in this regard.
Gowrishankar L
Hi,
I have cleared the first interview.
I have the second one this week.
Can anyone help me out with some more sample problems.
You have to sort the list. Also you have to use a external data structure like a hashtable to solve this.
Note: In any case where you want reduce the order on time, you have to look for increasing spatial requirements. Always think about a data structure in case you are unable to solve it without using one.
hii Kiran
I have got a Tele.. Intw with Amazon in coming weekend so it will be really grea8 if u can put some of the questions they asked and also mainly the areas they were focussing…
thanks
Chintan
Hi Kiran,
Hope your phone interview went well. I have a phone interview with amazon for an intern position this month.I would really appreciate if you could briefly explain their interview process,some of their typical questions and the areas they focus on.
Thanks,
Arjun
Hey Sridhar,
Could you please tell me how you solved the problem with the hints given by the interviewer? I have an phone screen interview tomorrow. You inputs will be greately appreciated.
thanks,
-Kiran M
This is the question that they asked me in my last interview (8th interview) with Amazon. However there was a slight modificication. You have to find if any two numbers add to the third number in the same array (instead of an externally provided number). I solved it with hints from the interviewer.
However, I was not selected
This is due to html tags that is used in the blog…..we need to escape to get that displayed it….
I don;t get this. Why my messages seem to be incomplete!
contd…
The algorithm mentioned by the starter of this thread is missing the case if more than one pair of numbers sum up to sought number. As an example, if I given number to seek is 12 and I have following sorted array to work on
{3,4,8,9}, then I should report two pairs (3,9) and (4,8).
Following code achieves it. It is in C.
#include
int main()
{
//Our sorted array
int a[] = { 2,3,4,7,8,9};
int left,right,sum,sought;
int len = sizeof(a)/sizeof(int);
sought = 11;
for(left=0,right=len-1;leftsought)
right–;
else if(sum
I thought amazon had 2 phone screen interviews before you could get a call for an on-site final round. But I have got a 3rd Phone screen interview with Amazon. Is that strange?
^^^ Hey shital how was your interview ?
HI Silly or Tonic,
Could you tell how would you implement hashing? I know the basics as I have used it for Angram and Poker Hand problems.
I am apearing for an interview in Amazon tomorrow 9th November, Thursday, 2006 and I can not get a good understanding of this particular problem.
Thanks
How about this — assume function is called with array, num elems in array, and target sum:
1. If num elems == 0 or 1 return false (can’t find two elems that add up to target).
2. If num elems == 2 return (num elems == target ).
3. Create hash h of elems.
4. For each elem in array:
4.a. If hash.contains( elem ) then return true else hash.insert( target – elem )
5. return false (we have iterated over the entire array and didn’t find a pair).
The above algorithm will work for any order of the numbers in the array, for numbers being positive/negative/etc.. Note that the above algorithm will not give you the actual elements positions (but you may print the elements the moment you find them). If you want to actually return the elements indices, you may modify the hash to a dictionary keyed as the hash and where the value is the element index.
Hi Elliott,
Not binary search, for the orig algo, but an altered version of it. If the first half of the list contains numbers that when added to the last element will never add up to the given number, then why try them? Imagine a list from 1 to 100, and the given number is 199. I might test this given the time this week just to see if it can be done. But maybe it cannot
Determining if zero exists will only add to the constant. When you get rightmost value, before you add it to the leftmost, just see if it is zero. This is just one more step, 2n now instead of 1n. If it is zero you significanly reduce your runtime.
1) Binary search won’t work–imagine you start with some possible “left” value and fail–you’ll to repeat the search. You’d end up with something like (n/2) log n time.
2) This is definitely true!
3) It might improve the constant, but determining if 0 is in the array is already O(n)
A few things:
1) I believe that if you apply an altered binary search you can reduce your time complexity to log n.
2) You could do a quick sanity check. Let n be rightmost position. First check if (array[n] + array[n-1] is less than given number), if true, then bail, similar check at rightmost end. Why search for that which cannot exist?
3) Using your algo, add additional check for if zero does exist, if yes then the algorithm is reduced to a binary search for given num in array, reducing the rest of the search from n to log n.
I don’t get the 4th step from tonic’s reply. What do you mean by if value is more than 1 return key, then aren’t you prematurely breaking the iteration?
Shouldn’t it be if the key is >= 1 then look for a new_key = target -key, and if that also have exist then you return true, and at the end of the loop you would return false?
Thanks,
Rajan
That also uses O(n) space, which may not be desireable. In fact, if you’re operating in a space sensitive environment, you may use the O(n^2) algorithm even though it’s slower! And, n log n is the worst case time for an in-place sort, which really isn’t that bad. I am not sure if integers can be sorted in place in O(n) or not, although they can be sorted with additional memory in that time…
The best solution for this is:
1. Iterate array and insert it into hash table with key as Array element and value as #occurence
2. It takes O(n)
3. Iterate Hash table.
4. For a key x, check if value is more than 1 return key: if value is 1 then look for they key (target – key) in Hash table if exists return key else return false
5. Hence O(n) complexity