The Amazon SDE Phone Interview 2
I had my 2nd phone interview with Amazon today. My interviewer was from the same group as the previous one, albeit with different responsibilities. He started by telling me about what he generally does over there and he also told me about a new feature he worked on that got rolled out recently. He then started the interview:
Reading over my resume, he asked about some of the technologies that I have used in my projects; he asked what my favourite programming languages were and why they are my favourites. We then started talking about AJAX and whatnot. Once the resume stuff was done, he started the technical stuff:
- Imagine you are implementing Java’s garbage collector. How would you implement it and what algorithms would you choose? I explained how I would go around implementing it, with periodical garbage collection etc, but I honestly told him I had no idea on what algorithm to choose. He gave a hint about reference counts. That jumped in my mind and I remembered refcounts from implementing file systems.
- Are there any problems with the refcount strategy? (Answer: Circular references)
- Can you think about another algorithm that would solve those problems? (Answer: Mark & Sweep)
- Which one in your opinion does Java use? Why?
- What’s the difference between an array and a linked list?
- Imagine you had a random list of positive integers, not containing any duplicates. Give an algorithm that would print all pairs of numbers that would add up to 10. Give its running time ( O(n.log n) solution at first). Now improve this algorithm (Came up with a O(n) solution).
- Now imagine the list has duplicates. Give an algorithm that prints out pairs which has totally unique numbers this time.
- Say you were given the task of writing a game of poker, for example in Java or C#. How would you implement it? (I figured this was an OOD question, so I gave a list of what classes, attributes and functions I’d implement, spiced with some design patterns ). What kind of attributes would you give to the cards?
- Imagine you are building the game with a client/server architecture, supporting 4 players, where the clients would connect to a centralized server. How would you implement this? Any issues about security? Cheating? Explain architecture/solutions.
- Any questions?
During the question time, I asked about what he does over there, what projects they work on, how they choose and work on them and other things related to Amazon and Seattle. Here’s what I learnt:
- Amazon have no ’software development cycles’. Features are implemented and put to use on the storefronts quickly (’Finish project yesterday, live today’ kind of quick).
- Amazon is a very agile company. The teams work on a per-project basis and are fairly independent.
- Engineers(software engineers) have a high level of ownership on a project; when given a project, engineers sometimes work individually and sometimes work in teams. They often work on whole aspects of the project, from architecture to implementation, UI, testing etc.
- There are over 1000 full-time engineers at Amazon and the company is in constant growth.
- Seattle gets snow like once a year, and on that day, everybody panics because nobody knows what to do.
- It’s rainy in Seattle.
That was it. I thought the interview went rather well. He asked if I knew what was next and hearing that I didn’t, he said that if both interviews went well, I’d get a call to fly over to Seattle for the on-site interview. The interview ended at that and I felt positive about it.
A few hours later, I receive a call, which I was unable to take, and an email. The verdict was in and I am to get an in-person interview. Instead of going all the way to Seattle, I am invited to go to Montréal this Tuesday where they are holding interviews. More on that later.
Wednesday, May 24th, 2006 @ 9:00 pm 
interviews
RSS 2.0
Trackback
May 26th, 2006 at 10:18 pm
I understood NOTHING from that post but it’s still nice to see you have a lot to say.
May 28th, 2006 at 5:28 pm
I know the difference between an array and a linked list….YES!!!! But that’s pretty much it for me…unemployment here I come!
May 29th, 2006 at 2:29 pm
Congratulations on getting into the 3rd round of interview! I hope everything goes well for you tomorrow
July 30th, 2006 at 1:22 am
what’s the solution to the question where you find all pairs adding up to 10? i know the o(n ^2) solution heh.
how does the binary search and o(n) search work?
July 30th, 2006 at 1:42 am
hmm okay after a little thought, does this sound correct?
o(log n) solution:
foreach item in the list //O(n)
do a binary search for 10 - item (if result is negative, skip) // O(log n)
total time O(nlogn)
o(n) solution:
foreach item in the list //O(n)
int diff = 10 - item //O(1)
search hash table for key (diff) //O(1)
total time O(n)
July 31st, 2006 at 2:10 pm
A hash table insertion is O(1) if you use chaining as a collision resolution strategy. But its search time is potentially O(n). A running time of O(1) for search is possible, but its the best case solution, i.e. when there has been no collision.
The solution that I came up with is as follows:
Assume list is sorted (even if it isn’t, it can be sorted in O(n)) & that there are no duplicates.
Have a pointer p1 point to the beginning of the list, and have a pointer p2 point to the end of the list.
while( indexOf(p1) != indexOf(p2) || indexOf(p1) > indexOf(p2))
sum= p1+p2
if (sum < 10)
p1++
else if (sum > 10)
p2–
else
// sum == 10
print p1, p2
p1++
p2–
effectively, the algorithm runs through the list only once and prints out every pair that’s adds up to 10
January 31st, 2007 at 1:45 am
what about this
put them into a hash
for 1 - n item{
if n>= 10 next;
push n to hash as a key
}
for 1 - n item {
if n>= 10 next;
if hash [10-n] exisits
print n, 10-n
}
0(n)
January 3rd, 2008 at 10:27 am
Hi Oliver,
could you explain me the solution you gave for the 4 player client-server architecture game?
Thanks
Gowri
January 26th, 2008 at 9:33 pm
Quicksort will take O(n)
then compare for each i=0..n: (a[i] + a[i+1])
O(n) + O(n) = O(2n) = O(n)