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 =)

I came accross an article on lifehacker yesterday and it was called the 10 Steps You Can Take To Guarantee Failure. This article is rather interesting because in addition to being funny (not laughing off my ass kind of funny, but still funny), it contains pearls of truth. How many times have I wanted to do something and it didn’t happen? And its not the desire for that something to happen that is lacking often times.

Although other people have written whole books about the subject matter, this article sums up some nice points. I don’t think there is one most important point in the article as they are all requirements to success, in my opinion. As what it says in point number 5, or rather the contrapositive of it: Don’t talk, do! (that’s my favourite one right there) and have fun.

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:

1. 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).
2. Amazon is a very agile company. The teams work on a per-project basis and are fairly independent.
3. 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.
4. There are over 1000 full-time engineers at Amazon and the company is in constant growth.
5. Seattle gets snow like once a year, and on that day, everybody panics because nobody knows what to do.
6. 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.

The new buzz word is currently the hot stuff in technology circles. Everybody hears about it, talks about it, but not everybody knows exactly what it is. That’s what I’m talking about when I say its like Che: all the kids wear those T-shirts sold by the gap. Do they have any idea who che is? NO! In a similar fashion, everybody wants to jump in the web 2.0 bandwagon.

O’reilly does a good job explaining what “Web 2.0″ is. Mesh was a conference held Monday & Tuesday, 15 & 16 of May in Toronto. What was it about? Web 2.0, the ripples it promises to cause in society, media, business and more. Why have a conference held when we could all read a damn article on the net and be all happy? Well, the point was meeting the people that are causing the ripples and actually start one too, hence the ‘connect, share, inspire’ tagline.

As per the schedule we had quite a few keynotes, workshops and panels. Most of those were really interesting but in reality, these were all excuses and conversation starters for what would happen in between/after them; in line for lunch, at the little cocktail-party on Monday and particularly at the bar.

There have been many blog posts written about the conference, so I won’t explained what happened there, but I’ll give my take on the meta-information I grasped from there:

1. Elliot Noss, CEO of Tucows, plays World of Warcraft and is actually very funny.
2. Everything you learn, you learn more when there’s alcohol involved.
3. Waiting for food gives you the opportunity to go get drinks, which in turn allows you to learn more.
4. Holy crap, most geeks actually look normal.
5. Shameless plugs work: taking the mic at the proper moment and promoting yourself gets you the desired attention.
6. If you don’t go to the bar afterwards, you might as well have not come… sorta.
7. Where the nice chicks are (Amber was there!), the geeks flock like fat kids to pizza.

The moral of the story is this:

Web 2.0 is nothing new, it is just enabling what we’ve been doing for ages: meeting people and creating connections. It’s all about sharing and having an opinion. Web 2.0 is the virtual re-enactment of Mesh… sort-of:

• Some person says something stupid at the keynote (how does the name pinko sound to you?) and you get the fanboys/nVidiots/trolls/flamers all cussing it up on the way to the food table.

• When nerds see chicks, (by chicks i meant Amber, see above) they go crazy: the panel Amber was hosting seemed to be very rowdy!

All in all, the next time you hear there’s a conference like this, just go. Do whatever, sell your used underwear to a pack of weird japanese, steal off your grandma or pledge to do a speech even if you’re a kiddo, just go and don’t forget to get drunk, you might land your next job.

Interviews can induce some stress and some headaches, but if you can expect what’s ahead, you’ll be in much better shape. I hope to help others taking the interview to prepare and to remove some stress on people’s chest.
This is my first phone interview ever and it’s the first one for a full time job at Amazon as a Software Design Engineer (SDE). It happened 2 days ago, Friday 19th of May.

The interview

My interviewer called, introduced himself and promptly started the interview.

• What languages have you learnt in U of T? What tools to you use to program? What platform did you develop on?
• Having first scanned my resume, he first asked about a prototyping project i worked on. And seeing it won an IBM-sponsored competition, he asked what the competition was.
• Then he asked about an operating system project I listed. He asked what I did and what I’ve learnt. He asked if we actually implemented it (hell yeah… so many sleepless nights). And he went on by asking how to debug when developing an operating system.
• What’s the project you’re most proud of? And why so? Mine was online-marking tool, found at pyre’s past project page.
• Are you familiar with TCP? I honestly said that I didn’t know much except handshaking. He said it was fine and he re-assured me I was not expected to know it.
• Are you familiar with HTTP? I said I was, having written a basic web server, which I very briefly explained. He was interested in the web server, so I gave an explanation of the basic structure of my implementation. He asked about how I dealt with concurrency issues, but I didn’t. He then asked in general how to deal with concurrency issues.

After the first part of the interview was done, he gave more clarifications as to what he does at Amazon, and what exactly his group is responsible for. He talked about how this was just information gathering and there was no reason to be stressed. The second part could then begin:

• Give an algorithm that will allow you to find the Nth node from the end of a singlely linked list. We explored many solutions, ranging from the naive algorithm to using a stack to finally getting the solution which only requires one pass.
• Imagine you have a database that can only do 2,000 queries a second. Your web application gets 5,000 queries a second, what can you do to improve the situation? After asking him for some clarifications, he added: Imagine its a stock quote engine for NASDAQ and that the queries are about the top 100 stocks at closing.
• Imagine you have a big online storefront. Your webserver can only do 1,000 concurrent requests. Many people are visiting your website and you want to support 3,000 concurrent requests. What would you do? I asked for some clarifications, and he said: The limitation is computational power and not bandwidth.
• Any questions?

The questions period was the time I asked about things that I found interesting, as in, what kind of model they use for programming, software engineering practices, distributed computing and the like. His answers were interesting, in a nutshell what I learnt about amazon was this:

1. They work in 2-Pizza teams, i.e. the team is not bigger than the number of persons that could be fed for a meal with 2 large pizzas.
2. The models used for the software development cycle is different for each team as they are all very independent. My interviewer is a big eXtreme Programming fan himself.
3. Formal requirement documents are produced when a project is requested to a team. Their “customers” are usually other groups within Amazon. That I think is very cool… nothing like a good technical req doc to get started on the right foot!
4. Once Amazon acquires new talent, the little newb’s information is shared accross the whole Amazon.
5. Amazon is one of the most knowledgeable companies about Distributed Computing.

The interview I think ended quite well and my interviewer said he was definitely going to recommend me to the recruiter for a second interview. Well, let’s cross our fingers =)