Another episode to add to the list of interesting adventures, life obliges me to go through. Though I was not able to reach the destination, the journey was challenging enough! I have been lucky enough to have encountered quite a number of good technical interviews, from both sides, as interviewee and interviewer. This experience changed my perspective of how an interview should be taken (hopefully, I will get the chance to apply this sometime in the future).
And now, onto the interview. Being over the phone, I was terrified. And having to write runnable code on Google Docs while answering questions over the phone did not help the situation at all. To be frank, I hate phone interviews. Physically seeing the interviewer in front of you eases up the process a lot. But I understand that they are unavoidable in the case of big companies, who receive so many CV's and sifting through the lot is difficult.
Enough said; I will get into the actual questions now. So I got the call from Bjorn, a software engineer at Google. He asked me the programming language in which I would like to write the code and I replied C++. I was asked three questions in a time span of around 75 minutes and they progressively became harder and harder. I was also asked to describe the time complexities for all the solutions I had suggested for these questions. I will try to describe the conversation as far as I can remember. These are my answers and if they seem wrong to you, please feel free to comment so.
Question 1) For a lottery of 90 numbers, how can I get 5 non-duplicate random numbers?
Me > Use a random function to retrieve characters
He > What about duplicates
Me > Put the seed in the random function as the previously retrieved number
He > No, changing the seed won't guarantee non-duplicates
Me > In that case, we can add the elements to a set and stop when the size is 5
Question 2) For an ASCII string, find the most repeating character?
Me > Create an integer array of size 128 to store ASCII values...we traverse the string once and increment the count for each character...
He > Consider that instead of ASCII, it's Unicode and the string is very short
Me > We can use a dictionary, so that each character is the key and so only those that are present have to be stored...
He > What if it's Unicode and the string is very very large, lying on different clusters...
Me > Use a distributed hash table for storing...split the string into different sets and calculate the counts and then combine the results
He > Then since it's Unicode, there is a chance that 65536 keys and values have to be sent across the network...
Me > Since we are sending only the count, it should be ok
He > What if we sent only the max count character from each machine...would that work...
Me > No, that would not work, as there can be characters low in number, but when combined could be the max...
He > So, what would you do...
Me > We could calculate a subset of the top counts to be sent across and so the probability of getting the top one would be high...
He > Yeah ok, deciding on such a subset would be a difficult task to do...so lets move on...
Phone disconnects...
Question 3) For a calendar, with start time and end time and 'n' appointments , how would I find the conflicting appointments?
Me > Crude solution...compare each appointment with each other...
He > Ok...so how to improve
Me > We can sort the list based on endtime so that all the adjacent appointments will be close together...
He > endtime or startime?
Phone disconnects....
Me > Both can be used
He > Could you write the code
Me > Ok...
Me > Ok, so then after sorting them, we could take an appointment, mark all the ones that have starttime within the starttime+1 hour...
He > Now, we don't have enough time..so could you tell me the complexities...
Me > I told for the sorting, it would be n log n and the comparison can go upto n^2...
He > n^2, in which case?
Me > If the appointments are different
He > Ok, then, so we are out of time...the recruiter will contact you with the feedback...
He then asked me whether I have something to ask him, which I did. We discussed about that for a while and then he hung up. So that was it. I definitely could have done better. I prepared for the wrong type of questions, based on my previous experiences. I did not know whether I had done well or not as there is a big difference being 'Good' and 'Google good' and it seemed to me that I hadn't done so. Nevertheless, it was the best interview of my life till that time.
The next day itself, I got a mail from Google that made me EXTREMELY happy. It said ‘Congratulations!’ mentioning they had got the feedback about the interview from Bjorn and I can move on to the next round. Alls well that ends well. And so that concludes my first Google interview. I will write about my next one which was the best interview of my life till date.
