My Google Phone Interview

 | March 20, 2008 3:23 PM

Today I phone interviewed with Google for the 5th time. I have already been rejected four times.

Surprisingly I was nervous. I am not sure why, I have gone through this so many times but I think being put on the spot and being technically tested makes me nervous. This is not good when you’re interviewing, it’s better to be confident.

I was asked first why I want to join Google, especially considering I seemed happy running my own consulting company.

Next were the technical questions.  First the interviewer asked me what I did not like about Ruby.  I talked about how I was not used to strongly typed languages.  He corrected me by saying I meant statically typed languages.  I was then asked some questions about garbage collection, how does it work, when does it get called, when and why would you manually call it? I think I did okay with these questions but I did not ace them.

Then I was asked an algorithm question about shuffling a deck. I came up with the expected solution which is get a list of cards, then randomly remove a card. Each time you pull out a card is O(n) because you have to resize the list so pulling out all n cards is O(n2). I was then asked to come up with a better solution and I could not really. I tried using a stack instead but then it was O(n2) to shuffle before putting the cards on the stack. I tried randomly pulling out cards and then tagging if I took them so that I don’t have to resize the list, I just look at the tag to see if I took it already. But then there’s a problem of finding the last few cards that weren’t selected since the probably of finding one continues to go down as I select more and more.

Afterwards I looked up on Wikipedia and found two solutions. One was to randomly assign different numbers to each card and then resort the list. That would be O(n log n). Immediately I thought to myself “Why didn’t I think of that? Whenever something is O(n2) that immediately screams out you should try a sort.” The next solution is even better where you move down the card list and randomly swap the card with a card that hasn’t been swapped yet. This almost seems obvious since that is kind of what you do when you shuffle.

Oh well, maybe next time.

No Responses to “My Google Phone Interview”

Care to comment?