Preparation guide for google: II

Preparation guide for google: II

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.

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.