This is a non-exhaustive list of topics that may or may not be covered during your interviews. Its intent is to guide your study and preparation.
- How We Hire Google Careers
- How to get a job at Google, interview questions, hiring process by Don Dodge link
- How We Hire 4 min
- Example Coding Interview 24 min
- Recruiter Tips for Technical Interviews 31 min
The interviews focus on coding, data structures, algorithms, computer science theory, and systems design (systems design questions normally reserved for applicants with 5+ years of industry experience)
Likely additional topics include: hash tables, heaps, binary trees, linked lists, depth-first search, recursion (think CS 101 - concepts that everyone knows but doesn't always quickly come-to-mind). More information on Algorithms
Many questions are open-ended and are deliberately underspecified to see how you engage the problem. Verbalize your thought process as you work to understand, approach, and solve the problem. Interviewers want to see which areas you find most important to the problem's solution. Think about ways to improve the solution you'll present. In many cases, the first answer that springs to mind will need refining. Verbalize your initial thoughts to the question. Ask clarifying questions if you don’t understand the problem or need more information. As a rule: efficient solution > brute force solution
For in-depth study - 3 highly recommended reads from Sr. Engineers: (1) "Programming Interviews Exposed: Secrets to Landing Your Next Job" (2) Programming Pearls and (3) Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms
- Coding: construct / traverse data structures, implement system routines, distill large data sets to single values, transform one data set to another
- Algorithm Design / Analysis: big-O analysis, sorting and hashing, handling obscenely large amounts of data. Also see topics listed under 'Coding'
- System Design: features sets, interfaces, class hierarchies, designing a system under certain constraints, simplicity and robustness, trade-offs
- Open-Ended Discussion: biggest challenges faced, best/worst designs seen, performance analysis and optimization, testing, ideas for improving existing product
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
If you don’t understand something or are stuck, please question your interviewer and ask for clarification and/or a hint
When asked to provide a solution, first define and frame the problem as you see it
If you need to assume something, verbally check it's 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 they are just as interested in your thought process as the final solution
Finally, listen - don't miss a hint if your interviewer is trying to assist you
- Algorithm Complexity: Understand big-O complexity analysis and Big-O notations (aka - "the run time characteristic of an algorithm.") Working through practice problems is key
- Sorting: Know how to sort. Don't do bubble-sort. 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
- Hashtables: The single most important data structure. Be able to implement one using only arrays in your favorite language with time limitations
- Trees: Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Know 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: There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); know each representation and its pros & cons. Know the basic graph traversal algorithms: breadth-first search & depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code. Time permitting, study fancier algorithms such as Dijkstra and A*.
- Other Data Structures: Know as many other data structures and algorithms as possible. Start with the famous classes of NP-complete problems, such as traveling salesman and the knapsack problem. Must recognize them when an interviewer asks you them in disguise. Find out what NP-complete means
- Mathematics: Some interviewers ask basic discrete math questions. At Google we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. Know the essentials of combinatorics and probability. Be familiar with n-choose-k problems and their ilk – the more the better
- Operating Systems: Concepts to know: (1) processes, threads and concurrency issues. (2) locks, mutexes, semaphores, and monitors (3) deadlock & livelock and how to avoid them (4) resources processes needs, and thread needs, and how context switching works, and how it's initiated by the OS and underlying hardware (5) scheduling (6) multi-core: the fundamentals of "modern" concurrency constructs