Technical revision topics...
Here is a list of topics about which interviewers may ask questions. They won’t all come up, but it’s a good idea to review them before your interview.Algorithm Complexity:
Review Big-O notation. That stuff is useful every time we write an algorithm at Google, so it’s great when candidates understand it!
Sorting:
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.
Hashtables:
Familiarise yourself with this very useful data structure! Consider when and why you might use a hash table as well as how they work.
Trees:
Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarise 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.
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, interviewers will be really impressed if you can discuss fancier algorithms, such as Dijkstra and A*.
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.
Mathematics:
You shouldn’t need to explicitly study any mathematical topics, but you should know powers of 2 (even if you can’t remember which one is peta- and which one is exa-), and be able to do back-of-the-envelope calculations e.g. to estimate the required number of machines for a given design. You should have a basic knowledge of logic and probability.
Systems Design:
Know Google's products, and think about how you would design the back-end (of front-end). System design questions are a test of your problem solving. Sample topics include: features sets, interfaces, class hierarchies, distributed systems, designing a system under certain constraints, simplicity and robustness, tradeoffs.
Distributed Systems and Cloud Computing:
Many systems design questions involve a distributed design. You won’t need to know the finer details of networking and data marshalling algorithms in use today (although of course it won’t hurt if you do!) but you may be asked to come up with a design that spans multiple machines. Be able to judge the execution cost and latency of different parts of system such as memory, disk, local networks and wide-area networks. Think about how data is shared between machines. You should also have a rough understanding of how the World Wide Web works, starting at the browser and ending at the server in the data centre, and all the bits in between.
Coding:
You should know at least one programming language well, and it should preferably be C++, Python or Java. C# is OK too, since it's pretty similar to Java. You will be expected to write code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language and also be expected to produce code on a whiteboard - although you won’t be expected to know all of the standard libraries off by heart!
Classic CS problems
Towers of Hanoi - Write a recursive program to solve this problem. What is the complexity?
Shortest path problem - Write an algorithm to plan a route by minimising distance or time.
Traveling salesman problem - Write an algorithm to determine the least cost round-trip, given multiple cities and varying costs of flights.
Knapsack problem - Write an algorithm to optimize the value of items you can fit into a backpack based on weight and volume.
Sample questions from Programming Pearls
- Given a file containing at most ten million 7-digit integers with no duplicates. What is an efficient way to print these numbers in ascending order using just 1.5Mb RAM and reading the data just once? What are the consequences of only having 1Mb of RAM and no other storage? How would your answer change if duplicates were permitted?
- Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn’t in the file (and there must be at least one missing...why?). How would you solve this with unlimited main memory? How would you solve it if you could use several external files but only a few bytes of main memory?
- Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 andi=3, the vector abcdefgh is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?
- Given a dictionary of English words, find sets of anagrams. For instance, “pots”, “stop”, and “tops” are all anagrams of one another because each can be found by permuting the letters of the others.
- Write functions for the following date problems: given two dates, compute the number of days between them; given a date, return it’s day of the week; given a month and year, produce a calendar of the month as an array of characters
- Given a very long sequence (say, billions or trillions) of bytes, how would you efficiently count the total number of one bits? (i.e. how many bits are turned on in the entire sequence)
- Although Quicksort uses only O(logn) stack space on the average, it can use linear space in the worst case. Explain why, then modify the program to use only logarithmic space in the worst case.
- Write a program for finding the kth-smallest element in the array x[0...n-1] in O(n) expected time. Your algorithm may permute the elements of x.
- Build the fastest possible complete function to generate a sorted array of random integers without duplicates. (You need feel constrained to use any prescribed interface for set representation)
- Implement heap-based priority queues to run as quickly as possible; at what values of n are they faster than sequential structures
To practice for your interview you might find these resources useful:
- Wikipedia (http://en.wikipedia.org) has good articles on many computing topics, if you just need a refresher on something. Some good starting points:
- Project Euler (http://projecteuler.net/) has a large set of mathematical and other coding puzzles which you may find useful to practice with.
