Tech interview preparation

This is adapted from an e-mail I wrote in January 2007 (when I was a junior in college--after I'd gotten internship offers with Google and Microsoft but before I knew anything about life). Though my Google full-time conversion interviews were more of the same (of the technical stuff--the interviews were longer, so the questions were a little deeper), this is probably mostly relevant for applying to internships.

For Harvard people: At the Office of Career Services they have (or had?) a nice small booklet on how to prepare for the interview. It gives some pretty good advice about how long you should spend preparing (the number of hours in proportion to how long your interview is) and it has you do a self-evaluation.

Here are some websites with puzzles:
http://www.techinterview.org/
http://halcyon.usc.edu/~kiran/msqs.html
The programming questions on this one are good as well.

This website is good for the nontechnical aspects of the interivew:
http://www.wetfeet.com/

So some non-technical questions I've gotten are:

• Tell me about yourself.
• What was your favorite computer science class and why. (You will often be given questions based on what you say your favorite class is.)
• Tell me about a time you solved a problem creatively.
• Have you been in a situation where a project you've been doing has gotten off schedule and you couldn't make the deadline? What did you do?
• Have you ever been in a situation in which someone has pushed you to do something that you didn't want to do? How did you respond?

Some technical questions I've gotten are:

• How would you represent friendship networks on Facebook? (Say you have a list of people and their friends.) I was asked on what data structure I would use, running time for searching through it, space complexity, etc.
• Given a vector of numbers, how would you find the median? Second part: say we chose a number and then put everything less than it on one side and everything greater than it on the other side. Assume we could throw away half the list each time. What would the running time be?
• How could you get unbiased flips out of a biased coin? (Say you had a 2-side coin of unknown probability p of landing on heads--if you wanted to make an unbiased decision between 2 choices using the coins, how would you do it?)
• Write a hex to decimal function.
• Write an insert function for a circular linked list. If we are inserting into an empty list, how can we make it circular?
• Write an insert before function for a singly linked list if you're only given the pointer to the node you want to insert before. (Hint: How can you turn this into an insert after function?)

Some good advice I've gotten has been:

• The most important thing is to talk through how you are getting the answer. Even if you don't get the answer, talking through it to show how you think is very important.
• If you get something wrong and they tell you the answer, don't argue with them unless you are sure your answer is right. (Think through it first, and discuss rather than argue!)