Noogler's Secret


From: secret sender < secretemail@google.com>
Date: xx februari 2011 xx.42.xx CET
Subject: Additional interview preparatory information

Hi Aidi,

We usually send this info to engineers interviewing for xx roles at Google--but I thought you might find it helpful as well!

Software engineering roles at Google are quite unique. You may be currently architecting, analysing, researching, or coding but here, engineers handle the full cycle; system architecture, design, coding and testing, without any hierarchy, in an Agile environment.

"Design" tends to be one short piece of paper and 5 engineers agreeing to develop a prototype. If it works, they ship it in "beta" or on Google Labs, often having 100's of 1,000's of users in a matter of hours, then they iterate and see where they can take it. Often, if other engineers like the project, they use their 20% time to help out, so you can have specialist engineers across the globe meshing together. Its confusing, complex, challenging...and a lot of fun.

The emphasis is on the software engineers to design & develop cool, simple, user friendly (globally scalable) products, so Google doesn't need to market them or provide sales support. If applications are popular, we monetise them - but only then.

"Engineering" tends to have more prestige than "management" (as many people can be taught to manage - even me! but only the select few can call themselves "legendary coders" or "globally renowned engineers") and so Google engineers are recompensed to reflect their world class skills/contributions, rather than how many people they manage.

Usually you would start here as an engineer (there are engineers at every level) and once you comprehend how Google operates, then you can naturally start leading projects and then teams. Many of the engineers want to progress their career without focussing on people management; eg. http://research.google.com/people/jeff/index.html

Even at Director level, Google seeks technical candidates with awesome, hands-on Computer Science fundamentals - every engineer who has access to the Google code base needs to have a really solid CS foundation. They don't use pre-coded solutions or architectures (so we don't use any MFC, .NET or J2EE) - everything is created from scratch (including internal systems - everything!). Its not about delivery speed or commercial return - but rather quality of code and efficiency of design.

Tips on how to prepare for a phone interview at Google:

The interviewers are keen to assess your ability to development original software in a fairly short period of time.

Interview topics may cover anything on your CV (especially if you have stated that you are an expert!), building and developing complex algorithms and analyzing their performance characteristics, logic problems, systems design and fundamental computer science principles - hash tables, stacks, arrays, data-structures, object-oriented programming skills, algorithms, etc. and how they can be used in your solution.

For instance, he/she may set a deliberately ambiguous real-world problem and ask you to find solutions to it. You'll need to interpret the coding knowledge that you have for that particular situation. They are looking for process of thought, creative solutions and being able to work out more than one way to solve a problem and talk through your rationale for choosing a certain way to approach solving the problem. So, you could perhaps recommend an algorithm, code up a solution using that algorithm, analyze the runtime of your code and then optimize your solution.

Software engineers at Google each handle all aspects of system architecture, design, coding and testing, developing original software products and applications with a global scale, without job hierarchy. Therefore, computer science fundamentals are pre-requisite for all engineering roles at Google, regardless of seniority, due to the complexities and massive scale of the projects you would end up participating in.

Tips on how to succeed:

At Google, we believe in collaboration and sharing ideas. Most importantly, you'll need more information from the interviewer to analyze & answer the question to its full extent.

* Its OK to question your interviewer.
* When asked to provide a solution, first define and framework the problem as you see it.
* If you don't understand - ask for help or clarification.
* If you need to assume something - verbally check its a correct assumption!
* Describe how you want to tackle solving each part of the question.
* Always let your interviewer know what you are thinking as he/she will be as interested in your process of thought as your solution. Also, if you're stuck, they may provide hints if they know what you're doing.
* Finally, listen - don't miss a hint if your interviewer is trying to assist you!

What is Google looking for?:

"We are not simply looking for engineers to solve the problems they already know the answers to; we are interested in engineers who can work out the answers to questions they have not come across before."

Interviewers will be looking at the approach to questions as much as the answer -

* Does the candidate listen carefully and comprehend the question?
* Are the correct questions asked before proceeding? (important!)
* Is brute force used to solve a problem? (not good!)
* Are things assumed without first checking? (not good!)
* Are hints heard and heeded?
* Is the candidate slow to comprehend / solve problems? (not good!)
* Does the candidate enjoy finding multiple solutions before choosing the best one?
* Are new ideas and methods of tackling a problem sought?
* Is the candidate inventive and flexible in their solutions and open to new ideas?
* Can questioning move up to more complex problem solving?

Google is keen to see really high quality, efficient, clear code without typing mistakes. Because all engineers (at every level) collaborate globally throughout the Google code base, with an efficient code review process, its essential that every engineer works at the same high standard.

Ask more questions!:

Make sure you have a decent understanding of Google as a business - further than Google's main products - find out about what we do here: http://www.google.com/corporate/ OR: http://en.wikipedia.org/wiki/Google
At the end of the interview, most interviewers will ask you if you have any questions about the company, work environment, their experience, etc. Its clever to have some pre-prepared for each interview, but don't worry too much if your mind goes blank.
If you have questions about the interview process, remuneration or your performance, please direct these to your recruiter.

Interesting further reading:

* The Google Zurich office experience! http://news.bbc.co.uk/1/hi/technology/7290322.stm
* Videos about our technologies: http://research.google.com/video.html
* Research Papers written by Google engineers: http://research.google.com/pubs/papers.html
* To understand how Google's development teams work - http://en.wikipedia.org/wiki/Agile_development
* To know more about Google's core projects - http://labs.google.com/why-google.html
* If you have not already read through Steve Yegge's technical prep tips, please check out his blog - http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html
* Due to the size of the products you'll be building, its imperative you're comfortable with big O notation, here's where to brush up - http://en.wikipedia.org/wiki/Big_o_notation
* Tips to interviewing at Google: http://www.youtube.com/watch?v=w887NIa_V9w
* The Algorithm Design Manual - A lot you'd want to know about designing and implementing lots of fundamental aglorithms Structure and Interpretation of Computer Programs - http://mitpress.mit.edu/sicp/full-text/book/book.html (esp. Pragmatic Unit Testing, Effective Java, Code Complete 2, Agile Estimation and Planning).

Technical Preparation tips!:
The main areas software engineers should prepare to succeed at interview at Google:

Algorithm Complexity:  You need to know Big-O - basic big-O complexity analysis

Sorting:  Know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

Hashtables:  You should know how they work. Be able to implement one using only arrays in your favorite language, in about the space of one interview.

Trees:  Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarise yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and know how it's implemented. Understand tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.

Graphs:  Graphs are really important at Google. There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); familiarize yourself with each representation and its pros & cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code. If you get a chance, try to study up on fancier algorithms, such as Dijkstra and A*.

Other data structures:  You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. Find out what NP-complete means.

Mathematics:  Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.

Operating Systems:  Know about processes, threads and concurrency issues. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.

Coding:  You should know at least one programming language really well, and it should preferably be C++ or Java. C# is OK too, since it's pretty similar to Java. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language.

To practice for your interview you may want to;

Visit the website www.topcoder.com - if you launch the "Arena" widget and then go to the practice rooms where you can play with the problems in the first/second division as a warm up.
OR
This is a useful site for practicing coding which is not competitive and doesn't require that you download additional apps: http://projecteuler.net/
OR
Play around with Google's APIs: http://code.google.com/


Please let me know if you have any questions.
Secret sender
People Operations
Google xxx
Secret Street