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.
23 Responses to 'The Amazon.com Interview'
Leave a Reply
Fresh, related resources:
- Oconomowoc’s Most Famous Former Drag Queen?
That being said, we’re willing to accept that a persona such as Aqualicious can exist only in a fictionalized sense on the internet, and to that end, we point you to Susan Henderson’s LitPark.com where you can read a fantasic interview ... - Third live radio interview to air this summer In the Spirit host ...
Third live radio interview to air this summer In the Spirit host Gary Goldberg has invited Tom back to continue their conversation on the spiritual vision of Henry Corbin - the new date and time will appear in this space. ... - I'm also attracted to things that are very dark
Here is a new interview with Jon that was posted on YouTube!: "I'm continually wrestling with the idea that there are certain things in this world that simply don't fit. The idea that I have this longing for beauty and truth, ... - Times are a'changing
I had my last interview with a huge Swedish clothing company this Wednesday and apparently it went so well they offered me a position right then and there and we signed all documents. I start May 26th. ... - IMAGINE THIS – LOOSING THE USE OF YR LEFT BRAIN – DRJ B TAYLOR DID ...
My stroke of insight would be: Peace is only a thought away and all we have to do to access it is silence the voice of our dominating left mind…” You can listen to the interview on BBC Radio’s Website – Outlook program Look for: ...
on February 16th, 2006 at 4:09 am
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
on February 16th, 2006 at 4:17 am
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…
on March 16th, 2006 at 7:30 pm
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
on April 28th, 2006 at 10:26 am
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.
on April 28th, 2006 at 2:46 pm
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)
on April 29th, 2006 at 12:00 pm
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.
on June 9th, 2006 at 8:43 am
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.
on November 8th, 2006 at 10:44 pm
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
on November 13th, 2006 at 11:17 pm
^^^ Hey shital how was your interview ?
on November 14th, 2006 at 3:41 am
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?
on November 28th, 2006 at 2:26 am
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
on November 28th, 2006 at 2:36 am
contd…
on November 28th, 2006 at 2:37 am
I don;t get this. Why my messages seem to be incomplete!
on January 8th, 2007 at 8:12 am
This is due to html tags that is used in the blog…..we need to escape to get that displayed it….
on May 5th, 2007 at 7:46 pm
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
on October 3rd, 2007 at 7:38 pm
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
on October 8th, 2007 at 1:41 am
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
on October 10th, 2007 at 3:39 am
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
on October 16th, 2007 at 11:02 pm
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.
on October 24th, 2007 at 3:21 am
Hi,
I have cleared the first interview.
I have the second one this week.
Can anyone help me out with some more sample problems.
on November 3rd, 2007 at 1:45 pm
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
on January 4th, 2008 at 5:26 am
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
on April 25th, 2008 at 6:31 pm
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.