Google Interview

Prompted by a recruiter, I submitted a resume to Google. They let me skip the phone screen and just do the full-day interview with 5 guys. It was easier than I feared. If you can do the first half of CLR you should be fine, except for trick questions. Unfortunately, I think I blew my last interview. He posed a simple problem: Given a lot of files, find all the duplicates. This is easy. Hash all the files, store each in a Map<hash#,filename> and whenever the key already exists you’ve found an identical file. So he asked me to implement a hash function. I thought he wanted a real hash function, which is very complicated. I fumbled around for a while and suggested XOR could work but it sucks for many reasons. He said XOR was fine, surprised that I was struggling. Then he asked what the odds are of a collision, except he asked it in a weird way that I didn’t understand for a while. I thought he wanted to know the odds of collisions using XOR as a hash. I know that XOR doesn’t distribute hash keys uniformly for normal input, but there’s no way I can compute the probability for it. I fumbled for a long time. Finally, I said it’s 0.5^N for N bits in the hash, unsure of what he was looking for. The whole interview went like this, including how to implement a hashtable. He asked a vague question and I misunderstood it as something much more complicated. I didn’t realize we were talking past each other until he told me what he was looking for at the end. So now he will probably tell the hiring committee that I don’t know about hashes and hashtables. That’s too bad.

One comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s