I've been meaning to write up some tips on interviewing at Google for a good long time now. I keep putting it off, though, because it's going to make you mad. Probably. For some statistical definition of "you", it's very likely to upset you.
Why? Because... well, here, I wrote a little ditty about it:
Hey man, I don't know that stuff
Stevey's talking aboooooout
If my boss thinks it's important
I'm gonna get fiiiiiiiiiired
Oooh yeah baaaby baaaay-beeeeee....
I didn't realize this was such a typical reaction back when I first started writing about interviewing, way back at other companies. Boy-o-howdy did I find out in a hurry.
See, it goes like this:
Me: blah blah blah, I like asking question X in interviews, blah blah blah...
You: Question X? Oh man, I haven't heard about X since college! I've never needed it for my job! He asks that in interviews? But that means someone out there thinks it's important to know, and, and... I don't know it! If they detect my ignorance, not only will I be summarily fired for incompetence without so much as a thank-you, I will also be unemployable by people who ask question X! If people listen to Stevey, that will be everyone! I will become homeless and destitute! For not knowing something I've never needed before! This is horrible! I would attack X itself, except that I do not want to pick up a book and figure enough out about it to discredit it. Clearly I must yell a lot about how stupid Stevey is so that nobody will listen to him!
Me: So in conclusion, blah blah... huh? Did you say "fired"? "Destitute?" What are you talking about?
You: Aaaaaaauuuggh!!! *stab* *stab* *stab*
Me: That's it. I'm never talking about interviewing again.
It doesn't matter what X is, either. It's arbitrary. I could say: "I really enjoy asking the candidate (their name) in interviews", and people would still freak out, on account of insecurity about either interviewing in general or their knowledge of their own name, hopefully the former.
But THEN, time passes, and interview candidates come and go, and we always wind up saying: "Gosh, we sure wish that obviously smart person had prepared a little better for his or her interviews. Is there any way we can help future candidates out with some tips?"
And then nobody actually does anything, because we're all afraid of getting stabbed violently by People Who Don't Know X.
I considered giving out a set of tips in which I actually use variable names like X, rather than real subjects, but decided that in the resultant vacuum, everyone would get upset. Otherwise that approach seemed pretty good, as long as I published under a pseudonym.
In the end, people really need the tips, regardless of how many feelings get hurt along the way. So rather than skirt around the issues, I'm going to give you a few mandatory substitutions for X along with a fair amount of general interview-prep information.
Caveats and Disclaimers
This blog is not endorsed by Google. Google doesn't know I'm publishing these tips. It's just between you and me, OK? Don't tell them I prepped you. Just go kick ass on your interviews and we'll be square.
I'm only talking about general software engineering positions, and interviews for those positions.
These tips are actually generic; there's nothing specific to Google vs. any other software company. I could have been writing these tips about my first software job 20 years ago. That implies that these tips are also timeless, at least for the span of our careers.
These tips obviously won't get you a job on their own. My hope is that by following them you will perform your very best during the interviews.
Oh, and um, why Google?
Oho! Why Google, you ask? Well let's just have that dialog right up front, shall we?
You: Should I work at Google? Is it all they say it is, and more? Will I be serenely happy there? Should I apply immediately?
Me: Yes.
You: To which ques... wait, what do you mean by "Yes?" I didn't even say who I am!
Me: Dude, the answer is Yes. (You may be a woman, but I'm still calling you Dude.)
You: But... but... I am paralyzed by inertia! And I feel a certain comfort level at my current company, or at least I have become relatively inured to the discomfort. I know people here and nobody at Google! I would have to learn Google's build system and technology and stuff! I have no credibility, no reputation there – I would have to start over virtually from scratch! I waited too long, there's no upside! I'm afraaaaaaid!
Me: DUDE. The answer is Yes already, OK? It's an invariant. Everyone else who came to Google was in the exact same position as you are, modulo a handful of famous people with beards that put Gandalf's to shame, but they're a very tiny minority. Everyone who applied had the same reasons for not applying as you do. And everyone here says: "GOSH, I SURE AM HAPPY I CAME HERE!" So just apply already. But prep first.
You: But what if I get a mistrial? I might be smart and qualified, but for some random reason I may do poorly in the interviews and not get an offer! That would be a huge blow to my ego! I would rather pass up the opportunity altogether than have a chance of failure!
Me: Yeah, that's at least partly true. Heck, I kinda didn't make it in on my first attempt, but I begged like a street dog until they gave me a second round of interviews. I caught them in a weak moment. And the second time around, I prepared, and did much better.
The thing is, Google has a well-known false negative rate, which means we sometimes turn away qualified people, because that's considered better than sometimes hiring unqualified people. This is actually an industry-wide thing, but the dial gets turned differently at different companies. At Google the false-negative rate is pretty high. I don't know what it is, but I do know a lot of smart, qualified people who've not made it through our interviews. It's a bummer.
But the really important takeaway is this: if you don't get an offer, you may still be qualified to work here. So it needn't be a blow to your ego at all!
As far as anyone I know can tell, false negatives are completely random, and are unrelated to your skills or qualifications. They can happen from a variety of factors, including but not limited to:
- you're having an off day
- one or more of your interviewers is having an off day
- there were communication issues invisible to you and/or one or more of the interviewers
- you got unlucky and got an Interview Anti-Loop
Yes, I'm afraid you have to worry about this.
What is it, you ask? Well, back when I was at Amazon, we did (and they undoubtedly still do) a LOT of soul-searching about this exact problem. We eventually concluded that every single employee E at Amazon has at least one "Interview Anti-Loop": a set of other employees S who would not hire E. The root cause is important for you to understand when you're going into interviews, so I'll tell you a little about what I've found over the years.
First, you can't tell interviewers what's important. Not at any company. Not unless they're specifically asking you for advice. You have a very narrow window of perhaps one year after an engineer graduates from college to inculcate them in the art of interviewing, after which the window closes and they believe they are a "good interviewer" and they don't need to change their questions, their question styles, their interviewing style, or their feedback style, ever again.
It's a problem. But I've had my hand bitten enough times that I just don't try anymore.
Second problem: every "experienced" interviewer has a set of pet subjects and possibly specific questions that he or she feels is an accurate gauge of a candidate's abilities. The question sets for any two interviewers can be widely different and even entirely non-overlapping.
A classic example found everywhere is: Interviewer A always asks about C++ trivia, filesystems, network protocols and discrete math. Interviewer B always asks about Java trivia, design patterns, unit testing, web frameworks, and software project management. For any given candidate with both A and B on the interview loop, A and B are likely to give very different votes. A and B would probably not even hire each other, given a chance, but they both happened to go through interviewer C, who asked them both about data structures, unix utilities, and processes versus threads, and A and B both happened to squeak by.
That's almost always what happens when you get an offer from a tech company. You just happened to squeak by. Because of the inherently flawed nature of the interviewing process, it's highly likely that someone on the loop will be unimpressed with you, even if you are Alan Turing. Especially if you're Alan Turing, in fact, since it means you obviously don't know C++.
The bottom line is, if you go to an interview at any software company, you should plan for the contingency that you might get genuinely unlucky, and wind up with one or more people from your Interview Anti-Loop on your interview loop. If this happens, you will struggle, then be told that you were not a fit at this time, and then you will feel bad. Just as long as you don't feel meta-bad, everything is OK. You should feel good that you feel bad after this happens, because hey, it means you're human.
And then you should wait 6-12 months and re-apply. That's pretty much the best solution we (or anyone else I know of) could come up with for the false-negative problem. We wipe the slate clean and start over again. There are lots of people here who got in on their second or third attempt, and they're kicking butt.
You can too.
OK, I feel better about potentially not getting hired
Good! So let's get on to those tips, then.
If you've been following along very closely, you'll have realized that I'm interviewer D. Meaning that my personal set of pet questions and topics is just my own, and it's no better or worse than anyone else's. So I can't tell you what it is, no matter how much I'd like to, because I'll offend interviewers A through X who have slightly different working sets.
Instead, I want to prep you for some general topics that I believe are shared by the majority of tech interviewers at Google-like companies. Roughly speaking, this means the company builds a lot of their own software and does a lot of distributed computing. There are other tech-company footprints, the opposite end of the spectrum being companies that outsource everything to consultants and try to use as much third-party software as possible. My tips will be useful only to the extent that the company resembles Google.
So you might as well make it Google, eh?
First, let's talk about non-technical prep.
The Warm-Up
Nobody goes into a boxing match cold. Lesson: you should bring your boxing gloves to the interview. No, wait, sorry, I mean: warm up beforehand!
How do you warm up? Basically there is short-term and long-term warming up, and you should do both.
Long-term warming up means: study and practice for a week or two before the interview. You want your mind to be in the general "mode" of problem solving on whiteboards. If you can do it on a whiteboard, every other medium (laptop, shared network document, whatever) is a cakewalk. So plan for the whiteboard.
Short-term warming up means: get lots of rest the night before, and then do intense, fast-paced warm-ups the morning of the interview.
The two best long-term warm-ups I know of are:
1) Study a data-structures and algorithms book. Why? Because it is the most likely to help you beef up on problem identification. Many interviewers are happy when you understand the broad class of question they're asking without explanation. For instance, if they ask you about coloring U.S. states in different colors, you get major bonus points if you recognize it as a graph-coloring problem, even if you don't actually remember exactly how graph-coloring works.
And if you do remember how it works, then you can probably whip through the answer pretty quickly. So your best bet, interview-prep wise, is to practice the art of recognizing that certain problem classes are best solved with certain algorithms and data structures.
My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are – they should be part of every working programmer's toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types.
Other interviewers I know recommend Introduction to Algorithms. It's a true classic and an invaluable resource, but it will probably take you more than 2 weeks to get through it. But if you want to come into your interviews prepped, then consider deferring your application until you've made your way through that book.
2) Have a friend interview you. The friend should ask you a random interview question, and you should go write it on the board. You should keep going until it is complete, no matter how tired or lazy you feel. Do this as much as you can possibly tolerate.
I didn't do these two types of preparation before my first Google interview, and I was absolutely shocked at how bad at whiteboard coding I had become since I had last interviewed seven years prior. It's hard! And I also had forgotten a bunch of algorithms and data structures that I used to know, or at least had heard of.
Going through these exercises for a week prepped me mightily for my second round of Google interviews, and I did way, way better. It made all the difference.
As for short-term preparation, all you can really do is make sure you are as alert and warmed up as possible. Don't go in cold. Solve a few problems and read through your study books. Drink some coffee: it actually helps you think faster, believe it or not. Make sure you spend at least an hour practicing immediately before you walk into the interview. Treat it like a sports game or a music recital, or heck, an exam: if you go in warmed up you'll give your best performance.
Mental Prep
So! You're a hotshot programmer with a long list of accomplishments. Time to forget about all that and focus on interview survival.
You should go in humble, open-minded, and focused.
If you come across as arrogant, then people will question whether they want to work with you. The best way to appear arrogant is to question the validity of the interviewer's question – it really ticks them off, as I pointed out earlier on. Remember how I said you can't tell an interviewer how to interview? Well, that's especially true if you're a candidate.
So don't ask: "gosh, are algorithms really all that important? do you ever need to do that kind of thing in real life? I've never had to do that kind of stuff." You'll just get rejected, so don't say that kind of thing. Treat every question as legitimate, even if you are frustrated that you don't know the answer.
Feel free to ask for help or hints if you're stuck. Some interviewers take points off for that, but occasionally it will get you past some hurdle and give you a good performance on what would have otherwise been a horrible stony half-hour silence.
Don't say "choo choo choo" when you're "thinking".
Don't try to change the subject and answer a different question. Don't try to divert the interviewer from asking you a question by telling war stories. Don't try to bluff your interviewer. You should focus on each problem they're giving you and make your best effort to answer it fully.
Some interviewers will not ask you to write code, but they will expect you to start writing code on the whiteboard at some point during your answer. They will give you hints but won't necessarily come right out and say: "I want you to write some code on the board now." If in doubt, you should ask them if they would like to see code.
Interviewers have vastly different expectations about code. I personally don't care about syntax (unless you write something that could obviously never work in any programming language, at which point I will dive in and verify that you are not, in fact, a circus clown and that it was an honest mistake). But some interviewers are really picky about syntax, and some will even silently mark you down for missing a semicolon or a curly brace, without telling you. I think of these interviewers as – well, it's a technical term that rhymes with "bass soles", but they think of themselves as brilliant technical evaluators, and there's no way to tell them otherwise.
So ask. Ask if they care about syntax, and if they do, try to get it right. Look over your code carefully from different angles and distances. Pretend it's someone else's code and you're tasked with finding bugs in it. You'd be amazed at what you can miss when you're standing 2 feet from a whiteboard with an interviewer staring at your shoulder blades.
It's OK (and highly encouraged) to ask a few clarifying questions, and occasionally verify with the interviewer that you're on the track they want you to be on. Some interviewers will mark you down if you just jump up and start coding, even if you get the code right. They'll say you didn't think carefully first, and you're one of those "let's not do any design" type cowboys. So even if you think you know the answer to the problem, ask some questions and talk about the approach you'll take a little before diving in.
On the flip side, don't take too long before actually solving the problem, or some interviewers will give you a delay-of-game penalty. Try to move (and write) quickly, since often interviewers want to get through more than one question during the interview, and if you solve the first one too slowly then they'll be out of time. They'll mark you down because they couldn't get a full picture of your skills. The benefit of the doubt is rarely given in interviewing.
One last non-technical tip: bring your own whiteboard dry-erase markers. They sell pencil-thin ones at office supply stores, whereas most companies (including Google) tend to stock the fat kind. The thin ones turn your whiteboard from a 480i standard-definition tube into a 58-inch 1080p HD plasma screen. You need all the help you can get, and free whiteboard space is a real blessing.
You should also practice whiteboard space-management skills, such as not starting on the right and coding down into the lower-right corner in Teeny Unreadable Font. Your interviewer will not be impressed. Amusingly, although it always irks me when people do this, I did it during my interviews, too. Just be aware of it!
Oh, and don't let the marker dry out while you're standing there waving it. I'm tellin' ya: you want minimal distractions during the interview, and that one is surprisingly common.
OK, that should be good for non-tech tips. On to X, for some value of X! Don't stab me!
Tech Prep Tips
The best tip is: go get a computer science degree. The more computer science you have, the better. You don't have to have a CS degree, but it helps. It doesn't have to be an advanced degree, but that helps too.
However, you're probably thinking of applying to Google a little sooner than 2 to 8 years from now, so here are some shorter-term tips for you.
Algorithm Complexity: you need to know Big-O. It's a must. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. It's, like, one chapter in the beginning of one theory of computation book, so just go read it. You can do it.
Sorting: know how to sort. Don't do bubble-sort. 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.
For God's sake, don't try sorting a linked list during the interview.
Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview.
Trees: you should know about trees. I'm tellin' ya: this is basic stuff, and it's embarrassing to bring it up, but some of you out there don't know basic tree construction, traversal and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very very least. Trees are probably the best source of practice problems for your long-term warmup exercises.
You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree. You should actually know how it's implemented.
You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.
You might not use trees much day-to-day, but if so, it's because you're avoiding tree problems. You won't need to do that anymore once you know how they work. Study up!
Graphs
Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think.
There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should 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. You should know their computational complexity, their tradeoffs, and how to implement them in real code.
You should try to study up on fancier algorithms, such as Dijkstra and A*, if you get a chance. They're really great for just about anything, from game programming to distributed computing to you name it. You should know them.
Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!
Other data structures
You should study up on as many other data structures and algorithms as you can fit in that big noggin of yours. 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.
You should find out what NP-complete means.
Basically, hit that data structures book hard, and try to retain as much of it as you can, and you can't go wrong.
Math
Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other places I've been, and I consider it a Good Thing, even though I'm not particularly good at discrete math. We're surrounded by counting problems, probability problems, and other Discrete Math 101 situations, and those innumerate among us blithely hack around them without knowing what we're doing.
Don't get mad if the interviewer asks math questions. Do your best. Your best will be a heck of a lot better if you spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.
I know, I know, you're short on time. But this tip can really help make the difference between a "we're not sure" and a "let's hire her". And it's actually not all that bad – discrete math doesn't use much of the high-school math you studied and forgot. It starts back with elementary-school math and builds up from there, so you can probably pick up what you need for interviews in a couple of days of intense study.
Sadly, I don't have a good recommendation for a Discrete Math book, so if you do, please mention it in the comments. Thanks.
Operating Systems
This is just a plug, from me, for you to know about processes, threads and concurrency issues. A lot of interviewers ask about that stuff, and it's pretty fundamental, so you should know it. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, and you'll be a dinosaur in a real hurry if you don't understand the fundamentals of "modern" (which is to say, "kinda broken") concurrency constructs.
The best, most practical book I've ever personally read on the subject is Doug Lea's Concurrent Programming in Java. It got me the most bang per page. There are obviously lots of other books on concurrency. I'd avoid the academic ones and focus on the practical stuff, since it's most likely to get asked in interviews.
Coding
You should know at least one programming language really well, and it should preferably be C++ or Java. C# is OK too, since it's pretty similar to Java. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language.
Other Stuff
Because of the rules I outlined above, it's still possible that you'll get Interviewer A, and none of the stuff you've studied from these tips will be directly useful (except being warmed up.) If so, just do your best. Worst case, you can always come back in 6-12 months, right? Might seem like a long time, but I assure you it will go by in a flash.
The stuff I've covered is actually mostly red-flags: stuff that really worries people if you don't know it. The discrete math is potentially optional, but somewhat risky if you don't know the first thing about it. Everything else I've mentioned you should know cold, and then you'll at least be prepped for the baseline interview level. It could be a lot harder than that, depending on the interviewer, or it could be easy.
It just depends on how lucky you are. Are you feeling lucky? Then give it a try!
Send me your resume
I'll probably batch up any resume submissions people send me and submit them weekly. In the meantime, study up! You have a lot of warming up to do. Real-world work makes you rusty.
I hope this was helpful. Let the flames begin, etc. Yawn.
93 comments:
Thanks, Steve; that was very helpful, although it would've been more helpful before I had a phonescreen with you guys last fall and totally brainlocked on a tree traversal. I kid you not, I could hear the guy interviewing me impatiently tapping his fingers on the table. He was just ITCHING to pencilwhip my ass out of there. I don't interview all that well, even though I like to pretend I'm not a dumbass.
Big +1 on data structures and algorithm study, though. Not knowing the answer to the tree stuff made me go out and read algorithm/DS books, and it was very, VERY helpful. Plus I got to use it in an interview that I managed not to fail.
The best discrete math book I've ever read has to be "Concrete Mathematics: A Foundation for Computer Science" by Graham, Knuth, and Patashnik
Great post. As a programmer who's hitting that "5 years out of college" threshold soon, some of those algorithms read less like everyday tools and more like old friends. Not good, not good, time to blow off the dust and crack open the books :)
MIT OpenCourseWare has really good lecture notes on discrete math for CS. They served as the textbook for a college class I took on the subject.
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-042JMathematics-for-Computer-ScienceFall2002/Readings/index.htm
Considering that I'm still in my freshman year, I'm going to try to make full use of all this....I'll let you know how it goes in about....say 5 years.
Thanks Steve. Great advice for a graduating senior. I got my first offer last week, but I never rule out Google!
A degree in CS is nice, but don't get discouraged by not having one. I get by just fine with my BS in Math and a pickup of basic CS class (plus some extra studying on my own). This is a great summary of everything a person should hit if you don't have that CS background.
For Combinatorics, try "Applied Combinatorics" (Roberts & Tessman). There are lots of examples and problems. It's a good book.
http://www.cs.cmu.edu/~15251/
great lecture notes on discrete math on the wiki (for free).
Thanks for a great set of interview tips Steve.
For those of you who might be considering taking the dive and applying at Google I have one more suggestion. Apply with us at Valve Software (you know, the video game company? Half-Life? Counter-Strike? Steam?) too. You'll get put through a very tough interview process similar to Google's and it will be a great warmup for your Google interviews if nothing more. Best case you'll pass with flying colors and we'll convince you that not even Google could be cooler or more fun than Valve.
http://www.valvesoftware.com/jobs.html
Oh man, where was this a week ago! I just went through a four-hour brain squeezer of an interview for a company here in Manhattan and felt very stupid a few times that I'd forgotten some fairly basic stuff. (In my defense, I've been at architecture-astronaut level of abstraction in a very niche field for the last year as a consultant, so while I can talk at length about how one particular problem domain is handled in the financial industry I was brain-farting on things like what exactly the servlet life cycle is.) Oh well, at the very least an honest swing and miss would be respectable in my mind and it helped me figure out what my study list needs to be in the near term. Thank you very much for posting this list of pointers.
It looks like there's a bunch of good suggestions already for discrete maths texts both online and off, but here's a decent one (imho) that also has the virtues of being widely available and dirt cheap (~$15), "Discrete Mathematics (Schaum's Outlines)" by Lipschutz and Lipson (2e). I feel almost bad about suggesting it next to a list of "real" texts (e.g. anything by Knuth) but if you're long out of school or sold your existing text and want dead tree it's a solution.
Great post (as always). I can't say I'm interested in working at Google since I live in North Carolina (although I see you guys have opened a data center here...), but the book suggestions alone make it a good blog post. I have a copy of "Applied Combinatorics" (which someone else recommended), and I concur that it's a great book on the subject.
"Discrete Mathematics with Graph Theory", by E. Goodaire and M. Parmenter. ISBN: 0131679953.
I did a phone interview @google about a year and a half ago just for giggles.
Gots no degree at all so I was curious how far I would get. And I love a challenge!
It was pretty brutal and it was just for an ops position. I didn't get it. First rejection of my career, which was pretty humbling!
My advice for an operations/IT gig, make sure you understand everything about the gig from the bottom up. I realized to my horror in mid-sentence that in all my career I had never really understood exactly how DNS was implemented. Fun!
Plus, don't ask the interviewer to repeat themselves. Take notes or interview on a speakerphone in front of a whiteboard.
Anyway, great article. I'm going to go make sure I understand all the CS topics from the bottom up. That should make for a fun weekend!
P.S. I wouldn't work for Google anyway. The fact that they advertise fraudulent services, like psychics, galls me. Especially given their motto and supposed dedication to science.
"But the really important takeaway is this: if you don't get an offer, you may still be qualified to work here. So it needn't be a blow to your ego at all!"
Bullshit. That's exactly what I would have said in between the thoughts of what questions I clearly got wrong.
Dang... your post comes about a month and a half late! Oh well, I'm sure I'll interview again when I'm closer to graduation.
OK besides my 'bullshit' comment, this is great. The idea of bringing in your own whiteboard markers is smart. I'd give credit for preparedness. It wouldn't turn a mediocre candidate into a good candidate, but it would be a good soft-touch credit.
There are definitely parts of this list I don't know, and parts I just have forgotten, and while I'm not looking for a job, this could turn in to an excellent skills check-list.
Great write up! I am a system administrator trying to get into programming and this gives me a great place to start.
BTW, I am looking for work (specifically in the NYC office), and my resume is online: http://www.core.binghamton.edu/~burner/new/res.html
*wink*
One follow up question, is there a particularly good way of dealing with the "now, what questions do you have for us?" question?
The Best Answers to Tough Interview Questions should be of some help for non-technical questions.
Steve, you are the best, as always. I had my Google interviews about month ago - and I can't agree more on everything you mentioned (well, maybe except for thin pencil thing ;).
One little addition to the tech prep skills section would be dynamic programming - the tasks on this one appear to be quite common.
FWIW, Adjacency lists and the object-oriented form for graph representation are effectively the same. The problem with adjacency lists is you have to decide where to put the lists. If you happen refer to the lists from your nodes, then you end up at the OO form without necessarily distinguishing it.
On the subject of Discrete Mathematics I would recommend "Concrete Mathematics" By Knuth, Graham and Patashnik.
Send me your resume
I'll probably batch up any resume submissions people send me and submit them weekly.
OMG, Steve, how much do you plan to cut on these referral bonuses?
If I get hired, can we share 50/50? :)
Very helpful post Steve thanx!
Also I am not sure why no one mentioned the free online educational resource form ArsDigita available at http://www.archive.org/details/arsdigita .
They span a wide range of CS topics.
So that's it? I thought there was more to software than 1's and 0's. What about knowing how to deal with requirements or change requests? What about knowing a few principles about software quality? What about knowing some foundations on software architecture? What about some knowledge of effective development processes?
You said that these questions were more oriented to software engineers, but it sounds more oriented to computer scientists.
I'm not saying that algorithms and data structures aren't important, but there's more to development than just knowing where and how to place a bunch of 1's and 0's.
But, as you have said, there are many types of interviewers at tech companies. I think there should be two or more different types of interviewers per interview so the candidate can get a better chance of answering the questions (it might help to decrease the false negative results).
Thanks for writing this post, it was very informative.
--
www.BrianDiCroce.com
I did the whole phone screen (I should say screen x 3) and flyout to Mountain View with Google. It was a fantastic experience regardless of the fact that I was sent home without an offer in hand (nor did one come since). A few people that I have spoken with regarding their experiences in the Google interview process are quite bitter. That is, they tend to fall into two categories: 1) "How dare they ask those college course questions!" and 2) "Screw them I didn't want to work there anyway" (these are not xor). However, I was never bitter at the way things shook out, and viewed it as a motivating factor for making myself smarter. You better believe that the next time someone asks me to design a concurrent queuing system, I will knock their damn socks off. ;)
Great post.
-m
had you just posted this 2 weeks ago I might have not been rejected by Google. Very good programming tips. I wonder, can you get rejected by google and reapply again anyway? I mean is there a timeout period I should wait for before reapplying?
Thanks, Steve; that was very helpful.
I was recently interviewed with one of those goggle type companies and I was rejected after second round of phone interview.
The first one went ok and the second one went really well (at least from my perspective). The second interview was scheduled for 45mins but it went almost 1:15 mins. All the questions are exactly as you described in this blog. Alogorithms, operating systems and finally some coding in Java (yes, over the phone. He wanted me to read out the code for him on the phone).
After the second phone interview I was pretty sure I will be called for an onsite interview :-) but to my surprise I got an email from recruiter saying "After serious consideration, the team has decided to pursue other candidates at this time. We are currently reviewing your resume for other opportunities." Well I know that is a standard rejection email but I would have felt really good if I got a good feedback from the recruiter.
Is it possible to get a feedback on my interview? Can I write to the recruiter back asking for feedback or should I just leave it aside and move on with other opportunities. Of course 6months is not a long time :-).
Thanks again for your excellent post.
I just want to question the obsession with writing code on a whiteboard. Nobody ever writes code on a whiteboard (except maybe to very roughly show some structure). That's what computers, with nice text editors, and syntax highlighting are for. Everybody types (and certainly edits) faster than they can write on a whiteboard. I'd rather write code in notepad than on a whiteboard. Give your interviewees a shot at writing code on an actual computer, you know, like what they would actually do on their job. As a bonus that makes it really easy for you to test if the code really works.
There's a lot of good stuff in this post though. I enjoyed it.
Tim
I'm curious, why Google? I mean, aside from working for a huge conglomerate and perhaps it's "the chic place to work", I don't see why Google can afford to be so picky through it's interview process. In fact, I'd say the arrogance and apparent growing bureaucracy throughout the HR process that is in Google seems to be almost such a turn-off that I don't think someone could get me to work at Google even if they paid me some grandiose amount.
That would be a great article Steve, the arrogance of Google. I'm not trying to troll or be flamebait and I don't mean everyone or even you, I love your blog & writing style but it's impossible to ignore this elephant in the room.
Jeff,
Why not? It seems to me that Google is in an interesting position that only a few companies in the past could claim. That is, they are the desirable place to work in tech, probably the most desirable. I haven't seen the numbers, but I have to imagine that there is a mountain of resumes piled in the HR department. If that is the case, then why shouldn't they be picky? It is a win/win situation as far as I can see.
-m
Mathematics: A Discrete Introduction is a good book on discrete math.
Just a minor issue, but I had to get it out: The guy's name is Dijkstra, not Djikstra.
Otherwise, thanks for the great write-up.
My previous company hired a guy who has mad whiteboard skills and couldn't code or design for shite.
Um, if you select for whiteboarding skills, that's what you're going to get.
If I ever hire an employee the interview process is going to consist of putting him/her on a computer with his/her favorite editor and go from there.
Why not put your candidate in the environment they're going to be working in?
Who the hell codes on a whiteboard with hyper-annoying misguided uber-geeks staring at them over their shoulder.
I'll be avoiding the Google interview process like the plague. Thanks.
Pablo,
That's just the thing. You will *never* be able to properly simulate that potential employee working in your environment. Sitting them in front of a computer no more shows their propensity for working in your company environment than making them use a slide rule.
-m
Sitting them in front of a computer and writing code is a lot closer to what they will be doing on their job than standing them in front of a whiteboard and writing code.
Here at GHS everybody who comes on-site is expected to write a small but interesting program, from scratch (about 4 hours of time). I think that's a hell of a lot better than writing code fragments on a whiteboard, and it really isn't all that hard to administer such a test.
Tim
Note to Self: no need to apply for a job at Google. Your process is filtering for CS-bots, not necessarily top-quality programmers or engineers. The best programmers I have worked with with have either walked out on your interview or been asked to leave. Most didn't have traditional CS degrees and they couldn't care less about Big-O. They knew when they hit a problem that required more study and tools to be brought to bear, but the key is having the skills to know what you need to know and the ability to go seek out that knowledge. And graph theory? Please - get over yourself.
I would just like to add a suggestion: do some company-specific technical reading. This is especially easy when preparing to apply at Google, which has a few white papers out there. Reading up on map reduce, and being able to ask some questions about the paper (and talk about how I had done a distributed process at another company) might very well be what got me in.
And, guys, don't blame Steve for what Google's interview process is. He didn't say it's optimal, he's just telling people how to prepare for the terrain. The process appears to screen for CS-bots, as some of you say, and I'd like to see more questions asked about process -- but since they likely won't be, the burden is on you to just mention as much of that stuff as you can while answering the technical problem. For example, scribble some quick Javadoc on the whiteboard while saying "in real life this would probably have to be exposed in a user manual", make a quick stab at writing unit tests, etc.
> And graph theory? Please - get over yourself.
> I would attack X itself, except that I do not want to pick up a book and figure enough out about it to discredit it. Clearly I must yell a lot about how stupid Stevey is so that nobody will listen to him!
Why I Would Never Hire Steve Yegge:
I'm quite sure that less than 10% of all software developers in this world are able to understand big-O complexity, n*log(n) sorting algorithms, hashtable implementations, graph theory, n-ary trees, NP-completeness, mutexes and semaphores. But Steve states that (for him) this is all basic knowledge, and that his requirements for candidates are not much different from those of any other software company. Now, if this was really true then 90% of the software developers in this world would not be able to find themselves a new job at this time, if they needed to. As this is definately not the case -- millions of them are changing jobs every year, despite all their shortcomings -- Steve's statement is evidently false. I know companies that hire demented trolls only because they look a lot like software developers, and they know which side of the computer they need to bang with their club. (And in my own interviews, I prefer socially-aware software engineers with common sense over uebergeeks from outer space. But that's another story.) Therefore... 1 point off for tunnel vision, distorted sense of reality and false reasoning. I can't abide know-it-alls.
In my opinion, building software is about delivering value to customers and making users happy. -- Oh, and it would be nice if you enjoyed doing that, but it's no requirement. -- Software engineering is so much more than just knowing your "basic" algorithms and data structures. It not only entails Construction, but also Requirements, Design, Testing, Maintenance, Configuration Management, Project Management, Process Management, Tools, Methods and Quality. According to SWEBOK, the knowledge area of Construction -- for many of us, including me, the most enjoyable part -- accounts for only 1/10th of the body of knowledge for a software engineer. Many of us need that part to enjoy ourselves. However, we need the other 9/10th to make our customers and users happy. Therefore... 1 point off for forgetting whom you're building for.
I hate it when people talk to long. The KISS principle is just as valid for blog posts as it is for code. If Steve's blog writing is any measure of the volume of code he writes, then I understand why Google is so busy building these super server farms here in my country. -- Therefore... 1 point off for not knowing when to stop.
Anyone who misspells the name of one of the greatest thinkers in the history of our Software Engineering discipline must be turned down immediately. No matter how many sorting algorithms he knows by heart. Now, I wouldn't mind if people accidentally referred to Stevey Yiggo. That would be understandable. But come on, misspelling Edsger W. Dijkstra is quite something else! -- Therefore... not 1 but 2 points off. Because Dijkstra was Dutch, just like me.
That's five points in the negative, mr. Yegge. Thank you for coming, that will be it. Don't call us, we'll call you. Please leave the markers on the table. Thank you.
Noop.nl
One other technical X I would add to the list: know how the web works down to the level of IP packets.
Fortunately, this is a technical area that there's a very easy home test for, so you can assess yourself well in advance of your interview and read up on what you don't understand. Go get a packet tracing tool, such as wireshark. Capture all the network activity that happens when you ask a freshly opened browser window to go to www.google.com (just the front page, not counting what happens when you start typing).
Now make sure that you can explain every single packet you just captured in detail. This should cover DNS lookups, the three-way TCP handshake to port 80, HTTP headers on both the request and response, etc.
The description "software engineering" is starting to cover too broad a field and seems to be the main cause of confusion for many here (evident in some comments above).
If you're building software from scratch or very near the metal, rather than very high level 3rd party bespoke business agile solutions, of course knowing graph theory is going to be more useful than studying stuff like requirements and configuration. they're completely different areas and it's just disappointing to read confused defensive comments by some seemingly insecure "offended" types here.
Perhaps worth writing a post some day about different layers of the software cake sometime to clarify such things.
I don't have the credentials for Google, and nor do I intend to work on that kind of software anytime soon - most of my work is with high level languages/frameworks and problem solving with those, but *still* found your content valuable.
Would have thought fewer words are better to describe most things well, but your blog proves otherwise. don't be put off, ever, and keep up the great work.
"I'm curious, why Google?"
Start on this page and work your way down...
http://www.google.com/support/jobs/bin/static.py?page=benefits.html
Jurgen said: "Anyone who misspells the name of one of the greatest thinkers in the history of our Software Engineering discipline must be turned down immediately."
You should Google around and see what Dijkstra said about "software engineers" (hint: he put it in scare-quotes, too).
It's also odd that you don't think that programmers need to know big-O notation or n log n sorting algorithms (!) but still have kind words for Dijkstra. Another hint: the kindness would not be mutual.
If you don't know why you're doing what you're doing, you're just an Eclipse macro that happens to breathe. Educate yourself.
I've only just started programming, and I've gotta say, that's an intimidating list. Still, speaking as the neo-est of neophytes, it looks like a lot of fun stuff to study! Thanks for the ideas!
Steve,
Are there software engineer jobs at Google that aren't so academic in nature?
For example, do the people who work on Gmail have to memorize all of that "baseline" stuff you listed?
Is there room for smart software engineers at Google who like working at a higher level?
I'm genuinely curious to hear your answer. Google seems like a great company to work for, but I'd sooner be bashed in the face with a sledgehammer than have to commit all of that low-level nastiness to memory.
My impression of Google is that they can afford to hire only the '10' employees. Can't really blame them.
I like to think of myself as maybe a 9 tops, so no free lunch for me!
The important thing I think is that if someone understands the fundamentals, whether its graph theory or an http session from layer 1-7, they can figure out the high-level stuff no problem.
I do think they are hurting their bottom line in the long run though, as hiring only one "flavor" of employee can make for dull products. Compare/contrast with Apple for example.
I'm also willing to bet that the seeds of the next Google are being sown within their own walls as we speak. Lots of smart people with money in close proximity tends to make new companies.
Btw, from what I hear from people I know actually at Google, its a very mixed experience. The senior folks (pre ipo) are, not surprisingly, pretty happy. The worker bee types tend not to like it so much.
Hi Steve, great post as always.
I really like the Grimaldi "Discrete and Combinatorial Mathematics" book. This was the book (along of course with the discrete math class) that made me really feel I had a Vocation as a programmer.
A lot of people will recommend Concrete Mathematics by Knuth, but went through that and preferred the Grimaldi.
For the people questioning why this is useful in interviews... it's sort of like auditioning for a job in the classical music field. You'll be asked to play not just some set audition pieces and some sight reading, but also scales, arpeggios, etc.
If you can play an F minor arpeggio and an E major scale confidently on demand, the reviewer can probably safely make some assumptions about your basic musical knowledge and skill. Of course, you might be able to do those and still suck, but hopefully the rest of the audition will take care of that.
Hey now, quicksort isn't O(n*log(n))! Are you sure you work at Google?
Those people criticising Steve or Google for being "too academic" (in requiring basic knowledge of the domain) are merely exposing their own ignorance - or worse, inadequacy. Data structures and algorithms are the foundation upon which solid programs are built; those who believe that other people are supposed to worry about them are condemned to live out their days are mere interior decorators - or worse, to build unintentionally collapsible buildings.
Nonetheless, there are legitimate reasons to shy away from Google as an employer, not least its size. Whether you believe that large organisations are simply unworkable, have a zero tolerance for bureaucracy, even relatively benign forms (any large organisation has to spend some effort making sure it continues to go in the same direction, which is what bureaucracy is - it comes with the territory), or simply can't stand to be in close proximity with any number of your fellow man (especially those fellows who might work at Google) - as it happens, I'm afflicted by all three - Google wouldn't be a good fit, and no long and exciting list of benefits or cool technical challenges (and believe me, I can see how cool they are!) can offset that.
Now, if you'll excuse me, I have to go and refresh my ADS knowledge :)
@oligophagy
Actually, Stevey didn't specify whether he was using an average case or worst case analysis.
Now, if he had said worst-case n*log(n), then sure.
Which actually raises a question... what to do when the interviewer is wrong?
I heard of one interviewee that was asked how to lazily instantiate a singleton in Java without locking every single time the getter is called (the infamous "double checked locking" issue). This is effectively impossible, and the interviewee informed the interviewer about the problem with the question. The interviewer then proceeded to argue (wrongly) that DCL is a perfectly proper solution...
"For example, do the people who work on Gmail have to memorize all of that "baseline" stuff you listed?"
I'm intimidated by the amount of complexity in Gmail, as i think about it. Like everything else in Google, it is a distributed application, with millions of users, each of which has gigabytes of emails stored. Emails are interconnected between conversations and between users; Conversations are interconnected between users; Attachments are interconnected between emails and between users; Everything is stored in some sort of a grid, possibly in an efficient manner (no need to save the attachment for both the sender and the receiver).
What have we? A graph of email conversations modeled in a distributed storage system. All the text is scanned in favor of presenting relevant ads, which is not the easiest thing in the world. If any part of this gigantic system is implemented inefficiently, the whole thing becomes much too slow for use by millions of people. And let's not forget that the UI and the server/UI communication are written in a subset of Java that is compiled to Javascript, which I am sure is a method developed specifically for Gmail. So all in all, I'd say yes, the people who're working on Gmail do need to be proficient in Computer Science. It is just not possible to create such an application without deeply knowing what you are doing.
From a fellow Kirkland Googler:
An excellent post that I highly recommend Google candidates read before their phone screens or interviews. I can't stress the importance of hashtables or big-O enough. Whether or not the topics are actually important, they come up regularly in interviews often in the same question: "So, you've given me a O(n*logn) solution using a tree, can you come up with a better solution?" should serve as a huge hint.
I also want to echo the extremely high false negative rate and it's arbitrary nature. It's true and it's frustrating from both sides of the table (a candidate several interviewers may like can still get rejected), but dust yourself off and try again.
One minor quibble though, depending on the job for which you are applying you may be asked to rate yourself in several areas. This is, generally, to alleviate some of the problems with getting an interview quizzing you about Java when you're more familiar with C++ (or Python). It's not perfect, but interviewers typically will take that into consideration before asking questions.
Related to the point about asking questions, just demonstrating some enthusiasm goes a long way. There's often not much you can do about this, if the interviewer is asking you particularly inane questions, but in a typical interview there should be at least one question that can be taken in an interesting direction.
"Is there room for smart software engineers at Google who like working at a higher level?"
From another Googler, I say yes, absolutely. But you'll still be expected to know the basics. It's near impossible to be a really good software engineer at *any* level if you don't understand why to use one data structure or algorithm vs. another, even if you're not implementing them.
Google even expects product managers to have a good foundation in this stuff, so you can bet you'll be expected to for any kind of programming position.
One tip I haven't seen, that helped me a lot before interviewing, was to read Wikipedia. The articles on various data structures and algorithms are great, and free. Read them!
If your language of choice is Java, study the source code of the Collections classes. Understand how *they* implement a HashMap, and then you'll be able to do it too. You might be surprised at how simple most of that code is.
I'm quite sure that less than 10% of all software developers in this world are able to understand big-O complexity, n*log(n) sorting algorithms, hashtable implementations, graph theory, n-ary trees, NP-completeness, mutexes and semaphores.
Really? Then more than 90% of coders in the world aren't up to the job. Unless you count "coders" as someone writing HTML for a webpage.
Out of that stuff, I'd say knowledge of hashtree implementations isn't critical so long as they're aware of the pros and cons of hashtree (and other container) usage... that's about it. For me to hire someone, they'd have to have at least the ability to hold a conversation about everything else in that list.
How can anyone claim that Big-O notation is not important??? Unless your datasets never grow above a few KB maybe.
I mean, I wasn't bang alongside everything Steve just said, but seriously... your comment is like saying "people don't need to know how to program to be programmers". Um... they do, y'know. They really do.
I intereviewed at Google a few years ago and had a great time. I wasn't offered the job, and I can choose to chalk that up to either the false-negative problem or the fact that I blew a few questions.
But one thing I'd like to comment on from the article is the recommendation to know one programming language *really* well, "preferably C++ or Java".
That should read "preferably C++. We will allow you to write code samples in Java, but we will silently dock you points for not knowing C++."
One of my interviewers asked me to reverse a String.
I wrote the code to get the char array from the String object and then I reversed the char array (in place), passing the reversed array into the constructor of a new String.
The interviewer frowned and asked if there was anything wrong with the code. I looked at it for a moment, and then stepped through the lines, debugger-like, on the whiteboard.
No, there was nothing wrong with the code.
The interviewer was annoyed, finally telling me "you forgot to null-terminate your array".
In reply, I said "actually, in Java, a String object is like a C struct containing both an array of characters, and an integer indicating the *length* of the string."
Now he was really annoyed. "Yeah. But you didn't put a NULL at the end of the array. You have to put a NULL at the end of the string."
I could sense his annoyance, and wasn't quite sure what to do. But I trudged on, explaining "Well... since the String object knows its own length, it doesn't need to have a null at the end. Java Strings are not null-terminated. They're like Pascal Strings."
He paused for a second and then shrugged his shoulders dismissively. "Yeah, well I never really knew much about Java."
The moral of the story is this:
Java may be a decent programming language, but you loose points for writing code samples in Java, since many of your interviewers probably consider it a lesser platform than C++ coding.
Thanks. Guess I have a lot to learn. Because I don't know all that stuff.
But I figure I'm ok right now because I'm very new, still in High School and just concentrating on completing the AP test and graduation. When I get to college I can work on the more advanced stuff.
Good to know that Google accepts Java, even though it has its problems (I dislike having to call 4 different methods from one object if I need a whole bunch of variables. Really needs to be a way to return a bunch of stuff at once besides setting up an array, because that can get weird).
@oligophagy, @michael head:
The running time of quicksort depends on your pivot element selection. If you use a linear-time median selection algorithm then quicksort is O(n lg n). I believe that you can read about the algorithm in CLR's Introduction to Algorithms. However, their is an inefficiency in their pivoting code (at least in the first edition). When is it bad? What running time does it give in the worst case? One of my interviewers had a similar problem in a question that he asked me to code, which I found.
If you like solving problems and using your knowledge of algorithms, then Google interviews can be fun. I suggest ACM programming contest problems (easier ones from the finals and some regionals, for example) as good sources of practice material. You could easily be asked similar problems during an interview.
@mlvanbie
Sure, you can tweak the selection algorithm and guarantee an n log(n) runtime, but you kill your performance, so nobody does it that in practice. That's why the textbook answer is that quicksort is n log(n) in the average case, and n^2 in the worst, but everyone picks it over mergesort because its constants are so much lower in the average case.
Special pivot selection is more of theoretical interest -- though I agree it is interesting and worth being aware of.
@Michael Head
>lazily instantiate a
>singleton in Java without
>locking every single time
>... impossible.
Wrong. DCL will work in the Java5 memory model if the reference is volatile. Even then, its an ugly approach. The better approach is to use a static inner class as a holder of the instance and rely on the fact that class loading is synchronous.
In fact, stating ignorance is a fine answer. Stating something is impossible is always a wrong answer, unless mathematically provable.
This is really a great discussion.
Can anyone @Google provide a short list of either a "Google Library" of recommended texts or at least bulleted list of Wiki articles? I have about 60% of a CS education under my belt and would love to really dive back into this stuff.
On a completely unrelated note, I think there is an elephant in the room here. For all the supposed brainiacs, no one has supposed that there may be more people qualified to work @Google then there are positions available. So no surprise there are false negatives.
Google isn't the alpha and the omega. They've already IPO'ed, so you ain't gonna be googlenaire anytime soon. And trust me, once you realize you spent your life working overtime in order make someone else rich, you will realize those dinners weren't 'free' after all.
@ben
Thanks, that is true, I should have written the problem as "without any overhead" rather than "without using synchronized".
And, BTW, the point of my comment wasn't about the specifics of DCL in Java, but questioned what one may do when the interviewer is actually wrong on a point.
Do you just write off the interview at that point, accept an incorrect premise, or try to correct the interviewer?
This is probably a useless comment, but I'm hoping this will stave off anyone giving me more guff for mentioning Singleton vs. DCL.
Sure, I could have been more specific about the anecdote, but we all understand that there are issues with respect to double checked-locking. I misposed the supposed interviewers question. But that detail isn't critical to the point. The point of my story was to imply that the interviewer wasn't aware of those issues.
And my question was, what does a hypothetical interviewee do in that situation?
Don't let the anecdote distract from the message! (I say this knowing exactly how I'd respond to an imprecisely/incorrectly posed question).
what's wrong with trying to sort linked lists?