Google Interview Study Guide

gistfile1.txt

Author unknown.

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:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

2.) 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.
*Strongly recommended* for information on Coding: Programming
Interviews Exposed; Secrets to landing your next job by John Monagan
and Noah Suojanen (Wiley Computer Publishing)
http://www.wiley.com/WileyCDA/WileyTitle/productCd-047012167X.html

3.) System Design:
http://research.google.com/pubs/DistributedSystemsandParallelComputing.html
Google File System (http://labs.google.com/papers/gfs.html)
Google Bigtable (http://labs.google.com/papers/bigtable.html)
Google MapReduce (http://labs.google.com/papers/mapreduce.html)

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
(say, quicksort and 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 and
manipulation algorithms. Familiarize 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.

7.) 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*.

8.) 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.

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, 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.

10.) 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.