What's a Google Interview Invitation Email Like?
Interview instructions from Google Careers
AREAS TO PREPARE, DIRECTLY FROM OUR ENGINEERS:
1) Algorithm Complexity: You need to know Big-O. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. For more information on Algorithms you can visit this link.
We also highly recommend that you get comfortable answering problems similar to those available on www.TopCoder.com.
2) Coding: You will be expected to write some code in at least some of your interviews. You should know at least one programming language really well (preferably be C++, C, Java or Python, though C# is OK too, since it's pretty similar to Java). You will be expected to know a fair amount of detail about your favorite programming language. Strongly recommended for information on Coding: Programming Interviews Exposed; Secrets to Landing Your Next Job by John Monagan & Noah Suojanen.
3) System Design: Check our basic system design here. Also check out: Google File System, Google Bigtable, & Google MapReduce.
4) 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 (e.g., quicksort & merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.
5) Hashtables: Arguably the single most important data structure known to mankind. You absolutely should know how they work. Be able to implement one using only arrays in your favorite language, in about the space of one interview.
6) Trees: Know about trees; basic tree construction, traversal & manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, & 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, & know how it's implemented. Understand tree traversal algorithms: BFS & DFS, & know the difference between inorder, postorder, & preorder.
7) Graphs: Graphs are really important at Google. There are 3 basic ways to represent a graph in memory (objects & pointers, matrix, & adjacency list); familiarize yourself with each representation & its pros & cons. You should know the basic graph traversal algorithms: breadth-first search & depth-first search. Know their computational complexity, their tradeoffs, & how to implement them in real code. If you get a chance, try to study up on fancier algorithms, such as Dijkstra & A*.
8) Other Data Structures: You should study up on as many other data structures & algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman & the knapsack problem, & be able to recognize them when an interviewer asks you them in disguise. Find out what NP-complete means.
9) 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, & other Discrete Math 101 situations. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics & probability. You should be familiar with n-choose-k problems & their ilk – the more the better.
10) Operating Systems: Know about processes, threads & concurrency issues. Know about locks & mutexes & semaphores & monitors & how they work. Know about deadlock & livelock & how to avoid them. Know what resources a processes needs, & a thread needs, & how context switching works, & how it's initiated by the operating system & underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.
11) Research Publications: Check out Google's publications here & paper on Google’s Hybrid Approach to Research.
HELPFUL LINKS:
Five Essential Phone Screen Questions
Nice summary, but next to useless. I remember years ago when I did talk to them, I queried why I was not asked anything of C++ or other primary skills (which is why you think is why they were interested in the first place) - the answer would surprise (even to this day) - because it was determined I would likely know all of the answers put to me. Rather, they want to know what you do not know, and seen that pattern repeat many times over. Frankly, I'm only interested in contributing to where I can add value, not the other way around. They are good at researching problems, but poor in engineering solutions. They are after scientists as opposed to engineers is the key realization. 10 years on, and I refuse to interview with them again, for this and many other reasons.