- Dynamic Programming
- Super recursion (permutation, combination,...2^n, m^n, n!...etc. type of program. (NP hard, NP programs)
- Probability related programs
- Graphs: BFS/DFS are usually enough
- All basic data structures from Arrays/Lists to circular queues, BSTs, Hash tables, B-Trees, and Red-Black trees, and all basic algorithms like sorting, binary search, median,...
- Problem solving ability at a level similar to TopCoder Division 1, 250 points. If you can consistently solve these, then you are almost sure to get in with 2-weeks brush up.
- Review all old interview questions in Glassdoor to get a feel. If you can solve 95% of them at home (including coding them up quickly and testing them out in a debugger + editor setup), you are in good shape.
- Practice coding--write often and write a lot. If you can think of a solution, you should be able to code it easily...without much thought.
- Very good to have for design interview: distributed systems knowledge and practical experience.
- Good understanding of basic discrete math, computer architecture, basic math.
- Coursera courses and assignments give a lot of what you need to know.
- Note that all the above except the first 2 are useful in "real life" programming too!
Graph related question and super recursion
Design discussion involving a distributed system with writes/reads going on at different sites in parallel.
Array and Tree related questions
Designing a simple class to do something. Not hard, but not easy either. You need to know basic data structures very well to consider different designs and trade-offs.
Dynamic programming, Computer architecture and low level perf. enhancement question which requires knowledge of Trees, binary search, etc.
- Recursions
- Dynamic Programming
- Graphs
- Data Structures
- Problem-solving query test
- Array and Tree
- Computer architecture (binary search, low level enhancement...etc)
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.