Amazon.com - Job Interview

I've taken a 6 month internship with Amazon.com. Not sure what I'll be doing there just yet, but I'm excited to start with such a great company.

Since other helpful people posted their interview experiences on their blogs (and thereby, helped me get the job) I figured I'd do the same.

First of all, Resources:

google.com - Since you found this site, you probably already got this: Find people's blogs to read about what to expect from the interview.
Steve Yegge's Amazon.com rant-blog - A particularly awesome resource... An ex-Amazon employee posted his internal blog publicly after leaving. It had a guide to interviewing employees... which it was very clear that my first interviewer had read that very guide, as he followed many of the points it made.

Highlight posts for Steve's blog:

• Five essential phone screen questions


• Miracle Interview


• Make sure you read the comments on the posts too... much higher quality commenting than your typical "open internet" blog, as this was an internal blog years ago.

That was all I used, but other useful things are basic Java and Object Oriented details. Can you explain multiple-inheritance? What about the difference between an abstract class and an interface? Go reread your old notes, wikipedia, etc. You'll need it.

My second interview was the hardest, though it's hard to say which interview was the "Bar Raiser" that people talk about. None of them were monumentally different. The first interviewer gave me a homework assignment due in 3 hours, which was unusual, but not hard.

I won't post all the questions I got, as some were silly easy: (Fold a 1mm paper 50 times.. how thick will the resulting paper be...? 2^50.)

Only 1 question really caught me off guard:
Given a 32 bit integer, how can you count the number of set bits?

I was really taken aback by this question for a few reasons. First: I have never gotten binary operations in any of my classes so far. Second: I've never even considered that this sort of thing might be important.... or even anything close, so my brain took a bit to get in gear to answer the question.

I gave a quick answer, which I admitted was brute forcing the solution:

Imagine the 32bit integer is x.

I just talked it out, but to explain it better here, I'll write it out in pseudo-code:

z = 1;
for (int i = 0; i < 32; i++){
  x XOR z = y;
  if(y = 1)
      counter++;
  z*2;
}

This worked well enough, but he talked me through it a bit, and I decided that instead of y*2, it'd be better off to do a >> (right bitwise shift) on x, rather than bother messing with y.

I don't believe my first solution would work without a bit of tweaking, but it sounded good.

So... I brute forced the solution.

A bit of googling after the interview lead to several articles like this one: http://graphics.stanford.edu/~seander/bithacks.html

There is a way to do it in constant time... but that takes a very special person to figure out on the fly in an interview. ;)

That question threw me off rather badly, as it was wholly unexpected, so the next question he asked me... which SHOULD have gone in the "stupid easy" category, took me a bit of work.

Remember what I said about getting into the right gear for the first question? Well, upon setting that gear in my brain, the gear-shift stuck solid, and I had a hard time getting out of it.

Here's the second question in that interview:
Given two integer registers, how would you switch the values without a third register?

My first thought: "Wow, I hope a register is like a variable, cause I've never heard that before" so I pretended that they were variables, and it turns out my guess was right, as the interviewer didn't correct me.

Brain gear: bitwise operations. Question? Apparently solvable with bitwise operations.

Given two ints, x and y:

x XOR y;

Figure out which bits are set following the XOR, then flip the bits in both x and y in each position that is set.

Tadaa, x and y are flipped values. (Note: I don't believe you can do that without a third variable, but I think that slipped past the interviewer).

The interviewer responded that he liked my solution but wondered if I could do it with more conventional means... my brain snapped back into conventional mode and replied immediately, albeit flatly, realizing I was overengineering the solution:

Oh.

x = x + y;
y = x - y;
x = y - x;

The interviewer laughed, and said very good.

His final question was for me to find the depth of a binary tree.

I TRIED and tried and tried to explain to him what I was thinking... and some how I couldn't convey what I was thinking. After 5mins of failing to convince him I knew what I was talking about, I asked for his email address and emailed him this:

static int findDepth(TreeNode root) {
    if (null == root) {
        return 0;
    }
    return (Math.max(findDepth(root.getLeftChild()), findDepth(root.getRightChild()))+1);
}

Sigh. Well, apparently that convinced him well enough, as I got a call for the final interview later that week.

Hope that helps someone out there. I'll update this post with other points if I think of any. Leave a comment if you want ot know more. I start work there at the end of March, as my 3rd interview was easily the best of my 3. :)