In another 6 days, my summer internship program at Google will begin. I have been waiting for over 7 months for this to happen. Google booked a flight for me to get to Bangalore and a cab to take me home from the airport. I am expecting the best from Google. So how did I get here? Since this is my tech blog and not the philosophical one, this post is about how I got my internship at Google.
I faced 3 rounds of telephonic interviews involving questions on algorithms and problem solving in a span of 3 weeks. This was my second interview. The first one by Microsoft did not go that well. I RG-ed myself in IITM lingo (caused my own failure). Learning from my mistakes, I was well prepared for the second one. One thing that I learnt from my mistakes was that I did not speak much about myself. I thought of everything that I had done and planned on what to speak about myself with the interviewer after that. I had been SPOJing out of interest and addiction. That did help me a lot.
My first interview lasted around 50 minutes. I spent the first 15 minutes introducing myself. Then started the programming round where I had to write a piece of code for the atof function. Although the task seems simple, converting an error free string to a floating point number, the actual work involved writing error free code and tracing the code like a machine and analysing the function to find the exact number of multiply-divide operations. My initial code took 2*N steps, I had to reduce it to 1*N multiplications using simple optimisation principles. The next question involved mapping an arbitrarily sized string to a number. That is quite trivial as its just conversion of bases. The final question involved generation of all possible subsets for a given set. A binary tree with recursion or a bit-vector iteration from 0 to 2^N are simple ways of generating all possible subsets of a set of size N. The interviewers were happy and I was selected for the next round scheduled after a week and a half.
The difficulty level of the questions increased with each round. This is clear considering the simplicity of the questions in the first round. The second round was interesting. The algorithmic question asked me to find out the total number of ways in which 2*N number of people sitting around a round table can shake hands so that no hands cross. I wasn’t aware about this problem and it turned out to have some interesting results as I discovered during the problem solving session. I quickly suggested a recursive approach where we divide the table, recursively calculate the value for the two halves, multiply them and sum it over all possible divisions of the table. The image in this link should make it clear. This was done in the first few minutes and I suggested a pseudo-code for the same. The interviewer then asked me to make it more efficient and gave me a hint asking me the number of times the value F(10) was calculated while calculating f(20). That suggested I had to use dynamic programming and memoisation. I suggested an alternate version for the same where you maintain an array ‘F’ and remember the outputs of the function ‘f’. I further suggested an iterative alternative for the recursion where f(n) was calculated after all f(i), i < n are calculated. The interviewer gave the last hint through which I realised that I was calculating nothing but Catalan numbers (A simple recurrence relation). The rest of the interview involved some simple questions on C++ language right out of the text book. (Private constructors, static functions, object method invocation after destruction …) The second interview was over in just half an hour.
The final interview was scheduled a couple of days after the second. The first question was a graph theoretical question where I had to find the maximum number of edges in an DAG. The right side implication is just a proof by example and the left side implication was proving that only nC2 pairs of unordered pairs (a, b) can be constructed. The next question was the first one where I actually wrote code. I had to write a program to find the number of 1′s (S(n)) in the series (0, 1, 10, 11, 100, 101 … B(n)) where B(n) is the binary representation of n. Eg S(5) is the number of 1′s in (0, 1, 10, 11, 100, 101). S(5) = 7.
I remembered something that I learnt in my combinatorics class which suggested S(2^k – 1) is easy to calculate. S(2^k – 1) = k * 2^(k-1) is a very easy formula to derive using summation and I did that in the first 5 minutes.
S(7) = 3*(2^3) = 12
I had to write code which worked for any n. This involved extracting the first bit of the number and processing the rest of it. I had a vague recurrence relation in my mind and I spent over half an hour trying to ‘write’ the code which worked for all end cases. There was a small bug in my code and I could not fix it in time and the interviewer moved on to the next question. I could have typed out the code in my computer and executed and tested instead of manually tracing the program with code written on a piece of paper.
The last question involved suggesting a strategy for Google to suggest alternate search results in case the user makes an error. The “Did you mean …” part in a google page like here. I suggested naive strategies like flipping the characters in the query to see if better search results are obtained. The idea is clearly not scalable because of the sheer number of ways the user might have made the errors. I further went on to suggest using the keyboard key-placement and restricting the character flipping to just the neighbouring keys. This again wasn’t good enough. The interviewer wanted a better approach. I though for a while and suggested a directed graph structure for queries where there are directed edges from one string to another if there is a high probability of the suggestion. The edge-weights could be proportional to the probability of error. The closest few neighbours of a given node would list the most likely queries. A simple BFS could reveal the closest neighbours. The problem now was in the assignment of weights to the edges for which I had to suggest an algorithm. I thought on the lines of people querying for something, not being happy with the results, changing the query immediately to get a good response. The edge between query1 and query2 could be inversely proportional to the number of times the same happens. The interviewer was pleased with the approach. I then requested him to give me a few minutes to complete the program. I fixed the bug and submitted the code and it worked great in logarithmic time. (Linear on the number of bits in ‘n’)
In a couple of weeks, the HR called me up and asked me to send my certificates and informed me that I had been selected for internship at Google.
Update: http://picasaweb.google.com/photos.jobs/IndiaOfficePhotos# has a collection of images that describe the environment in Google. Looks awesome!