The Night Before Google

‘Twas the night before Google, when all through the house
Not a creature was stirring, not even a mouse;

Tomorrow’s outfit was picked from the closet with care,
In hopes that the first impressions are fair;

…

It would be interesting to complete “The Night Before Google” however it could take hours and I want to be up around 7:30 so that I am ready for my 10AM start at Google headquarters tomorrow. So to keep this simple I wanted to write about my experience becoming a Google intern.

I applied for Google internships online back in January. It was actually an interesting experience because their jobs site is like a shopping cart. It allowed one to add five jobs to the cart and submit their information along with a resume and cover letter. To maximize my chances I selected five internships which seemed suiting and then quickly wrote a cover letter. My letter was very informal, in fact I mentioned the informality within it, however it apparently was sufficient because a few days later I was contacted to setup two phone interviews with Google’s Platform division.

It’s been quite some time since my interviews however both interviewers asked me general questions about the TCP protocol and networking tools of the trade. The good stuff was the technical questions which I will provide. Feel free to comment with your solutions, however I will omit mine.

1. Given two sorted lists of positive integers and a number N, describe an algorithm which determines if any two numbers in the list sum to N.
2. Describe an algorithm which determines if there is a cycle in a singly linked list.
3. Describe character for character the C code to reverse a 32 bit integer. If the following string represents a 5 bit integer “10011” the reverse would be “11001”.

A few comments and hints for those having some difficulty. The first can be done with constant memory and O(n). The second can be done in O(n) but not constant memory, or an alternate solution can be done with constant memory but not O(n) running time. The third is quite trivial, however try programming via voice over the phone; it’s not the simplest task.

Well that’s all for this one. I should have a post about my first experience at Google soon.