Google Onsite Interview 11.20

Every interview in Google seems really lucky from the on campus all the way to this onsite interview .

Heard passing the on campus interview at the second day and was told some HR from Mountain View would contact with me. However one week passed still nobody contact me in the mean time others have already been contacted by the hr and started to schedule the onsite interview.

So I contacted with the university hr and one hour later a call came from Mountain View. It seems that he forgot me. He told me GTECH team was interested in me and would sign a onsite interview. That was a Friday and the interview was scheduled at next Thursday while I would have Facebook at the Monday. So I fried to San Jose twice in three days.

Just skip all these stuffs and let’s start the interview. Three interviews in total and a unofficial lunch with one engineer. Google’s interview is even more straightforward then Facebook. Even the self introduction is eliminated and just start with a ‘hi’ and followed by the coding problem. Because of signed NDA, I cannot talk about the detail questions.

Compared with Facebook to be honest I must say the culture of Facebook seems is better then Google in some content. Because the Facebook is new and young. Just like the previous days compared Google with Microsoft, it is the same now when compared Facebook with Google.

However Google is still really attractive not because its free food or beautiful campus or work space.  Those are not advantages compared with Facebook. I think the most attraction for me is Google is the only place where I could probably have chance to reach some great technology like GFS, MapReduce or BigTable. This is the only place. And those are the best ones in the world. As a engineer I must say it is impossible to resist such temptations of great technology. 

以下是面经部分。。


1st interview. One white handsome man with a asian shadow.
(1) build up the sibling pointer for every node in a binary tree.
        I just did this problem with constant memory in about 2 days ago. So I said there are two solutions. First uses a BFS to do the level order traverse and in each level just build the siblings in the next level which uses O(n) memory. The second also traverse the tree but take advantage of the current level are already build up and thus we only need the left most node of each level would be fine which uses O(1) memory. And he said the first solution could be fine and I implemented it in couple minutes.
(2) Given a list of characters and a dictionary, find out all the words in the dictionary which can be  built using the characters from the list. There are duplicates in the list and each character can be used only once.
I found two ideas which use hash or prefix tree as a dictionary. He asked me to do the second one. So I first preprocess the input list as a list with distinct characters and its number. Then use a DFS to generate all the combinations of the words built by the characters from list. During the DFS each step check if each character could be used by two conditions. If there is still available number. And if it resides in the next level in the prefix tree.

2nd interview. One white man who was late for 15 mins but made up it
Only one question something like a design problem but not. Say you are a project manager and someone need you to implement one class. The input of the class is a segmented linear function. And when given a x you need to return the y value corresponding to that segmented linear function. After several rounds of back and forth I started understand what he wanted to implement. Actually it was to use nodes in the edge of each segments to represent the segmented line. And then the coding part is given two segmented linear function and how you use add them up to a new one using the node representation. Do a merge by O(n) time complexity. Then he asked what’s the time complexity by adding m functions all together. I said that’s a better solution to do the bunch merge. He said it’s fine just answer the time complexity by your current algorithm. I said it’s mmn. Then I said I could optimize it. Because it’s already out of time and the next engineer is waiting outside the door. He said “your’s is already better then others”. Hope he didn’t lie me.

Unofficial lunch with a Asian engineer who is really nice and friendly and shared me a lot of feeling about working here.

3rd interview. Some one looks like Bosh who dropped the UCI degree and came here.
At first a little bit arrogant. But after coding part he became really nice and friendly. Totally agree that the ability decide how others attitude to you. And this round was the most satisfied one.
Given a real time infinite input stream with numbers. You are asked to implement a algorithm that could stop the input and return the current medium of the previous input stream.
I gave several different implementations.
(1) just use a vector. Insertion O(1). Get_medium O(n)
(2) maintain it is sorted. Insertion O(n) get_medium O(1)
(3) binary search tree with each node store the number of node in the subtree Insertion O(log n), get_medium O(log n)
(4) two heap Insertion O(log n), get_medium O(1)

Then he asked me implement it by two heaps. I did it. Then he asked me to test by a lot of test cases. I just wondered why he ask me to do so many. Then after doing all the test case correctly. He told me my solution is better then what he thought. Now I understand why he is so eager to run a lot of test cases. Because he just doesn’t want to believe my better solution is correct.