I think it could be valuable to have the perspective from someone who trained for these interviews very recently and got a job offer as a direct result. I’m going to detail how I prepared for technical interviews in ~1 month, after which I got a job at Facebook. The process of getting an interview all the way up to getting an offer will probably take 1-2 months extra after that. Note that this is for the general Software Engineering position (in my case, new grad), and nothing specific like Android/iOS developer, or Infrastructure Engineer, or so on.
The cool but not-so-convenient thing about tech interviews is that you really never know what you’re going to get, so you have to be prepared for a huge range of possible topics, some of which are more likely to occur than others. I’ll touch on these below and then outline some very important question-types that may arise and that you should be prepared to deal with.
So let’s say your interview is in one month. Here’s how I would plan said month (assuming a full-time schedule). Note that this is what I would do (and did, actually), so it might not be the optimum approach for you, but I suggest working similarly and switching it up a bit based on how you feel you’d grasp concepts better (e.g. solve and code in parallel, as opposed to what I did which is solve everything then code everything…)
I assume that you have taken an algorithms course and know your way around major data structures including but not limited to: binary trees, binary search trees, hash tables, heaps, stacks, queues, graphs, lists, tries… as well as all algorithms related to them (insert, delete, search, find, find max, find min…) and the time complexity for each of these, at least at a high level. For graphs you need to know searches (BFS and its properties, DFS and its properties including cycle detection and the like) and shortest path algorithms (Dijkstra, Bellman-Ford, and A*) at a bare minimum. If you don’t know all these, along with Dynamic Programming, you’re going to need longer than a month. Pick up Introduction to Algorithms (CLRS) and start studying them first. This is the easy part, as it’s all academic and it’s just expected that you know all of it. The part that follows below (Day 1 onwards) is the actually valuable part that I can offer you.
I also assume that you know a programming language like C++ (or Java) and the built-in functions which actually make it useful (i.e. STL or its Java equivalents). If you don’t know STL, spend time learning vectors, maps, sets, unordered maps, unordered sets, queues, stacks, and the entire “algorithm” library (seriously, all of it). These are essentially implementations of what you just learned in CLRS, so that if you need to use a heap you won’t actually start to code one during an interview (just use a map or priority queue). You also need to know how to implement a linked list, BST, and a trie in 5 minutes flat, which is a lot easier than it sounds (just build a Node class and an insert function and for interview purposes, you’re good).
I do not assume that you know anything about the following topics: parallel programming, computer networks (HTTP/ TCP/ IP/ Ethernet), operating systems/ scheduling, threads/ processes/ parallelism/ concurrency, assembly, hardware and hardware-descriptive languages, or whatever else. While these are all valuable concepts to know as a computer scientist (as are machine learning and AI and others), the chances that they come up are close to none unless you state them as skills on your resume, so your time is better spent elsewhere (i.e. working on the topics below). You do need to have some awareness of distributed computing, though, so scroll down to the System Design section for that and make sure you read the MapReduce paper at the very least.
Buy this book: Elements of Programming Interviews. Phew. That was hard.
In all seriousness, this is the best book on the subject in my opinion, and I’m actually really surprised so little people know about it or use it. The collection of questions is excellent and to-the-point, it is large (300+ problems, which is the most I’ve seen in one book), they focus on the right concepts (e.g. several problems are on binary search, which is extremely likely to come up in an interview — more so than any other algorithm), and their answers (and the code provided) are almost all correct and excellent. I say “almost” because there are 1 or 2 problems which have much simpler solutions than the book details, but it’s not an issue, especially when you compare it with other programming interview books, which have several answers which are downright incorrect. Plus the online support community is pretty good, with Java code available for all problems (the book has them in C++ only) and an online forum for discussions over at Elements of Programming Interviews. They also forgo all the ‘teaching’ stuff that other books have where they try to teach you big-O notation and data structures, and focus almost completely on the problems part, which is much, much, much, much more important. The big-O notation and data structures you should learn from CLRS, which is the best resource for them, period. No other book, especially not programming interview books, come close to its quality in teaching that stuff.
I also know (through various sources) that several of these problems are actually asked as-is during interviews, which shows how on-point it is. If this happens to you, however, I suggest you tell your interviewer, as it’s very easy for them to tell if you know the problem before or not, and if you just recite the answer it defeats the purpose of the interview. Luckily for me, I wasn’t asked any of the problems I’d done from the book.
Go through the book chapter by chapter, one chapter per day, starting at Chapter 5, ending at Chapter 19. Do every single problem. All of them. (To be completely honest, I might’ve skipped a few, but this was more by accident than anything else, and I definitely did like 98%+ of them.) Don’t code, solve the problems only (i.e. find the algorithm). Give yourself a deadline per problem, depending on how hard the problem is (for example, 10 minutes for non-ninja problems, 20 minutes for gray-ninja problems, 30-40 minutes for black-ninja problems) — if you haven’t found the solution by then, look at the answer and understand it. If you don’t you won’t improve. It’s important to think of the problems on your own, because it’s the way of thinking that matters, as you can’t go and recite the book on interview day. If you found a solution, make sure it’s correct, and that you have thought of all corner cases.
Note 1: The new version of the book (which I linked to) has all the ninja problems in a separate chapter (Ch. 22). This, in my opinion, is a terrible idea. The book I had had the problems which are currently in Ch. 22 spread across the book, each in its relevant chapter. I suggest you go through the relevant ninja problems of each chapter while doing said chapter. For example, on Day 2, do Chapter 5, and the Chapter 5-related problems in Chapter 22. On Day 3, do Chapter 6, and the Chapter 6-related problems in Chapter 22, and so on. I believe the problems in Ch. 22 are ordered accordingly (the ninja problems of Ch. 5 come first, then those of Ch. 6, and so on), so this shouldn’t be too hard, but I’m not 100% sure as I have the older copy of the book.
Note 2: I sometimes spent hours on a single problem, just because I thought the problem was really interesting and I insisted on cracking it myself. I find these random endeavors useful in the long run, as it develops your critical thinking a lot more than the easier problems, but it also takes time, so you likely can’t do this for every problem, if you even want to do it at all.
Repeat the book, this time with coding. You already know the answers, so you should be able to remember the algorithm for each problem pretty quickly (if you don’t, look it up. It happens, and it can happen sometimes even if you’d previously figured the problem out by yourself.) This is the coding stage, so don’t waste time re-deriving algorithms.
I do not suggest you code all problems, especially if you’re experienced with ACM-ICPC, TopCoder, or Codeforces and the like (and really, if you’re familiar enough with STL, you probably have a decent skill set). Only write the code for problems you feel have complex algorithms, a new data structure you haven’t used before (e.g. unordered map for hashing maybe), problems with tricky corner cases (binary search is at the top of this list as its variants are asked often and can be much trickier than you think) or a programming concept you’re not comfortable with (these include, but are not limited to, operator overloading, custom comparators, custom hash functions, custom == functions, and much more…) If a problem proves tricky for you, or you implemented it in a way which you feel isn’t optimal, look at the solutions the book provides, which are excellent and clean, and will teach you all of the above-mentioned concepts. I suggest you mimic their style of writing code a bit. Some important-if-obvious notes are: use descriptive variable names (none of that 1-letter-variable-name crap) and indent properly, and don’t forget to close parentheses and brackets.
I also suggest you code all problems from the Greedy Algorithms chapter and almost all ninja-marked problems. The Dynamic Programming chapter is also important if you’re not familiar with DP, and can be tough to grasp, so make sure you give it its time. Use CLRS to learn DP if you’re not previously familiar with it.
So now that you’ve exhausted the best question reserve and are comfortable enough to step into an interview, you… need to prep even more. Go to Google Interview Questions (Career Cup). This is a dangerous place. Some very good problems exist, but there’s also a class of problems that my ACM trainer likes to call “Chuck Norris problems”: Problems written where the OP has no idea what’s going on and suggests the interviewer required linear time for problems that clearly cannot be done in linear time like this, which is clearly not linear time, or similar.
Now that you’ve finished Elements of Programming Interviews, you should easily be able to differentiate between good problems and terrible problems. On Day 25, go through “all” (the last 20 pages or so) the Google Questions (even if you’re preparing for Facebook) and make a list of the ones you deem ‘good’, and by ‘good’ I mean problems you feel might have actually been asked in a Google interview. You know the question style from the book, so you should be able to tell which are legit and which are questionable. I assume you should have a list of something like 80-120 questions in the end, some simple, some not so much.
Also note that very few problems actually have correct answers posted on the site, so mainly you’ll have to rely on your know-how to figure them out and make sure they’re correct, but given your previous prep you won’t find it too difficult to know when you should be sure of your answer and when you shouldn’t. This is actually valuable prep for the actual interview, which is a similar experience.
Solve all the problems you jotted down on Day 25. Find the algorithm. If you feel it’s too difficult, seek help. If you feel it’s impossible or the best solution is exponential time, it really might be that the OP was mistaken. Shake it off, move on to another problem. If you still feel like it, code some of the more challenging problems. Several of the Career Cup questions are similar to ones in the book, so you shouldn’t have too much trouble with most problems.
I’ve heard that Google has recently gotten into the habit of asking about Skip Lists (not sure why). Watch this video:
This was first published by Jimmy on Quora in response to the question, How do I get a job in Facebook or Google in 6 months? Jimmy’s response is reproduced here with his permission.