How to study/prep for Algorithms/Google Interviews?

January 26, 2009 8:27 AM

Best ways to prep/study for CS Algorithm/Google style job interviews?

When interviewing for CS jobs, many great companies love to put emphasis on more abstract and academic interview questions involving classical CS problems, algorithm analysis, and design.

I'm more a Software Engineer than a Computer Scientist, with 6 years doing back-end work in web applications and a great CS degree from a top school.

However, I don't do this type of academic work/analysis in my day to day job and it's all a distant undergrad memory. I'd like to prepare myself to start thinking this way again and become more familiar with the problem domain.

There is an argument that this type of interview is not useful and a red flag about the quality of the people running the organization. I agree with that somewhat, but would prefer to build the tools to make the best impression possible in a variety of places.

What's the best way to prep for these interviews?

My current plan was to try and find a sharp grad student in CS to quiz me and help analyze my answers.

posted by anonymous to work & money (19 comments total)

These style of interview question (I have worked in teams crafting many) are designed to separate those who merely know a programming language from those who are good problem solvers, or to say that another way, to divide those who know how to code well from those who know how to write good code.

(Any half-decent programmer can learn another language quickly, but it is near-impossible to teach lateral thinking or creative problem-solving after the fact, especially on the clock.)

So based on that, I'd recommend the sort of CS101 'concepts' refresher you're talking about (and yes, algorithms is most of it) just to remind yourself of what all the available "tools" are (data structures, types of sort, normalizations, debugging techniques, logical problems, memory leaks, etc.) and then stop and switch to a whole pile of those "tapping into your problem solving brain" books about locked rooms and black boxes and how did this murder happen.

Seriously. Hammer your brain with those for a couple months and you'll start looking at problems differently.

It's the synthesis of those two things that these companies are looking for: someone who knows the tools AND is very smart/clever at using them.
posted by rokusan at 8:41 AM on January 26

You could dig out your old data structures and algorithms textbook, if you have it.

Programming Pearls might be good to practice with. It has a lot of interview-type questions and is recommended highly by the kind of people who like that kind of thing.
posted by phoenixy at 8:49 AM on January 26

The problem is there's no real "standard" for job interviews. They're all over the map. One guy might ask you about the latest technology (Spring! Struts! Ruby on Rails! Groovy! JQuery!) Another might ask you algorithm questions, others might ask you to write some code on a whiteboard, etc.

Since there's no standard, there's really no way to study. I think it's really unlikely you'll get questions on big O notation or NP-Completeness.

Frankly, given how dumb most programmers are, the interview questions are not going to be that tough overall, otherwise no one would ever get hired. If you're really a good programmer you shouldn't have too much trouble answering questions. And of course there are going to be lots of dumb interviewers will come up with crazy-ass questions.

One hint would be review and memorize some academic terminology like "Polymorphism", different types of database normalization, etc. You're probably familiar with the concepts but may have forgotten the terms because you don't actually use the terms when you're writing code.
posted by delmoi at 8:49 AM on January 26 [1 favorite]

Delmoi's last bit of advice is golden. That's part of what I meant by re-acquainting yourself with the basics, but boiling it down to the terminology is really the crux of the interview biscuit. You can program, fine. But can you talk like you know how to program?
posted by rokusan at 9:11 AM on January 26

This book may help - it's very geared to the kind of interviews where you get asked questions about linked lists, big O notation, and all that other stuff I remeber for interviews and completely forget at all other times.

There seem to be fads in interview questions - last year it seemed like I got the same questions about abstract classes, interfaces and factory patterns half a dozen times. This year I interviewed less, but MVC came up a lot.
posted by Artw at 9:14 AM on January 26

I think it's really unlikely you'll get questions on big O notation or NP-Completeness.

Big O seems to come up just about every time for me.
posted by Artw at 9:15 AM on January 26 [1 favorite]

One guy might ask you about the latest technology (Spring! Struts! Ruby on Rails! Groovy! JQuery!)

FWIW, the reason for the question is not always the obvious one. I have asked those kind of questions myself, not because the employer cared about that technology qua technology, but just as a check into whether the programmer was up-to-date on his reading and general industry knowledge, or if he stopped learning in the mid-80's and had been coasting since... as many have.

