Shared publicly  - 
 
(Ob disclaimer: these opinions are my own, I do not speak for my employer, etc)

Public service announcement: if you follow the advice of articles like the one below from the WSJ or anyone else who tells you that Google interviews ask brain teaser/lateral thinking puzzles, you will not get hired. The people giving this "advice" simply do not know what they're talking about, or they are deliberately lying to you to sell books/page views.

I spent ~20 months serving on one of Google's hiring committees, which means I saw all the questions being asked in interviews for Test Engineer and Software Engineer in Test positions. If someone had asked questions like the one from the WSJ article ("you are shrunk to the height of a nickel and thrown into a blender blah blah blah"), we would have sent the interviewer an irritated email asking them to knock it off and ask real questions.

When training engineers to interview candidates, Google's very explicit instructions are to not ask brain teaser questions or any question where there's a trick. This is why you won't get asked to sort 1 million integers in 1MB of memory: without realizing the trick, you can't make any headway; if you don't make any headway, we don't learn anything about you.

Each interviewer comes up with their own slate of questions (from their own experience, from Google's internal question database, from talking to friends, whatever), but here's what's usually on my list:

- I want to see you write real code. I'll give you an algorithm or a problem and you'll need to write functioning code in a real programming language of your choice. You can start off with an inefficient solution and iterate to make it better, that's fine, but the code will need to work. If you use a high-level language so you can take advantage of a rich standard library, your reward will usually be to code up some piece of the standard library you just used. I want proof that you understand how that function/data structure you're using works.

- I want to see you solve a vague, open-ended problem. This will generally take the form of "You know how Google Product X does Y? Design that." I want to see you go from a high-level idea to a concrete process flow, data structures, algorithms, etc. If you hand-wave too much, I'll demand more and more details to make you demonstrate you know how these things will work under the covers. If you get a solution too quickly, I'll start throwing in extra constraints: it has to be faster; it has to use less memory; it needs more throughput; it has to support Feature Z; whatever. I want to see how you react to changing requirements.

- I want to see what happens when you get stuck. I try to ask questions with seductive naive, wrong answers; if you hit the honeypot, I get to watch what happens next. Candidates who can't get out of the honeypot and back to a working solution are in trouble.

Also, pro tip: don't ever put on your resume that you're an "expert" in something unless you invented the thing in question. Saying that you're an expert means we get to ask the most nit-picky, obscure questions we can come up with (opportunities like this make for great lunch-table conversations). "Experts" risk facing the combined maniacal, sadistic glee of a dozen Google engineers.

TL;DR: Google doesn't ask lateral thinking puzzles in interviews. Spend your time writing code, solving hard problems, and thinking about the hard problems other people have solved and you'll do fine.
30
172
Wayne Duran's profile photoDmitry Titov's profile photoJohannes Berg's profile photoDorron Katzin's profile photo
22 comments
 
"This is why you won't get asked to sort 1 million integers in 1MB of memory" is of course a double trick question.

If you get stuck on it then you've probably failed to see that 1 million ints won't fit in a meg. But if you dismiss it by saying "1 million ints won't fit in a meg" you've failed to see that it's a platform dependent question, and on some platforms 1 million ints can fit in a meg. If you further realize that megabyte is a term that is tossed around fairly loosely you can argue for another ~48000 bytes to use for local variables, and then standard sorting algorithms can work.

You can even take it further, because you have a bound on the problem size you can show that in this situation naive bubblesort runs in constant time.

Edit: May I ask a clarifying question? Is the list already sorted?
 
+teryret teryret, the real trick is that the question doesn't mention anything about resources other than RAM. I believe the canonical solution is to shard the integers to files on disk and then do a merge sort.

More broadly, though, you don't want the interview to become a variant of "guess the number in the interviewer's head", and this question turns into that really easily: the interviewer has a clever solution, and any attempts to think outside the box (ie, leading away from said clever solution) get disallowed.
 
Proves your point well, I had unwittingly taken 'memory' more generally than RAM.

Edit: Lol, in that case I amend my answer: I load all million ints into CPU cache and sort them there.
 
ISTR the canonical answer is that "the bubble sort would be the wrong way to go", but I suspect the candidate was pre-fed the answer (and some people claim he used a teleprompter).
 
+Chris Jones, a friend recently did a phone screen where he could hear someone whispering answers to the candidate. At first he thought it might just be the candidate talking under his breath, but then the one voice started arguing with the other voice. Things went downhill from there.
 
Can I draw your attention to http://infotrope.net/2011/07/21/a-note-to-google-recruiters/ of the case of someone re-interviewing to be able to go back to the job they had been doing for years at a company bought out by Google.

"True story: in my interview I was asked how I would extract entities from an HTML page. I suggested using OpenCalais (a free-as-in-beer API that does just that, and returns Freebase identifiers). If someone in the Freebase community wanted to do something like that, that’s exactly what I would have recommended. But the interviewer wanted to know how I would implement it myself. I told him I wouldn’t — that that’s why I was leaving the Search group for Developer Relations! Wrong answer, apparently."

Unfortunately, your choice of deciding that everyone should be able to reimplement everything works out as another "Guess what the right answer is they want" in a lot of cases. Replacing 'magic questions' with other 'magic questions' doesn't make the interview process any better, just changes what irrelevant knowledge the interviewee has to know. In the above case, someone doing Developer Relations certainly shouldn't be wasting their time re-implimenting a well known library, so they answered as what they would do as part of the job. But they didn't know the secret, that you want to know is if they understand how such a function work, and so it ended up being a trick question.
 
+Jay Blanc, I think it's completely fair to ask a candidate how they would implement a given API or service. Being able to compose existing tools/code into something new is fantastic, but a) someone had to write the code you're using in the first place; b) what happens if that code needs to be changed? I expect software engineers to be able to poke under the hood and fix something that needs fixing or add a new feature. (I don't know enough to comment on the expectations for other positions.)

It's also frequently an issue of getting a candidate to think at a scale beyond what they're used to or to see how well they can work with unusual requirements. Example question: how would you implement driving directions for an online mapping product? What data would you need? How would you structure the computation? How would you make it fast? How would you make it work for the entire world? You don't need to come up with Google's exact solution, but the candidate would need to engage with the question, make some progress and come up with something interesting.
 
Google has that motto, right, "Don't be evil"? How to ace a Google interview has an answer that's similar (I think): "Be good".
 
+Collin Winter "Without using a library? Okay. So... Can I just do it for XHTML, or do you want me to implement a full SGML parser. And do I have to cope with defects in the input. And all on that white board? In less than an Hour? Because if so, I think you seriously underestimated the complexity of this problem set."

See, in the example I gave above, she did engage the question. She said it was irrelevant to the scope of Developer Relations to reinvent existing libraries, and would waste time and probably produce a lesser product that provided little assistant to the end user. But that wasn't what the question was probing, it wanted acknowledgement of how HTML is put together and what a system needs to do to work with it. Hence she needed to know the secret of "Do not answer this like someone who actually did this job, answer it like a fresh out of college CompSci grad."

Focusing in on being able to remember the right algorithm for any single problem is... also problematic. I doubt there are a large number of programmers over thirty who still have Dijkstra's algorithm memorised. There are a number who remember what it is, what it does, which problems it solves, and what it's limitations are. But would tell you they'd need to look it up. (Praise Knuth) You seem to have slanted your interview process so that it will give an advantage to recent CompSci grads who still have the stuff in relatively fresh memory.

Also... "Software Engineer" != "Programmer". Seriously. It doesn't. A Software engineer can do their job without programming at all. High level design even works better sometimes if you don't get drawn down to the "nitty gritty". There is a reason why "Design by Programmer" is a byword for shoddiness in open source projects that are code-jumbles put together ad-hoc. The roles of "Software Engineer" and "Programmer" can exist in the same person, and by all means Google can have the policy of wanting it's designers to be able to code, but it's sloppy to conflate design with implementation.
 
+Jay Blanc You were going pretty strong until the last paragraph. There are lots of systems designed by SEs that simply failed because the never could work. An SE who doesn't know programming, intricately, who doesn't know the "nitty gritty" is prone to design systems that look elegant, but are hell (if not impossible) to implement in a working an performing way. Design by SE? C++. Common Lisp.
 
+Jürgen Erhard And as we all know, no one anywhere ever uses C++, and no one ever attempted to fix the problems in C++'s design or design a better object orientated system that borrowed the things that work from it.

Good Software engineers fix the design when the implementation shows errors in it. Just like good programers fix their mistakes. Saying that bad designs exist where design and implimentation were seperated does not mean that design being separated from implementation leads to bad design.
 
+Jürgen Erhard +Collin Winter Also, I suspect that both of you have fallen for what I'm going to call the Mozart Fallacy. Mozart was not, contrary to popular opinion, technically competent in performance with every instrument he composed for. He was competent in many, but not all musical instruments, and he of course relied on orchestra players not only to perform his works, and also to inform him when revisions must be made where practicalities needed to be addressed.

A composer is to a software engineer as a programmer is to a orchestra player. A good composer is addressed of the practicalities that the orchestra player can achieve, but it is not a requirement to be a good orchestra player to be a good composer. It is particularly not required to be a good orchestra player of all possible orchestral instruments to be a good composer.
 
Those 20 months must've come after I interviewed at Google, Collin, because my interview was exactly like that. None of the interviewers had seen my resume before entering the interview room; none of them knew what work was involved in the position I was interviewing for, or would be working directly with the person eventually hired; none of the technical questions related to problems to be solved in a real-world software engineering position (either that, or the use of standard libraries is disallowed at Google, so every engineer is required to implement all CS101 sort routines from scratch); and the "capper" question literally came directly from the "AHA!" puzzle page of the then-current issue of "Make" magazine (vol. 09, page 189).

Also, none of the interviewers were within 15 years of my own age; this was right around the time that Brian Reid (with whom I had previously worked at DEC) was in the first rounds of his (ongoing) age-discrimination suit against Google.

I interviewed with VMWare in the same month, and the contrast was striking. The interviewers were the members and supervisor of the team with the open position. They asked informed, intelligent questions about my job history and the duties those jobs involved. (Oh, and unlike my Google interviewers, VMWare was not the first company they had ever worked for.) I was posed a hypothetical but reality-based problem (an automated nightly build and test system) and asked to start designing a database/object schema for representing scheduled tests and their results, thinking out loud and sketching an ERD on a whiteboard.

The impression I got from the people who interviewed me at Google was that they had heard about Microsoft interviews and were trying to be like that. (At least they didn't ask why manhole covers are round.) I've been told (by the Google recruiters who email me every few months) that the system has improved substantially. Collin, if you were part of reining in those interviewers who thought they were trying to hire a Will Shortz or a Scot Morris, you probably deserve some of the credit for that improvement. (Although I would like to hear you disambiguate "questions where there's a trick", which are disallowed, and "questions with seductive, naive wrong answers", which are encouraged.) But the worst that can be said of that WSJ article is that it's outdated, not that it's inaccurate, because it's exactly in line with my own interview experience at Google.
 
+Jay Blanc The comments thread on that infotrope post is just as eye-opening as the article.
 
Hey +Dave Krieger, thanks for your comments. A few notes in response:

- I see the difference between "questions where there's a trick" and "questions with seductive, naive wrong answers" as this: a question with a trick in it depends on having a eureka moment, and if you don't have it, you're completely stuck. I'll take the examples brought up so far: the trick in "sort 1 million ints in 1MB of RAM" is realizing I didn't say anything about limitations on disk space; for "jump out of the blender", you need to know that weight changes by the cube while muscle strength changes by the square. If you don't know or realize either of those, there's no way out, since your interviewer (really, dungeon master) is almost certainly going to rule out any other solution.

When I talk about "questions with seductive naive, wrong answers", I'm talking about a problem where you immediately see a solution and start coding, only to realize that, "hey, this is more complicated than I thought". We've all been there. When I give these kinds of questions in interviews, the candidate's downfall is almost invariably that they didn't try thinking of counter examples before coding. Frequently they won't ask any clarifying questions, talk through their solution first, or write down any examples at all before they start coding. The only trick here is that you need to understand the problem before you can solve it.

- I'm curious about your "none of the interviewers were within 15 years of my own age" comment, which you seem to imply is a bad thing. Why? Sure, Google is generally a young company, but we're not unique in that, and it can't have come as a surprise.

- Without knowing your specific situation, what position you were interviewing for, or who your interviewers were, I can still say this: anyone asking questions from the puzzle section of this month's magazine issue is a moron, and I hope they were duly smacked down by the supervising hiring committee. Unfortunately, we can't be there in the room to monitor every interview, so we can only catch these mistakes post-facto, but I'm sorry you had a bad experience in that regard.

I will defend asking candidates to reimplement common library routines, though. My rationale is this: if a candidate can't figure out how a function they use frequently or claim to understand actually works (assuming the problem is known and already solved), how do I have faith that they'll be able to solve problems they haven't seen or thought about before?

- If you were interviewing in 2004-2005 (based on your reference to Brian Reid), then yes, I believe the hiring process has changed dramatically since then. I'll still defend saying that the WSJ article is inaccurate, though, since their eight-year-old information isn't going to help someone get hired today.
 
+Collin Winter Again, "Reimplement common library routines" is not the panacea you think it is. It only works if you ask for simple trivial to implement routines where you explicitly state before hand why you are asking, otherwise you're going to get the experienced people try to explain why they wouldn't reinvent the wheel. And then that depends on them being able to remember the full algorithm required for any particular problem, which is not a sign of being able to do their job just a memory trick. So unless you give them access to a copy of Knuth's during the interview, you're slanting your interview process to hiring new graduates who just had their final and have that particular algorithm fresh in memory.

And frankly, yes, Google looks and acts like it's average age is below 25

And that isn't a good thing, because 24 year olds make tons of mistakes till they learn some experience.

But Google has apparently set up a way to try and keep it's average age low... That does not instil a lot of confidence that Google will build up and retain meaningful institutional experience.
 
+Dave Krieger, while it's true that some interviewers occasionally ask odd questions like this, we specifically avoid "trick questions" -- those that are easy only once you see the "trick". We work to improve the skills of those interviewers that ask such and most of the questions you receive should be coding, problem solving, or the like (for a software-engineering position, anyway).

Also, not looking at your resume is often a choice. I never do because I don't want to bias my questions/judgement of the candidates by hitting them only on their strength. Afterwards I check.

The goal of an interview is to find the boundary between what you know and what you don't know. I will push and drill-down until the candidate can't answer and then I'll move on. I'm typically nice enough to explain this in advance since some get rather flustered when they can't answer. :-)
But note that we're less interested in your knowledge than in your understanding and your ability to apply what you know and what you're told.

How do you ace a Google interview? Love what you do and do a lot of it. The rest will come naturally.
 
[Rrrrr, I was writing a long reply to Collin and the damn page refreshed, losing it all. (Those censorship algorithms are getting good! JUST KIDDING) Let's see what I can reconstruct:]

Thank you for your thoughtful reply, Collin; when I posted the same remarks in another thread where your post was shared, one Googler dismissed me as a troll. (Bad P.R., that.)

Being a young company isn't in itself a bad thing, but it correlates with a predominance of people who have never worked anywhere else, which can be a bad thing. Microsoft was notorious for that practice back when it was the Google of its day; it would hire naive grads and work them to death while drumming into their heads that (a) every other company does the same thing so stop whining, but (b) we're simultaneously somehow the best place to work in the world, ever, because (c) we're all so brilliant that people at other companies are as the apes and monkeys by comparison, so (d) any criticisms you hear of Microsoft come from envious derelicts who will die in the cold and the dark.

You don't have to be naive to drink this Kool-Aid; social psychologists have documented the mechanisms pretty thoroughly (but mainly by studying cult religions, not corporate cultures), and seasoned and intelligent people who are properly skeptical in other areas can be quite susceptible to this kind of in-group belief system (in part because they know they're so intelligent and skeptical they couldn't be taken in by something that wasn't true). It's flattering to think you're one of the Elect; it's so seductive that it's probably believed by the employees of most successful companies. ("Sure, but those fools at Apple, Oracle, and Google are deluding themselves; we've got the One True Religion!")

Why is any of this bad, if thinking they're superior to everyone else pleases employees and makes them more productive? It works... for a while, for most people. But it can also lead to the belief that your worth derives solely from your intellect (and by extension, your job), and from there, to a life seriously out of balance -- failed marriages, neglected health, the realization that your kids grew up and moved out while you were coding. I'm sure we all know some unhappy millionaires, and we probably also all know someone who made a bundle at one of the big success-story companies, and then blew all the money trying to find the fulfillment that had eluded them in the job.

Being a young company is a bad thing if age discrimination is the mechanism by which the company got that way. Some of the emails and other documents presented as evidence in Brian Reid's case are pretty damning. (And the 2010 California Supreme Court decision in the case looks to open the way for much broader powers of discovery going forward.)

I've taken up enough space on this topic. To all Googlers (and Microsofties and members of the Apple Corps or whatever the hell cutesy names companies have for their workers) -- if you are happy, contented, and fulfilled in your work, I wish you the best... even though you'll never know the sublime joys of working among the truly brilliant megabrains I'm humbly conceited to be surrounded by every day at my company (for which, naturally, I do not speak).
 
I'll be graduating in four years (if all goes well) with a major in Mechanical engineering, and a minor in robotics. I would love to work at Google, on the self driving car or other projects. Do you have any ideas that could help me land a job at my favorite company ever?
 
Having led many interviews for Google, I can vouch, this is good info.
 
+Tom Keaney, yep, I'm working on some posts about exactly that topic. I'll add a comment here with a link when they go live.
 
Now, that was a very, very useful post for me (I'm currently waiting for response regarding the initial phone screen...).

I was quite worried about forgetting to really grade myself on topics (outside of Operating Systems, where I specified whether I had in-depth knowledge, "working knowledge" or basics (though those can be... varied).

As for reimplementing library routines... from what I dug up, it's more about "what are the basic algorithms underlying that" and if you know where to find (and where to look for) the missing bits, it's okay. I was definitely less worried after hearing that no, I don't have to write the hash function from scratch if asked to implement a hashtable :)
Add a comment...