Coding: You should know at least one programming language really well, preferably C++
, Java
, Python
, Go
,
or C
. You will be expected to know APIs
, Object Orientated Design
and Programming, how to test your code,
as well as come up with corner cases
and edge cases
for code. Note that we focus on conceptual
understanding rather than memorization.
Algorithms: Approach the problem with both bottom-up and top-down algorithms. You will be expected to
know the complexity of an algorithm and how you can improve/change it. Algorithms that are used to solve
Google problems include sorting
(plus searching
and binary search
), divide-and-conquer
, dynamic programming/memoization
, greediness
, recursion
or algorithms linked to a specific data structure. Know
Big-O
notations (e.g. run time) and be ready to discuss complex algorithms like Dijkstra
and A*
. We
recommend discussing or outlining the algorithm you have in mind before writing code.
Sorting: Be familiar with common sorting functions and on what kind of input data they efficient or not.
Think about efficiency means in terms of runtime and space used. For example, in exceptional cases
insertion-sort
or radix-sort
are much better than the generic QuickSort/MergeSort/HeapSort
answers.
Data Structures: You should study up on as many data structures as possible. Data structures most
frequently used are arrays, linked lists, stacks, queues, hash-sets, hash-maps, hash-tables, dictionary, trees
and binary trees, heaps and graphs. You should know the data structure inside out, and what algorithms
tend to go along with each data structure.
Mathematics: Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because counting problems, probability problems and other Discrete Math 101 situations surround us. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of elementary probability theory and combinatorics. You should be familiar with n-choose-k problems and their ilk.
Graphs: Consider if a problem can be applied with graph algorithms like distance, search, connectivity,
cycle-detection, etc. There are three basic ways to represent a graph in memory (objects and pointers,
matrix, and adjacency list) — familiarize yourself with each representation and its pros and 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.
Recursion: Many coding problems involve thinking recursively and potentially coding a recursive solution. Use recursion to find more elegant solutions to problems that can be solved iteratively.
Operating Systems: You should understand processes, threads, concurrency issues, locks, mutexes,
semaphores, monitors and how they all work. Understand deadlock
, livelock
and how to avoid them. Know
what resources a process needs and a thread needs. Understand how context switching works, how it's
initiated by the operating system and underlying hardware. Know a little about scheduling. We are rapidly
moving towards multi-core
, so know the fundamentals of "modern" concurrency constructs.
System Design: System design questions are used to assess a candidate's ability to combine knowledge,
theory, experience and judgement toward solving a real-world engineering problem. Sample topics include
features sets
, interfaces
, class hierarchies
, distributed systems
, designing a system under certain
constraints, simplicity, limitations, robustness and tradeoffs. You should also have an understanding of how
the internet actually works and be familiar with the various pieces (routers, domain name servers, load
balancers, firewalls, etc.). For information on system design, check out our research on distributed systems
and parallel computing.