I just finished my phone interview with Google. It lasted 50 minutes. How did I do? I think I did OK. There were some things that I did not know and a lot of things that I did OK, in my opinion at least.
I stepped out of the office at lunchtime and went into my car to talk. It was not the most comfortable place but it was OK. I did not have to start my car since it was sunny so it was fairly quiet. I could not understand the guy, though. He was African descent and had a heavy accent. At time, I had to ask him to repeat what he said. But I wanted to make sure I understand what he wanted.
It started out as a “introduce yourself” type of questions. He asked me about my work. What types of projects I’m doing. What I’m doing now. Do I know any language? Did I work with other languages? I told him PHP. He asked me what I liked about Java? I told him that I like its type safety (vs PHP), maturity, and higher level of abstraction than C/C++. What do I don’t like about it? I could not say for sure. But I said Web services support, XML support, as compared to C#.
He then asked me to list sorting algorithms, explain what they were and their running time. I told him about Bubble Sort, where you go down the list and find values that are lower and swap them (order of O(n^2). I told him about Insertion Sort, where you also start at the beginning and keep a sorted list that grows at the beginning of the list and as you traverse it, you keep adding to it (also O(n^2)). I also told him about the Merge Sort (keep dividing recursively halfs of the list until you have one item and then you combine them (O (n log(n)). He asked me about Quick Sort, I told him it’s similar to Merge Sort, same runtime, but the difference is how you pick the middle — the breaking point.
We moved ahead into problems. He gave me a problem and how would I solve it.
You are given a number 1 to 100, how do you find out which number it is? I told him you can use Merge Sort algorithm, divide it in half, and one more time, so on, until you find it. He said whether there is another way? I could not really think about one. Then he asked me how many times it would take to divide. I was not sure how to answer it. I guessed. He said whether maybe there is a way to optimize it how you divide, and I agreed.
A burglar comes into your apartment and steals your dog. He wants to leave a ransom note but does not want to write it. So sees a lot of magazines so he figures he will use the letters from it to compse the message. The message he wants to compose is n characters, and the magazine has m characters. How can you check m has all of the characters. It took me some time to do this. I finally thought of a solution. You have a two maps, mapN, which has a key of letter and a value of number of times it occurs, and a second map, mapM which also contains the same setup. You iterate over mapN and make sure mapM has enough characters, if it does, you remove it from mapN. If map N is empty, you have enough characters. If not, you don’t.
He asked me whether there is another way. Could not really think of one. He said what if space is an issue and you have an array. I told him that you could asci representation of the characters and have a number of occurences. He inquired about whether you start at the 24th space. I told him you can have a simple conversion when you look it up to substract 24. He then asked how it would work. I told him that you can iterate over the list n, and each time, you decrement the number of occurences in the array n. If you have a negative you can stop.
He then asked me another problem. He asked me to write a function to that takes a list and the list can contain a string or another list. The objective is to take the list and flatten it. I wrote it out like this
public combine List(List list) {for (Object item : list) {if (item instance of List)list.addAll(combine(list));}return list;}
He said that he does not want the original list returned. So I modified it to the following.
public combine List(List list) {for (Object item : list) {if (item instance of List)List copy = (List) item;list.remove(item);list.addAll(combine(list));}return list;}
He said whether you can remove an item in recursion. I said yes, that might be a problem. So I said that you can make a new list and just keep adding to it. He said, OK.
He then asked me whether I have any questions. I asked him how long he’s been there (3 years). Does he like it? (yes, he gets to work on different projects, though not everyone is doing that). I aked him how I did? He said he cannot tell me. 🙂
Overall, I think I did OK and I am hoping to get called back; though I would not be surprised if they don’t call me for onsite interview.