Do you have a phone interview with Google on the schedule? Or any software engineering job interview for that matter? If so, then congratulations! You've made the most important step of getting your foot in the door. Now let's make sure we don't squander this opportunity.
As with any worthwhile ventures in life, proper mental preparation can often mean the difference between success and failure. It is imperative that you allocate enough time in your busy (or not so busy) schedule to properly review for this endeavor. In my experience, it's best to spend at least a week to prepare. Most will often spend several weeks to a month, and I know of some who have spent several months studying. It also depends largely on how many hours you can put in per day. I personally only had a few days to prepare and ended up having to study for 14-18 hours each day. Everyone is different but when time is of the essence, remember: A little bit of something is still better than nothing!
While I cannot comment on the best preparation strategies; I can, however, describe how I got ready for my phone interview and layout the different materials that I chose to cover. Hopefully the resources that I list here will give you a head start in your own preparation process. Some of the materials are specific to my interview process, but most are general and apply to all software development positions.
If you really have no time to prepare, however, it might be wise to reschedule your interview for a later date. In most cases, your interviewers should be more than willing to accommodate for your needs. You should never go into an interview feeling unprepared.
Now here we go, in no particular order ...
First and foremost, you will need to know how to code (well, duh)! The first thing I did, per strong recommendation from the recruiter, was looking up the book [Programming Interviews Exposed: Secrets to Landing Your Next Job], by John Mongan, Noah Kindler, and Eric Giguère. I must say, it was a fantastic read and I highly recommend the book myself. By the way, in most cases, your recruiter's only job is to get you hired, so use that to your advantage! Pick their brains for anything of use, such as what to study.
Asides from reading the book, I also aggressively reviewed my primary programming language. The language of choice for my interview was Java so naturally I Googled for "advanced Java tutorials." If you're already a seasoned developer, then you might decide to skip this step. If you're someone like me who constantly switches between multiple different languages, then a refresher course should definitely be on your queue. Remember, during the phone interview you will need to program in a Google doc, without the aid of an IDE! Here are some Java tutorials that I found to be useful:
Time permitted, you should also consider opening up a good Java programming cookbook, like [this one]. There are C/C++, C#, Python, Perl, and many other variations as well. I didn't have time for this myself, but it's a good idea nonetheless.
Know thy Big-O's! Or at the very least, know what it means and know how to analyze an algorithm for the time and space complexity. Although in academia you may have focused more on time complexity, often at the cost of space complexity, I would imagine that at Google one cannot afford to overlook space efficiency, especially when dealing with millions or billions of data points. I can almost guarantee that your chance of getting hired is slim to none if you don't know about Big-O. So here are some good resources that helped me:
Related to algorithm complexities, I think it's also important to know about complexity classes. In my humbling opinions, all interviewing computer scientists should be expected to know about NP-completeness and its implications. If you don't know or could use a reminder on the topic, Wikipedia has you covered [here]. Additionally, it is practical to know about common/popular NP-complete and NP-hard problems, see this [list].
Hold up, pop quiz: What is the difference between NP-hard and NP-complete anyway?
There are other complexity classes as well. Though unless you're specifically interviewing for a position that deals with advanced algorithms, I think it is sufficient to know about what they are and not their details (or at least I hope that is the case for my interview). For the curious minds though, here is another good read on [NP-completeness].
Finally, you will want to look at some example algorithm problems and tutorials. My recruiter suggested [topcoder]. These are certainly worth a look if you have time.
Sorting is one of the most fundamental problems in Computer Science, so you should know it by heart. One should understand why sorts like [bubble sort] and [insertion sort] are inefficient. Naturally, this means knowing about better sorting methods, such as [quicksort] or [merge sort] .
I found from experience that merge sort can be very useful in situations where quicksort is impractical. For example, here is a variation of a popular interview question that I've encountered:
Given a file with 1,000,000,000 random integers, sort the integers in ascending (or descending) order using only 1 MB of [runtime] memory space.Need help? Here's a [hint]. Feel free to share your solution below. If there are enough interests, I will consider posting my solution at a later time.
Lastly, did you know that in general no comparison sort algorithms can do better than O(n logn)? Why do you think that is?
Arguably, the single most used and important data structure in our toolbox. You should absolutely know how they work. My recruiter suggested that one should be able to implement a hash table using only arrays in the space of one interview. Clearly your implementation is not expected to be groundbreaking (though, it could be!), it should at least be functional.
To implement a hash table, you will need to understand how it works. Once again, Wikipedia knows best. Here's the [link]. If you're like me, you've likely learned about hash tables ages ago, so now is a good time to freshen your memory. If terms like load factor, item buckets, and hash collisions sound foreign to you, then it is time to hit the book. I personally had to review the different ways of handling hash collisions and how to keep the number of collisions low. More importantly, I needed to investigate how Java implemented its version of a hash table. On a related note, I also studied the different [hash functions].
Finally, does your language of choice support hash tables? A hash table is sometimes called a dictionary in some languages. If your primary programming language supports multiple implementations of a hash table, such as Java's Hashtable, HashMap, ConcurrentHashMap, TreeMap, and LinkedHashMap, then you should absolutely learn the differences between them.
The [book] I mentioned above has a very informative section on Trees, specifically binary trees. For more general information regarding trees, I once again suggest visiting the [Wikipedia's entry]. Here's another good introduction on [Trees] from a professor at CMU.
Random pop quiz #2: Do you still remember how to [rotate a tree]?
You should know the usefulness of a binary search tree (BST) and know that an unbalanced BST is about as efficient as a linked list (not very efficient at all!). So how can we keep a BST balanced? The recruiter recommended that I know about at least one [self-balancing BST]. I found the [splay tree] to be simplest to learn, but you may prefer the more popular [red-black tree].
Along with trees, graphs are the fundamental representation of many interesting problems. These problems are especially prevalent at Google. There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list) and you should know about all three, including their pros and cons. Here's a good review on [graph representations] (keep in mind that an adjacency list also uses objects and pointers).
Graphs are often traversed using breadth-first search (BFS) or depth-first search (DFS). If these don't sound familiar to you, then that's a very good indicator for what you need to study. Wikipedia does a decent job describing [graph traversals]. Here is a better [introduction]. Graph traversal algorithms are often used in graph searching problems. Of those, there are two common algorithms for finding the shortest path that you should know about: [Dijkstra] and [A*] (pronounces "A star"). I personally love A*; so simple and elegant, yet so powerful.
Here's a checkpoint, do you know the differences between in-order, pre-order, and post-order traversals? How about topological order? Personally, I had to review [Topological sorting] and I suggest that you do the same if needed. Topological ordering plays a crucial role in directed-acyclic graph (DAG) searching.
It's worth mentioning that there is a huge number of interesting graph problems out there! Knowing some of these may work to your advantages. I had the opportunity to take an advanced algorithms class last semester and learned a lot about graph theory and algorithms (and I loved it). These are purely for curiosity fulfillment, of course. Here is a good [list of graph problems] for those interested.
There are many other data structures out there that we have not mentioned. Some are common household names, such as the heap, queue, stack, list, and array, while others are lesser known but can be very useful under the right circumstances, such as the [skip-list], [trie], and [disjoint-set]. Here are some useful notes on [common data structures] from a distinguished professor at Stony Brook University, and here is a fun thread from stackoverflow.com about [lesser known data structures].
Though if you're pressed for time, please be selective about what to take on. Don't waste time, for example, studying the less mainstream data structures if you only have a few days to prepare.
Lastly, while reading up on different data structures. Make sure you pay close attention to their pros and cons, and know the complexities of their implementations. Most data structures are designed to optimize certain operations, often at the cost of others. It's hard to design a one-fit-all data structure.
It would be a good idea to know about [Operating Systems]. No, not how to use them, but how they work. Know the important parts of an OS, such as the [kernel], [file system], and the [scheduler]. Here is a very good set of slides on the topic of the [fundamentals of modern operating systems], from professor Lubomir Bic at the University of California Irvine.
Moreover, you will need to understand [processes] and [threads]. Speaking of which, do you know the distinction between a process and a thread?
The discussion of threading will undoubtedly raise the inherent issues of [concurrency]. You will need to know what they are, how they arise, and how to avoid them. Here are some good resources on concurrency:
You should also be aware of the fundamentals of "modern" concurrency constructs. Be able to program a simple multithreaded problem in your primary programming language. I found the following resources for Java: [Java concurrency constructs], [a unique take on Java concurrency], and [Java concurrency pitfalls].
It was emphasized to me that counting problems, probability problems, and other Discrete Math 101 problems are especially prevalent at Google, which means it is certainly a good idea to brush up on your math.
I think [combination] and [permutation] problems are quite popular since they are very relatable to coding problems. For example, you might be asked to find all [permutations of a string] - a classic permutation problem with many real-world applications.
In my line of research, statistics and probabilities are extremely important! Knowing basic statistics and probability theories will carry you far. Time permitted, you should fortify your statistics.
Lastly, if you have the time for it, here's a good site that covers various aspects of [discrete mathematics].
This section is more relevant to Google interviews. That said, as Google is often considered to be one of the leading figures in our field, I wouldn't be surprised to find other companies asking Google related questions in their interviews.
It is a good idea to familiarise yourself with the designs of Google systems. Acknowledge that a great amount of innovations on how to deal with big data have found its way out of Google's research labs. Here is a small sample of some important ones (as suggested by a Google recruiter):
If you find yourself wanting to know more about the works of the industry-leading giant, feel free to review some more [Google research publications]. Needless to say, these are especially important if you're applying for a research position.
Also, here's a list of available [Google products].
Finally, I think it's important to get plenty of practice answering interview questions. Experience is invaluable and practice makes perfect! You should spend any extra time going over example exercises. There are many resources available for you on the web. Here are a few good ones to get you started:
Also, don't pass up the chance to read experiences & guides shared by others who have gone through the process. Their insights could be the edge you need to get ahead of the competition.
And lastly, watch this pitch by Google:
That's about it for now. While the list of materials presented here may seem daunting at first, rest assured that with good time management and sufficient willpower, it can be done in a reasonable amount of time. Feel free to skip sections that don't apply to you. The bottom line is, start early and give yourself plenty of time to prepare. Proper preparation is the key to success.
Lastly, I wish you the best of luck on your venture.
Did you find my list of resources helpful or have you found some helpful links that I should include? Please leave a comment below and let me know about it.
Anh Tran 24 February 2014 Tucson, AZ
Tweet