Today I had an interview with Amazon.com. 
They had also requested an online evaluation using brainbench.com (also called
123assess.com). Whatever, the online test was somewhat not very exact and not
very clear. The answers were somewhat ambiguous.  So anyway, in the interview
there was this guy from amazon and he asked some very intelligent question. I
really liked him. His questions were not like some other companies where they
just ask you to recite C code or some some programming tricks. Rather, he would
pose a problem, wait for you to respond, hint if you could not solve it and
eventually lead to the solution. There were a lot of algorithm analysis type of
questions including big-O notation analysis of the scheme/algo/code I wrote for
any problem. Even though he said that he works with some very smart people, I
doubt that every one of the people at amazon is as good. He asked about hashing,
trees, string operations, garbage collection and in general big-O analysis of
all the answers that I provided. 

<p>

A sample question from the interview was to
come up with an algorithm to efficiently shuffle a deck of cards given some
random number genrator and then give the big-O complexity.

<p>

After an unsuccessful interview with Microsoft (where they asked almost trivial
questions and were definitely not testing my intelligence), I searched online
and found/realized that in any technical interview, you should think aloud i.e.
you should tell the person in front of you as to how you came up with a
solution. So, for example in the above question, you could start by telling him
what are the main tasks involved in solving the problem:

<ul>
	<li>Need a way to generate a listing of numbers from 1-52 (Random number
genrator, RNG, is given)
	<li>Since the RNG can generate the same number more than once, you need
to make sure that you keep generating numbers until all numbers 1-52 are
covered. 
</ul>

Then  you need to muse a little and say something like, if you keep generating
random numbers and hope to hit all the 52 numbers, potential complexity of the
is extremely high because by a really bad stroke of luck, you can keep hitting
the same number over and over again.

<p>

Then you need to think aloud, hey RNG is a costly process, what can I do so 
that I need to generate RNG a minimum number of times (say 52 itself). Then you
exclaim eureka and say that how about keeping an array of numbers from one to
52. Generate a random number from 1-52 pick the card at that index, remove it,
shorten the array to 51 and repeat the process until no more cards are left.

<p> At this point you exclaim that the "shortening the array" would cost too
much because you need to shift everything in the array after each card is
chosen. Then you exclaim "aha" and say that how about each time I pick an index
from the array, I swap the last element of the array with this index, decrement
the length of the array by one and repeat. You get to claim that the complexity
of the algorithm is O(n).

<p>
Also on saturday we had the taekwondo test. I tested for the blue stripe. Again,
the board breaking is something I need to learn how to do. I hit with sufficient
power but the aim was wrong and I did not break it. So, retests, here I come.
The rest of the test was quite good and I did well on almost everything else.
Dr. Speyer said that I did well, so cool.

<p>
In the night Craig hosted a costume party at his place. Well, I put on a dhoti,
rudraksh and dark black goggles and appeared there. Nice party, much 
fermented juice was drunk, but I prefer unfermented juice. Then there were some
kiss auctions and by this time people were pretty much heavily drunk. I had some
work to do next day so I left at around 1:00am...