Amazon SDE in-person interview
Foreword:
If you want the answers to the interview questions, you are most welcome to post comments and I will answer them.
I signed my first NDA so I can’t tell you about a lot of interesting things I learnt there. But everything else that I remember will be here =)
Early Morning
I went to Montreal today for the final round of SDE interviews. I had to wake up early, very early, around 5:30am to catch the plane at 7:30am. Deep in REM sleep when I woke up, I was dreaming I was… wait that’s not what I’m talking about here =)So, I took the plane, took a cab and then I got to the interview place. Man, that hotel is nice! I met with the PM (program manager) and she said I was to meet my first interviewer shortly. As expected, a few minutes later, there he came and introduced himself.
We went to a room, sat down and the interview started.
Interview 1
He introduced himself, talked about what he does, looked at my resume and asked me about my educational background, what I learnt in university etc. He asked what was the project I was most proud of, and he asked about something on my resume.
Then, he took a notepad and whipped up this diagram:
His question was: What is the radius of the circle? The answer is…. drumroll bobobobom bom bom… Beta *tshh*
Heh I looked at the diagram, mumbled something about cos under my breath, then i’m like… hey wait a minute! heh… He said that once, some person took as long as 10 minutes to find the radius. I guess that was just to check if the interviewee was utterly confused or something.
Next question: Given 3 sets containing positive integers as such:
S1= { 1, 7, 13, 27 }
S2= { 1, 7, 13, 21, 31 }
S3= { 7, 13, 21 }
Write pseudo-code that will return a list of all integers that are not found in all 3 sets. Running time?
That was a pretty cool question, very nice algorithm and it turns out it was one of the problems he needed to solve once, but in a real world context. I fumbled a lot, but with the proper guidance I was able to come up with a solution.
Next: Imagine you have a distributed system where requests go through a load balancer which is effectively a switch. Machines are connected to the load balancer and requests are passed on to them with some strategy. Devise a way such that each machine(hosts) would know about all the other host names, even when new machines are connected to the load balancer.
That was it for the interview. I left the room, went to the lounge and waited for my next interview. I had a chat with a few blokes there: Jason, Steven and Clive. They were all 1) older than me 2) more educated than me (they all had Masters at least) 3) more experienced that me(they all work… at IBM or some other bullcrap like that). But somehow, I think I was the ‘happiest’ person there. =) heh ignorance is bliss.
Interview 2
The interviewer introduced himself, looked at my resume and asked me about what I learnt in university. After the resume stuff, he briefly talked about himself, but on a personal level because he was not from the recruiting group (more on that later), but he was just helping out.
His question: Design an object-oriented program complete with classes, attributes and functions/methods, in the language of your choice implementing a directed, acyclic graph. Make sure to include all methods you think will be needed and implement the functions that will be critical in ensuring that the graph is acyclic and remains acyclic.
I started drawing the classes in a diagram looking a lot like UML, complete with attributes, etc. Of course the signatures and types changed along the way I was writing the program. This one was long… I was writing function after function…
The most critical method for ensuring the acyclic property is addEdge(Vertex o, Vertex d). I was writing this function down, but we were running out of time. Coding on paper is HARD. Especially when you’re as messy as I am. I sorta finished writing the classes and he came up with a special case and asked me if my code handled it. It didn’t I say, so he asked how I would solve it (no code correcting since there was no time left). I said something which doesn’t make much sense… under the pressure… and which was stupid. But hey, I realized my mistake, and the correct solution as soon as I walked out of the door; at least I learnt.
Interview 3
You’ve guessed it, it always starts like this: introduction, question about education, question about stuff on resume. This guy asked me the toughest question of them all. In retrospect it was not hard per se, but… I guess it was hard for me to come up with the solution. With a *lot* of nudging and hinting I did solve the problem.
Say you have an array of 1,000,000 elements. Each index of the array contains an integer ranging from 1 to 10,000,000.
The integers are in a random order. Produce an algorithm that will sort the array in O(n) running time.
Please ask me about it, I’d like to write down the solution =).
Now assume that instead of an array, you have a file that contains 1,000,000 lines of integers, arranged in a random order, ranging from 1 to 10,000,000. Assume this time that you only have 1,000,000 bits of memory. Find a solution that would output a file with the integers sorted. You still want the solution in O(n) running time.
Interview 4
The final interview was with the Program Manager and it wasn’t a technical one. What we talked about was: salary, relocation, seattle weather, work authorization status and whatnot. She also explained how the hiring decision is made: they meet up later on that day and discuss each candidate. She told me I’d get the hiring decision on Thursday.
Conclusion
Here are some lessons I learnt:
- Their interviews are challenging. (at least to me!)
- Sleeping the night before an interview is important. (playing Tetris WiFi definitely not recommended)
- They tackle really interesting theoretical problems in real life applications (Interview 2 & 3 anyone?)
- The main over-arching theme in all of Amazon’s technical challenges is scale.
- Their employees are passionate about what they do.
- They love UNIX.
- They make the interview process as painless as possible and come up VERY FAST with a decision.
- After I told interviewer 2 that the algorithm was very neat and that i wouldn’t have been able to come up with it within the minutes we had without his help he said: well, at least you got wiser!
- You learn a lot in interviews.
- I missed DemoCamp 6.0
To conclude, I’d say I got owned, nubbed, schooled and whatnot. I hit the rails a lot but eventually came up with the solutions with some hints. I should’ve slept properly the night before and we’ll see what they thought of my performance =)
Tuesday, May 30th, 2006 @ 9:15 pm 
interviews
RSS 2.0
Trackback
May 31st, 2006 at 12:35 am
Given 3 sets containing positive integers -> The example you gave seem to be sorted. If they are, you can pick an array with the least elements. For each element in this array, perform a binary search on the other two array. If you can’t find this element in both arrays, then it’s unique.
The other solution is pick an array where the range of the smallest and biggest number is smallest. Make a bit vector where the size is (largest_element – smallest_element.) For each element in the array, go through and subtract from smallest_element and use the result as an index. Well, the rest is pretty easy.
Better solutions?
Direct Acyclic Graph – To determine if a graph has a cycle, you just perform a modified version of DFS. Topological sort would work to.
Sort an array of 1,000,000 elements in linear time -> create an array of 10,000,000 and does a counting sort. If the elements are unique, then create a bit vector instead.
How would you do the 1,000,000 lines of integers problem?
May 31st, 2006 at 12:47 am
I misunderstood the 3 sets question. I thought the number that is unque from the three array. You can always use a hash table for the array with the smallest element. Or just a bit vector.
May 31st, 2006 at 1:50 am
lol. I dont remember any fo the stuff i did in uni.. well to me it becomes irrelevant afterwards once u got the experience and practical skills.
uni teaches u how to learn
May 31st, 2006 at 5:23 am
These interviews were really hard. The funny thing is, in real life you rarely ever use all this knowledge they quizzed you about. But then, was this vacancy for a systems developer job or an information systems developer job? I’m more of the latter category and would not have been able to answer the graph theory question. But, do I know my Java
I wonder whether the interview was so tough just because you are a fresh graduate and they want to make sure you actually learned something in university (in contrast with someone who has been practising for years). For my last job, I just had to point them to my web log (http://coding.mu) and they were sold.
May 31st, 2006 at 6:58 am
Yeah for the Set question, I did come up with the hash table solution.
Well, sort of a hash table (cause you don’t need to store the integers in a bucket, you just need to keep track of how many you’ve seen). He then asked me to come up with 2 problems with the hash table.
Well, I came up with 3:
The main problem is scale. The point was to come up with a solution that was do-able on a machine with limited memory, and the # of sets as well as integers might neighbour the millions.
A better solution is this:
Use n pointers, one in each set, starting from the leftmost integer.
Worst case running time? It is when all the integers are unique. All comparison require O(n) time, for going through the list. At worst case, you will need to go through the list everytime you move to a new int.
so that comes up to (|S1|+|S2|+|S3|) * n.
That’s still O(n).
May 31st, 2006 at 7:06 am
As for the acyclic graph, it is indeed a DFS that is de-rigueur.
A special case I needed to support was the above. It is not a cycle and it is definitely within what should be allowed.
What I did in the interview is a detectCycle method that would traverse the nodes in DFS. The traverse function would throw an exception if it goes through a node twice which I catch in the detectCycle method, in which case detectCycle would return true. (that solution doesn’t allow for the special case).
A method, which sprang to my mind right when the interview was done, is to traverse the graph, with origin say o, and trying to get to itself. If it succeeded, there would be a cycle. Although a more efficient solution could be found, at that point I just wanted something that worked. The solution above that could’ve worked with a tweak of the cycle detection mechanism, but that would’ve required more thought.
May 31st, 2006 at 7:26 am
For the integer sorting question here are the solutions:
After a few minutes of trying to come up with solutions (i first thought about a hashtable, then I realized the hashing function I would need would be just the int itself)
Create a bit array of size 10,000,000.
Everytime you get an int, you mark the corresponding index with a bit. (if there are duplicates, have a counter associated with each index).
An output of integers would require a pass through the helper array, printing out marked index as you go.
The twist of the question with files and restricted memory is rather neat.
If you only have 1,000,000 bits of memory available, you need to use that to represent 10,000,000 integers.
A way to do this is as follows:
This gives the correct solution, but requires multiple passes through the initial file. The conclusion is this: when there’s limited space, a running time tradeoff is necessary. This is a good tradeoff as it is only a constant factor more than the non-space sensitive one. Running time: O(n)
May 31st, 2006 at 7:16 pm
For integers in a file question, you are assuming that the integers are unique. If they aren’t, how would you handle collision?
May 31st, 2006 at 10:43 pm
Yeah, if the integers are not unique, you can associate a counter to each bucket. Not very space efficient, but it works, still in O(n) time.
June 3rd, 2006 at 12:25 pm
Hehe… so did you get back the results of the interview?
June 3rd, 2006 at 9:07 pm
yep i did!
unfortunately I didn’t get the job =(
I don’t feel so bad though, it appears i didn’t have enough experience.
I have some good news though, I have an offer for here in TO and possibly more coming =)
July 23rd, 2006 at 5:17 am
Dude, Going through your interview questions in my leisure was fantastic!
I’ve got a phone interview with Amazon soon, I had no idea what to expect and I’ve garbage collected (in my brain) all that good stuff that they seem to be asking.
Thanks a ton for putting up this experience, really refreshed my mind about solving these trickly little algorithms. I’m sure these dudes don’t ask the same thing twice, but good to know the style of questions sure gives me a heads up.
For the circle question, isn’t both alpha and beta the radius, if the centre point is where it’s supposed to be? unless beta is the angle, in which case that leaves only alpha.
Supposing the center point is shifted a bit elsewhere, neither alpha nor beta would be radius.
How much time did you have for each of those questions by the way?
Crossing the fingers for my own little phone interview.
-Mark
P.S. You are a good man for putting this online!
July 23rd, 2006 at 1:16 pm
hello mark, thanks for the comments =)
Alpha is the distance from the centre point to the first intersection of the perpendicular line. So Beta is the radius, going all the way to the circle from the centre point.
They don’t time for a question and they usually try to find if you have some sense of things. You shouldn’t worry about it too much!
And don’t get stuck thinking silently… always voice out what you’re thinking about.
One interview takes a bit less than an hour, being 30 to 45 mins depending on what you talk about.
Good luck!
let me know how it goes!
Olivier
July 27th, 2006 at 4:06 am
Well i had a phone interview today and they asked me similar questions which dealt with using hash tables and o notation stuff… among other few questions. i felt that i did about 50-60% ok, didn’t know a lot of things. then the HR person calls me about an hour later and schedules a 2nd phone interview. is it amazon’s policy to have a mandatory 2nd phone interview or do you think the first guy gave me the goahead for a 2nd one? he even implied i did not have enough experience for what his team was looking for.
July 27th, 2006 at 3:40 pm
I think it isn’t mandatory to have a 2nd phone interview. Those interviews are screeners, to sift through people to find people interesting to them. So you must’ve been of some interest =). I wouldn’t worry too much about the comment. Let me know how it goes and best of luck!
August 7th, 2006 at 6:16 pm
I had my 2nd phone interview over a week ago and no response whatsoever
they asked me some questions on design patterns and a data structure problem that had to deal with counting the number of times a word occurs in a file… he also asked me about a lot of terminology i don’t remember from college.
oh wells time to move on
August 7th, 2006 at 7:49 pm
i wish you good luck in your endeavours =)
August 6th, 2008 at 8:54 am
Can you share the answer of Interview 3? You can send it to my email @ davylw@gmail.com.
I appreciate it.
August 11th, 2008 at 3:57 pm
Assuming there are no duplicates, a tradeoff between space and running time can be made:
Make an array that can contains enough space for the difference between the largest and the smallest integer.
For 1 million integers, that makes it a minimum of 1 million bits.
We only need to store a bit of information, just 0 or 1.
Iterate through the list of integers, store a ’1′ bit to the corresponding index in the array.
When done, iterate through the array, and for each index, if the resulting bit is not 0, output the index.
Voilà!
If duplicates are in the mix, just store more than a bit…