idea's blog

Recently, I had a experience of Google interview(Beijing, China), I went through for three rounds of the interview. Firstly a phone interview, secondly an on-site interview in Google building, thirdly also an interview in Google building but with two people.

We didn’t talk too much on the phone during first call from Google HR, a kind lady. Actually, it was because my spoken English, you know, I didn’t even speak a English word during the past threes year. But I suggest I should directly go to there office and have a face-to-face interview.

The guy was an engineer, we had a comfortable conversation. He asked me to traverse a binary tree for the first question to work out. I was not simply the Preorder Traversal, Inorder Traversal or Postorder Traversal, but to print out every node when you left it behind, it was: Parent-Left-Parent-Right-Parent order.

The second question was based on the first one. I was asked to transform the output of the first question back into a tree. This one was more easier, I worked it out within 3 minutes. All codes were written in Python.

So I got into next round, also a coding and algorithm interview. I was asked to find out the Not-intersection set from two lists. He wrote a prototype of C++ function, then I asked if I may change the return type from list to list pointer, and the parameters from list to list reference. I firstly wrote one with two loops and STL list.find(), it was O(n2). We both know Google would not satisfied with it, then I said it should be using hashmap, not the solution. The he said the lists are ordered.

Next question was to find one random element from a list with an unknown length, with we only had a random function that returns double in (0, 1). He said that was one of the problems he faced in Google works and has not yet figured out a acceptable solution. I said it would be two traverses through the list, one to find out the length, and one to return the randomed index one. Until now, I still don’t know how could it be improved. But later after came home, I find something interesting relative to the question, and wrote a mail to the interviewer about that.

The last interviewer, I felt a bit weird about him, the conversation totally turned us into opposite sides. You know, people have feelings about each other at first glance. He asked me to design a web system like is.gd – the URL shorten service. Firstly, make it work, then supporting enormouse number of users, multi-IDC, distributed system synchronization, etc. I thought this as a wide question, so I didn’t answer into specifics, but he did not caught my idea at all! He asked something like how to distribute HTTP requests on multi servers? I said we may use network hardwares, or software like LVS, or HTTP proxy server(e.g. lighttpd, nginx). Oh man, what were you expecting for? Is this a question about certain technic, or is this a question about system/architecture design?

He realized the question was a blow into the air, so he followed with an algorithm question. Which I don’t want to talk about here, because I didn’t work it out at that time. It was not a complicated question, but he told in a unprofessional way. Howerver, time spending with this guy was not pleasant, it should be a friend-talk, which I expected.

You may have guessed out the consequence, I failed the interview for my weakness in algorithm. But I actually made a big improvement on my career since three years ago. I sent my resume to Google when I was a university student three years ago, and I didn’t even get a man-made reply. This time, I went a further way.