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(n²). 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(n²) 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(n²) 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.

Related posts:

1. Christianity Today’s Interview of Barack Obama
2. Dylan’s Valentine’s Card
3. Google Analytics or WordPress.com Stats
4. Google Social Graph API
5. Permanently disable Google Personalized Search

Categories: Frank
No Comments »