Google behind the screen

Review



Related posts:
* "Speed is king" or "how to prepare for future?"
* The Machine is Us/ing Us

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:

• Tuyển tập các câu hỏi phỏng vấn by Ngo Quang Hung
• Get the job at Google by Steve Yegge (a Googler)
• Introduction to Algorithms
• Elements of Programming

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?

"Speed is king" or "how to prepare for future?"

Google said "Speed is King". Who don't believe please try to build a better search engine than Google :) Why Google is so fast? What is the reason behind? I invite you to "a Google Behind-the-Scenes Tour". Let spend few minutes to go through slides before continue reading this post.
.
.
.
.
.
.
After the tour, you will discover that Goolge is fast because they do distributed computing with huge of commodity computing units that give best performance/cost ratio.
The key is that Google invented a simple programming model that applied to many large-scale computing problem called MapReduce (inspired by map and reduce functions in functional programming).

MapReduce hide a lot of complicated problems in distributed programming (like parallelization, load balancing, handling machine failures, robustness ..) from programmers so that their can buid efficient programs quickly and easily (Learn more about MapReduce here, and Google Architecture here. For an overview, the tour above is enough :)

MapReduce usage statistics (the tour, slide 29) show that for Sep, 2007 Google performed 2,200,000 jobs in average 6.5 minute completion time using average 400 worker machines.

The good news is that you can clone Google architecture using an open source software called Hadoop: "a free Java software framework that supports data intensive distributed applications running on large clusters of commodity computers.^[1] It enables applications to work with thousands of nodes and petabytes of data. Hadoop was inspired by Google's MapReduce and Google File System (GFS) papers." (from Wikipedia). Hadoop has been deployed in many big Web companies like: Yahoo, Facebook, Amazon ...

The bad news is that if you are a student, surely you don't have enough money to buy hundred machines to deploy a MapReduce system (let say each machine cost about $500 USD, 400 machines will cost $200,000 USD - not including setup and maintenance fee :(

Here come a rescuer, GPU (Graphic Processing Unit) as massive parallel processors for scalable high-performance computing (HPC) at very cheap price. CUDA is one of the first and most comprehensive platform (an overview here, more details here). What I mean about cheap is that with about 200 USD (at Aug, 2008) you can by a Nvidia 8800 GTX Card with 128 Stream Processors, 512MB DDR3 to play with parallel programming yourself.

Actually there is a lot of different between MapReduce and CUDA programming models. But I don't see they compete each others. Instead, they complement each others. I think that Hadoop+Cuda combination will give a lot of powerful for individual to utilize the most computing power giving best performance / cost ratio that current hardware industry can offer. It's also a good practice to prepare for "the next milestone in computing in history". Welcome to the world of parallel computing.

As a programmer you may say "I don't care. I still coding-for-food with my sequential programming techniques. My programs run very fast on latest CPU. That's all my IT company need."

Well well well, here is the point. Now a day, the Moore law is not correct. Since 2002,processor performance has improved less than 20% per year [link]. Then multiple-core processors appeared. The hardware industry started switch from single CPU to multiple core processors. Now you can buy a quad-core Intel processor at around $1000 USD. Intel also plans 32-Core Processor by 2009/2010. And then ADM also have it's own a lot of core processor plan :). Now I can see that you starting feel nervous. Of course, if your program can run in one core only and other programmer (who learn about parallel programming techniques) can run a new program with the same logic but can run in 32 cores. It means that your program will be 30 times slower than the new program. If you are a user, which program you want to use? If you a CEO who run an IT company, which program you want to hire?

I believe that in 2010 the will be a huge demand for parallel programming jobs just to utilize new parallel processor architecture to improve existing and develop new programs as fast as possible. From now, you have 16 months to learn about parallel programming. You should be hurry :))

Now I tell you that I'm in the same situation with you. I know almost nothing about parallel programming. Because universities don't offer me parallel programming courses, and jobs don't demand me for parallel programming techniques. But I will prepare myself for a near future where every desktop computers will have 32 (64, 128 or even 256) cores, and GPUs with computing power of thousand's GFLOPS (imagine that a near future desktop will be as powerful as 400 worker machines in above Google MapReduce jobs examples). In that concurrency world, the ones who master parallel programming techniques can write fastest programs, again "speed is king" :)

And please remember that "The world is concurrency, the applications are concurrency, and hardware is concurrency also". Programming need to catch up.

Note:
Google bought PeakStream (a GPU and multi-core computing solution startup)in middle of 2007. I don't know what Google going to do with PeakStream. Guest that they will use it to solve biology problems or build the next generation server farm.