Sunday, August 24, 2008

Interview with Google

I had an interview with Google R&D in Beijing, China on 08/08/2008. Nice day ha :)

Four week ago, I received an email from a professor in Vietnam said that Google need people to do Vietnamese Natural Language Processing in China. They need people who is good at programming, has experience in NLP and Vietnamese is a must. I applied at got an telephone interview invitation. They created a share document on Google Docs so I and the interviewer can share notes. I had a week to prepare.

I prepared by reading:
To improve important skills:
  • Algorithms
  • Problem Solving
  • Programming
At the interview day, the guy who interview me called late 30 minutes and was sorry because he had been busy. The telephone connection was not good. The guy could hear me clearly but I had difficult to hear him. I asked him to call again but still the same. We started the interview.

They didn't ask about programming skill and experience.
They didn't read my blog too :))
I was surprised while knowing that none people from China spent more than zero seconds on my blog. It means that my interview (in China) never read my blog although I put links to my blog on cover letter, emails and resume. I believe that any web company will ask "Do you have a blog?" to most of their interviewees. The assumption is that: If you love your work, you should write about it; and blog is the most effective way to let people know that. Don't know why Google China don't care about enthusiasm. The strongest force that make people great. All of web startups (include Google) was started with a small team with a lot of enthusiasm.

Come back to my interview. I was asked two questions. One about C programming language, one about algorithms.

Q1: Tell the different between following C codes?
char *a = "A";
char a = "A";
char *a = 'A';
char a = 'A';

Q2: Given a group of people. There is only one or none star in the group. Everybody know the star. The star don't know other people. Given a function know(a, b) that return true if a know b, return false if a don't know b. Design an algorithm to answer that is there a star in the group and who is the star.

I answered Q1 smoothly. It's not a tricky question. Anyone who know about C pointer and C string can answer Q1.

For Q2, I showed the interviewer a naive solution with two for loop that take O(n^2) time.
The interviewer asked me to improve the algorithm. He was emphasis that could I design an algo that take O(n) time only? I thought for a while and still don't have an answer. I remembered that in "Get a job at Google" post, Steve Yegge said that we should think graph first. I draw a graph and saw a solution there. I told the interview I got a solution when describe people and their relationship as a graph. The interviewer reminded me that we don't have a graph already, and it also take O(n^2) time to build that graph :)) Steve Yegge's advice did not work in my case. Ha ha. I ask for more time to think carefully. Finally I found a solution, it's an easy solution that I should came up with earlier. I was nervous. When we treat people as a set and try to eliminate non relevant elements from the set. We can solve Q2 in O(n).

The interviewer approved my answer and he asked me if I have any question for Google. I smiled because I had practiced with my friend before, Dinh Hai, he acted as the interviewer and asked me as much questions as possible. He told me that I should ask Google some fun questions, he suggested this question: "is it true that at Google, the food never be placed away from programmers more than 8 meters?". I asked the same question to my interviewer and he laughed. The trick worked, thanks Dinh Hai :)) I also told him that I have motivation to do Vietnamese Language Processing to help Vietnamese people understand English better and help Google search Vietnamese documents more accurately (It's a win-win situation) and asked about Google plan for Vietnamese. He said that he is not a member of language processing group and could not answer my question. It was my last question and we finished.

Two weeks later, I received a "thank you" letter from Google said that currently Google did not have any position relevant to my skill :) I guest Google need a person who really do Natural Language Processing and good at C/C++ or Java. My job is web development using Ruby and JavaScript. It is not a good match. Before the interview, I realized my weakness and betted on my enthusiasm and motivation in Vietnamese language processing. It did not work :)

What I learn from my interview?

First, big company care about computer science. They want people who master algorithms and have good problem solving skill. The better computer science you are, the bigger chance you have.

Second, interview over telephone is not a good idea. Bad telephone line can reduce the quality of the interview. I had to asked my interviewer to repeat the questions, and needed to confirm with him questions' content.

How about your interview experience?

2 comments:

oriondream said...
This comment has been removed by the author.
oriondream said...

Reading this post makes me feel as nervous as I am being interviewed :( .