("Rails, yeah that's that goofy framework thingy for Web 2.0 sites that all end up looking the same, right, with fading yellow boxes and really big fonts? Never used it." would have been a fine enough answer for me, even if the job required a better understanding of Rails than that. The answer shows you're aware of the state of the industry, that's all.)

(A programmer who responds with "Oh yeah (x-technology) is cool!" gets a D.)
posted by rokusan at 9:16 AM on January 26

There seem to be fads in interview questions - last year it seemed like I got the same questions...

You're not imagining that. Blame the morons who get paid to write the questions for many different companies, based on what those companies say they want to screen for.

(Blushes. Sneaks out of thread.)
posted by rokusan at 9:18 AM on January 26

It meant I got really good at "What is the difference between an interface and an abstract class", which, TBH, I was kind of hazy on the specifics of.

Assuming you have more than one interview it's probably worth researching anything you got asked and weren't happy with the answer you gave on it.
posted by Artw at 9:21 AM on January 26

Nthing the learning of terminology - because it sucks to have to describe something you know how to use as "the thingie".
posted by Artw at 9:22 AM on January 26 [1 favorite]

Best way to prep for this kind of interview is to do coding contest problems. For example, TopCoder has their problem archive online. They also have some algorithm tutorials, though I haven't read them so I can't vouch for their quality.

It'll take a lot of time. I spent a week doing nothing but Dynamic Programming problems before my last interview, and I went from not knowing what it was to being competent but not great.

Most interviewers I know want to see that you are good at analysis and competent at a language that they think you'll need. It's more important to do that well than to be able to provide a perfect dictionary definition of jargon terms.

Also, like someone else mentioned, buddy up with Big-O notation. There's a good chance you'll be asked about asymptotic running time or space for an algorithm you've never seen before.
posted by jewzilla at 9:36 AM on January 26

Big O seems to come up just about every time for me.

Er, yeah What I meant was, you probably wouldn't get questions involving complex analysis of algorithms to determine their order of growth, like you get in school. You should be able to answer "what's the run time of a binary search, a sort, etc."

Oh by the way, you should check out Stack overflow there are tons and tons of questions on interviewing for and as a programmer. Here's one that's actually pretty similar to the question you asked here.
posted by delmoi at 9:49 AM on January 26

Steve Yegge has written a pretty comprehensive what-to-prep list (read the comments on the post and poke around on his site, there's more stuff you should read too).
posted by inkyz at 10:35 AM on January 26

I would read How to Move Mt Fuji. Also, if you're interviewing at MSFT or GOOG those companies have very repeatable and predictable interview patterns. Google around for people's interview experiences. Also, read about consulting companies interview and how to do a case study question (previously).
posted by GuyZero at 10:54 AM on January 26

jewzilla: Where were you interviewing?
posted by delmoi at 12:16 PM on January 26

There's a good chance you'll be asked about asymptotic running time or space for an algorithm you've never seen before.

Also, brush up on graph-based algorithms. For me at least, these were always the stumpers. Finding cycles in a graph, finding tree depth, graphs and garbage collection, enumerating all nodes in a graph given a root, these sorts of things. I think it's just to try to figure out who paid attention in CS class.
posted by GuyZero at 12:39 PM on January 26

Career cup has a big archive of questions (but with lousy answers most of the time).
posted by jeffamaphone at 1:02 PM on January 26

Google "Google interview questions". Try to solve them, especially the ones that involve writing real code or solving real algorithm problems (like "how could you implement a queue using two stacks?"), not the stupid puzzle/brainteaser ones. If you get stuck on any or want to check your answers, my email's in my profile. I used to be a sharp grad student in CS (or at least I like to think I was).
posted by A dead Quaker at 6:53 PM on January 26

delmoi: I applied this for interviews at Google, VMWare, Palm, and Amazon. To a greater or lesser extent, they are all working off a similar template (started by Microsoft? not sure). Some companies will lean more towards theory, others are more practical, but the constant is that individual interviewers at one company vary more than the interviewers across companies.
posted by jewzilla at 10:54 PM on January 26