My Google onsite interview

On July 2015, I received an email from a recruiter, asking whether I am interested in working at Google London. Without a doubt, I response to him showing my interest, Google has always been my favorite company. After few weeks, they have set up a phone interview with one Google engineer on August 2015.

Phone interview

Doing a lot of research before, I manage to answer almost all questions in this interview. The phone interview covered large range of topics, from algorithm, regex, network programming to bit manipulation, math calculation. The questions are simple, I understand that the phone interview’s purpose is mainly focus on finding a “red flag”, without trying too hard to see how good is your analytical thinking or system design. Obviously, those abilities will be tested more carefully in the onsite. A very logical decision from Google. I think Steve Yegge has explained well in his must-read article.

After one week, I received a call from my recruiter, telling me I have passed the interview, and I was invited to Google Sydney for onsite, as there is no development center in Singapore. Great! By reading tons of question and answer on Quora, I know Google will be very flexible in its timing, so I scheduled the interview two months forward, plenty of time to study, as well as prepare all necessary documents for my travel.

Preparation

There are two major topics that will be tested in the onsite, problem solving skill and system design. I used most of my time to prepare for system design questions, following guidelines in this amazing link. Wonderful stuff for to start.

Algorithm is my strong point, practicing algorithm for the pass 3 years, day by day, I am fairly confident about my skill. However, doing the question with similar difficulty and format, and practice to present your approach clearly is very important. I was focus on solving a lot of Topcoder problems 250 pt Div 1, which I believe have very similar difficulty level (of course, I know this by reading one Quora question).

Interviewing with your favorite company first is suicide, keeping that in mind, luckily, I got another onsite with Amazon right before Google onsite, fantastic, similar format, that would help me a lot.

Onsite

Finally, the day has come. After a long flight, six hours on the plane, I have arrived at Sydney’s airport. The weather in Sydney was beautiful, my friend there has walked me around to visit some famous places in this lovely harbor city. Nice experience, however, due to jet lag, and sleeping too much on the plane, as well as being both nervous and excited at the same time, I cannot sleep the day before the interview. Not a big deal, a cup of tea will solve the problem.

I arrived at Google office 10 minutes before the interview, and was welcomed warmly by the receptionist. He is a very polite and nice person, who gave me a cup of mint tea and even a cookie, extraordinary! … starting to love this place …

Few minutes later, a Google engineer guided me to the interview’s room. And the battle began…

• First interview

My first interview was conducted by a senior engineer, he asked me some warm up questions, and after the introduction, we started to tackle the first problem, which was also the only problem in this interview.

An algorithm problem, a string processing problem, and its difficulty was out of my expectation. That was my first feeling. Being interviewed at Amazon and various other companies, I have never seen this type of difficulty. After first few minutes becoming more and more nervous, without any sight of “A ha” moment,  I decided to explain and implement my brute force solution, an O(n ^ 3) solution.

This turned out to be a good decision, after I proposed my solution, the interviewer admitted that this was almost the best I can do, except some other optimizations, which would bring the solution from O (n ^ 3) to O(n ^2).

Being too nervous, and still try to looking for a smart solution, I was lost and needed a lot of hint from the interviewer to derive the optimal solution. Big mistake, I should be focus on my code, rather than a smart move to impress the interviewer, that is the first lesson. Try to optimize your code! Think ahead of the interviewer two or three steps, but not more than that!

The interview ended by a very tricky optimization that I hardly believe someone can come up within a short amount of time, but it turned out that actually, there were two people, arrived at that point. Hat off to them.

One more point to note is, my interviewer was so nice, I felt like I was working with him, not interviewed by him, this has helped me a lot to relieve my stress and focused on solving the problem without much worrying about my interview. Very nice Google!

• Second interview

My second interview was with two engineers, one was training to be interviewer, not so surprise, I have done so many research, thank again to Quora. This time, the question was another string processing problem.

Being a lot more confident after the first interview, I quickly figured out the optimal solution, an O(n) solution, then implemented it without any difficulties. The interview asking me some questions to clarify my choice of data structure, and I answered them flawlessly, he looked satisfied.

However, I was being so confident, that, I forgot the first lesson. I think this question was done, and stop thinking or trying to improve it. Another big mistake! I should have written the solution in a better way, or try to test it at least.

• Third interview

My third interview was with one young engineer. We began with a game theory questions. Tough one, I cannot think of any solution except brute force, I considered to use Nim, but after a while, I didn’t think it was applicable for this problem. Try not to make the same mistake as the first interview, I started to explain and implement the brute force solution with the interviewer, and also suggest few optimizations. He was satisfied with my solution, and we moved to the next question.

The second question was a two dimensional dynamic programming problem, tough to come up with a formula, but once you did, implementation is straight forward. I started with implementing the recursive formula, and also mentioned about the dynamic programming approach. Nailed it!

• Lunch time

One engineer took me to lunch, we had a nice lunch and chit chat a little bit about working environment and culture at Google, the food was surprisingly good, it made me feel sleepy also :))

• Fourth interview

Fourth interview was between me and two other engineers, one junior and one very senior. We started by doing some performance approximation calculations, bit and bytes, straight forward, but can cause a lot of problem if you don’t understand the underlying concept.

After that, the interview was focus on a simplify version of a real world problem. Tough, but within my reach. Coming up with an optimal solution, then focus on optimizing and reasoning about the choices, I was kind of used to the process. I think I have done well in this interview.

• Final interview

Finally, system design, I started to being nervous again. This type of interview can go from very abstract to very detail level, which focusing on testing your engineering sense. (Common sense and logical thinking)

It turned out that it was an interesting and relaxing interview, we discussed a lot of problems from designing overall architecture to addressing performance problem, from handling transferring message to storing data. Feeling like we were truly teammates, we have enjoyed the interview very much.

Result

One week later, my recruiter told me about the result, I have done well on last three interviews, but not so good on the first two. However, the overall feed back was positive, so she would submit it to the hiring committee.

I was happy, but also understood that my chance was not so high. Hiring an engineer with an over-the-fence interview performance, without any significant accomplishment or support from other employee, I think rejection was not an unexpected result. And I was right, I was rejected few days later.

Final thought

I had an amazing experience, Google is far more better than I was expected, I have met a lot of nice and cool people, and even though the result was not good, it cannot destroy the good feeling towards the company. I was working with extremely nice and friendly recruiter, who tried her best to help me through out the process, thank you so much!

Some lessons :

• Always start from the simplest solution, and try to improve it, don’t stop working and thinking to make the solution better and better.
• Every decision should be backed by good reasons.
• You need to understand your tool, pros and cons, don’t just use it, reason about it.
• The problem of competitive programming is, when you arrive at a working solution, you stop, but when interviewing, you need to come up with a perfect solution.

Update:

Useful links

https://github.com/vasanthk/how-web-works#googles-g-key-is-pressed

https://www.ntu.edu.sg/home/ehchua/programming/webprogramming/HTTP_Basics.html

https://www.interviewbit.com/problems/tiny-url/#_=_

https://www.educative.io/collection/5668639101419520/5649050225344512

https://www.hiredintech.com/system-design

https://tianpan.co/hacking-the-software-engineer-interview/?isAdmin=true

https://github.com/donnemartin/system-design-primer#system-design-interview-questions-with-solutions

https://crackstation.net/hashing-security.htm#properhashing

https://aws.amazon.com/architecture/well-architected/

https://github.com/mister0/How-to-prepare-for-google-interview-SWE-SRE