You’ve probably heard stories about tough brainteaser questions asked by interviewers at Google. The now famous “shrunk to the size of a nickel and placed in a blender” question was featured in the film The Internship, a comedy in which Vince Vaughn and Owen Wilson interview at Google. That same summer there were a rash of news reports proclaiming that Google had decided such brainteaser questions were unreliable and would not be used anymore.
Guess what ? Google never asked brainteaser questions like that. It’s largely a myth. They have asked estimation questions such as “How many gas stations are there in Manhattan?” and will likely continue to ask such questions in the future. However, they don’t ask software engineer candidates estimation questions. The meat of a software interview is all about data structures, algorithms, design and coding. These topics should be interesting to anyone who expects to pull down a big Google software engineer salary.
Below is what to expect and how to prepare for an interview at Google or other top-notch technology firms like Microsoft, Amazon, Apple or Facebook. They all follow a similar process. In the interest of full disclosure, I’ve never worked for any of these companies but I have interviewed at a couple of them over the course of my career.
Long Term Preparation
So you’ve read about the Google pay scale and employee benefits and decided to join the team as a software engineer. Not so fast! The first thing you’ll need is a solid education in computer science. That could take four years or more. Technically speaking, you don’t need a degree to get a job at Google but you’ll have to demonstrate a profound understanding of computer science that normally comes from a university education. At a minimum, take a college level course on data structures and algorithms. The ideal candidate will have a Bachelor’s or Master’s degree in computer science.
The other thing you’ll need before contacting Google is fluency in one mainstream programming language, preferably C++ or Java. This falls under long term preparation because fluency is not something you can gain in a month. These are big languages and it takes a year or more of study and practice to really know one like the back of your hand. If you’re really comfortable with C or Python, that may be good enough. Check with your Google recruiter.
Human Resources Screening
The standard way to get your foot in the door is to apply online at Google Jobs for an opening that matches your skills and geographic preference. If they think your application deserves consideration, a recruiter will contact you to set up an initial telephone screening. The recruiter will call you and go over non-technical information like where the job is located and if you’re interested in living there. This is a really low stress interview. Unless you can’t communicate in English or admit that you lied on your resume, chances are that you’ll move on to the next interview.
The two things you should tell your recruiter are: 1. Which programming language you’re most fluent in (preferably C++ or Java); and 2. That you’ll need four weeks to prepare for the technical interview.
I know that four weeks sounds like a long time, especially when you need a job. Unless you just completed a data structures and algorithms course, you’ll need those four weeks to freshen up your skills. The reason to mention your favorite programming language now is so that the recruiter will line up an interviewer who also specializes in that language. Interviews go more smoothly when you both know the same language.
The next interview will probably also be on the telephone unless you happen to live near a Google office, even if it’s not the same one with the opening you applied for. You will talk to one engineer for about 45 minutes. Be prepared to write code in Google Docs (if on the phone) or on a whiteboard (if in person).
Preparing for the interview
You really need to study data structures and algorithms. My favorite book to prepare for coding interviews is The Algorithm Design Manual by Steven S. Skiena. Some prefer Introduction to Algorithms by Thomas H. Cormen et al. but you’ll burn up four weeks just getting through the whole thing. It isn’t necessary to memorize every data structure and every algorithm in the book. Instead, focus on your attention on the ones below.
Data Structures
Hash tables are your friends. With constant time insert and find, they can improve the efficiency of many algorithms that come up in interviews. You may be asked to write a hash function during your interview but not an entire hash table implementation. Just be sure to understand how hash tables work and what makes one hash function better than another.
Graphs should be your go-to data structure when faced with an unfamiliar problem. They can solve about half of all problems, even if it’s sub-optimal. Study the three ways to represent graphs and how to traverse them.
Binary trees are a popular interview topic. Again, know how to represent and traverse them. Become familiar with at least one type of balanced binary tree.
Another important data structure is the heap, especially as it applies to Dijkstra’s algorithm or sorting.
Algorithms
The most important skill for a technical interview is identifying a problem’s class in order to find a solution. For example, if you’re asked to minimize/maximize some function, they’re probably looking for a dynamic programming solution.
You must be able to determine algorithmic complexity using big-O notation. Whenever you propose a solution, you should be able to say whether it’s O(n), O(n*log(n)), etc.
Know how to code at least two O(n*log(n)) sorting algorithms, merge sort and another one of your choice. Merge sort is important because it’s external and can be applied in a variety of situations.
Miscellaneous
Besides data structures and algorithms, you may be asked about discrete math or operating systems issues. Probably the most common questions are about multi-threading, locks and deadlocks.
Practice
Once you’ve read up on data structures and algorithms, it’s time to practice coding. Find some actual interview questions either at Glassdoor (search for Interviews, Google) or in the book Cracking the Coding Interview by Gayle Laakmann McDowell.
Have a friend to ask you questions that you haven’t previously solved. Answer them by coding on a whiteboard and thinking out loud. Coding on a whiteboard is harder than on paper or in a text editor. If you can solve problems on a whiteboard, you can solve them anywhere. Most of us are not accustomed to thinking on our feet. This is an important skill for performing well on an interview and it only comes with practice.
Interview day
If you do well on the first technical interview, Google will bring you in for 4 or 5 more. This will essentially take all day and follow the same pattern: one on one interviews each lasting about 45 minutes.Tip: Bring at least two fine-tipped dry erase markers. The markers they have in the office are fat so you tend to run out of whiteboard real estate quickly. Having two allows you to color code diagrams and also provides a backup in case the first one dries out. Remember to start coding in the very upper left corner of the whiteboard.
When presented with a problem, ask clarifying questions. The problems are usually underspecified and the interviewer wants to see how you analyze them. If you jump in and start coding right away, that’s a red flag. They don’t want cowboy coders.
Think out loud and talk as you work, just like you did in practice. This will show the interviewer how you approach the problem and give him/her an opportunity to steer you in the right direction if you go off course.
Write real code in C++ or Java. Pseudocode is not encouraged unless you’re just sketching out an algorithm. If that’s the case, explain that you’ll replace the pseudocode with real code shortly.
Even if you know the most efficient solution, it may be better to start with a brute force solution. Then you can say how poor the algorithmic complexity is and refine it. Maybe even refine it twice. It will impress the interviewer if you can explain tradeoffs as you optimize an algorithm. You could also refine the code in other ways such as making it more robust or scaling better in memory. Ending up with a correct answer is nice but not necessary. How you approach the problem is more important.
Finally, hand simulate your code and look for bugs. Pretend that somebody else wrote it and asked you to help debug it. Consider boundary conditions such as negative numbers or null strings.