When I first started doing coding interviews, I got passed over by all my top choices; looking back at that time, I can see I had gone into them terribly unprepared. Today I sit at the other side of the table, and despite the many blog posts and books that have been written on the subject, I’m now the one encountering people who are unprepared or badly prepared for a coding interview. This is why I set out to write the one guide I wish I’d had when I was right out of college and interviewing for the first time, the guide I myself will follow from here on out.

Over the years I’ve worked at various companies where I got to hone my interviewing skills and where my involvement in the hiring process taught me what to ask, how to prepare for and how to interview. In this guide you’ll get an overview of the process, find out about the six steps to success as well as get my take on what data structures and algorithms to review. This guide can’t guarantee you a job but it will help you maximize your chances of putting your best foot forward.

Disclaimer: the opinions stated here are entirely my own, and not necessarily those of my current or former employers.

The Process

This section describes the general interview process at Silicon Valley companies, it’s meant to be informational; feel free to skip it.

There are generally two tracks to getting an interview besides applying directly: the current-employee-referral track and the LinkedIn track. While the former is slightly more expedited and deferential, the latter is probably where the majority of candidates hails from; in fact every day there are countless of recruiters whose sole job is to look for and reach out to prospective employees on LinkedIn; so keep your profile up to date, get connected, get endorsements and add any skills, personal projects or contributions you’ve made to open source software.

The first contact generally happens over email after which a recruiter will call you and get a sense of your technical background. If your skills align with what the recruiter is looking for, a phone interview will be set up where you can be expected to write code on a shared online document. Just so you know this document is likely to lack any type of code completion and syntax highlighting. Phone interviews last between 30 and 45 mins and if you do well on them, you’ll be invited for an on-site interview. Nowadays instead of or in addition to phone interviews, you may also have to do small coding project.

The on-site will consist of several interviews lasting 45 mins to an hour. They will be very similar to the phone interviews except the questions tend to be harder; however being able to see your interviewer in person will somewhat make up for it. A few weeks after your onsite, all feedback should have been reviewed and a hiring decision will be made on whether to extend an offer or not. If you don’t get an offer, be conscious that interviewing is a stochastic process where an element of luck is involved; treat it as a learning experience, and maybe remind yourself of Brian Acton who didn’t get a job at Facebook and Twitter before going on to become the co-founder of WhatsApp.

Which language to use officially doesn’t matter, but unless you’re interviewing for a job with specific language requirements such as iPhone developer or front-end developer, I strongly encourage you to code (and hence practice interview questions) in a language that is used at the company you’re interviewing.

The Six Steps To Success

The point of the coding interview is to determine if and how well you can code. Generally you will be asked to code a function or method, but sometimes you will need to write a class definition or design a series of related code modules. In any case, you’ll want to approach the problem methodically and adhere to the following steps:

1. First, make sure you understand the problem. Many questions are purposefully vague or ambiguous and this is the moment to ask for clarifications and ensure you actually answer your interviewer’s question. Asking questions also has the added benefit of allowing yourself some time to let your brain kick in.
2. Try an example or two and nail down the problem’s constraints and requirements (during the on-site do this on the whiteboard and during the phone interview use a notepad). Try to pick examples of medium size that also cover some edge cases. If you can think of a diagram that might be relevant, draw it. In fact, write down anything you think can help as it will serve as a visual anchor for you to return to when you’re stuck or thinking.
3. Talk things through, this is probably the most important step. Try to make the interview as interactive as possible; the interviewer doesn’t know what’s going on in your head and letting her into your thought process allows her to give you helpful hints and steer you away from going down a wrong path. The goal for you is to validate your approach with the interviewer before writing down a line of code and the more clearly and the more effectively you are able to articulate a solution the better the instant feedback you’ll receive.
4. Figure out your solution by using the following techniques: think back about similar problems you’ve encountered and how they were solved, try different algorithmic approaches (divide and conquer, greedy algorithms, recursion, sorting, etc.), break up the problem into smaller more manageable pieces (you can get partial credit), and finally go through your list of data structures as sometimes just thinking of the right data structure will give you the right solution.
   If you’re really, really struggling then be honest and ask for a hint as a last resort; you will get dinged for it but if it helps you clear an embarrassing mental hurdle then it’s well worth the penalty.
5. Start coding once you have talked through the problem and explained your solution to the interviewer. Be mindful that unlike shared documents where you can copy paste, leave comments, and come back to fill out skeleton methods and functions, coding on the whiteboard requires some clearheadedness and whiteboard space-management skills. Luckily by now you should have a pretty good idea of what you’re going to write down before you do so start at the upper-left corner of the board, and make sure you’re not blocking the view of your interviewer as you’re writing your solution. Take the time to make your code solid and pretty as your code will be part of the interview feedback. Talk out loud and explain what you’re doing as you’re doing it; this will enable your interviewer to more easily follow along.
6. Lastly, verify your code with different examples and special cases and walk through it line by line. This will illustrate your thought process, allow you to flush out minor bugs and demonstrate that your solution works. If you want extra credit, you can even write unit testing code! End with a discussion of the space and time complexity of your solution.

Phone Interviews Caveats

Phone interviews deserve a special mention because it’s where most people will fail. Part of it is because they’re the first real filter in the hiring process but some of it is also because their format, prone to miscommunication and lacking visual cues, makes them particularly unforgiving.

There are two major stumbling blocks of phone interviews, the first is that during the start of a phone interview the only thing that both parties can see is a blank shared document. This creates the tendency from the part of the interviewees to overcompensate for the loss of non-verbal communication by rushing to communicate through the screen. Unfortunately this seldom ends well. It’s thus imperative to not pay any attention to the blank document staring you in the face, and to first understand and evaluate the question (the first four steps) all while making up for the lack of physical presence by being as engaging as possible (remember that on the other end of the phone is an interviewer who could easily distract herself by doing something like checking email).

The second stumbling block is the logistical matter of having to type on the computer and talk on the phone; instead of using one hand for each function or having your phone on speaker mode, I recommend you receive the call on your computer through Google Hangouts (you’ll need a Google Voice number, and you’ll also need to test this before the interview). Use headsets or headphones to further minimize bad reception and improve communication.

Algorithms + Data Structures = Programs

If you’re wondering why software engineering interviews are dissimilar to every day programming you may be interested to read this answer on Quora. The bottom line is: your interview will test your foundation of computer science and be very heavy on algorithms and data structures so you will want to practice interview questions to get yourself in an interview problem solving mindset.

In the short run the very best thing you could do to prepare is to buy a whiteboard and go through Cracking The Code Interview, it’s full of great advice and the many interview questions and solutions it contains will help you with problem identification and solution pattern matching. See the end of this guide for more links to common interview questions.

In the long run though, nothing beats studying a data structure and algorithms book. I recommend the many classes on coursera as well as The Algorithm Design Manual which covers basic data structures and sorting algorithms in its first half but whose real values is in its second half where you can find a treasure trove of useful and interesting problems and various ways to solve them.

Of course in the long run we’re all dead, so I’ll make things easy and go over the key concepts you should absolutely brush up on.

Arrays / Strings

Arrays and strings are for the most part interchangeable and in fact most of the string-manipulation problems you’ll encounter will be solved based on your understanding of arrays. With that in mind you should know how to traverse arrays, know how to access, shift and transpose their individual elements and know how to apply various set operations on them. Binary search might be at the heart of more interview questions than any other single algorithm (if you ever get a question that has a sorted array, chances are a binary search should be part of your solution), you absolutely have to know how to implement it.

Sorting

Closely related to arrays, are sorting algorithms. It’s unlikely you’ll be asked to regurgitate a sorting algorithm and more often than not it’ll be sufficient to know that sorting can be done in at least O(n log n). Still, you should have a cursory knowledge of the implementation details of merge sort and possibly quicksort and radix sort.

Dynamic Arrays / Growable Arrays

A dynamic array is an array that resizes itself as needed while still providing amortized constant time access. A typical implementation is that when adding an element to a full array, a new bigger array is created and elements are copied from the old array to the new one. You should be able to implement a dynamic array during an interview.

If you get a non-array question but you need an array like data structure for your solution, save yourself some trouble and use a dynamic array.

Hash Maps / Hash Tables / Dictionaries / Hash Sets

Hash tables are the swiss army knives of programming and many different types of problems (checking for presence, calculating frequency, sorting, etc) can be optimally solved with them. It’s almost guaranteed you’ll encounter them in your interview process and you should understand how they work (the role of hash functions, how collisions are resolved, when and why to resize) and how to implement them.

Linked Lists

Linked list problems are most common in C and C++ interviews as they’re an easy way to ascertain whether a candidate understands pointers. Still, they’re so basic and fundamental that you should know how to implement them from scratch no matter what language you use. Furthermore since most linked list problems are mere variants of well-known problems dealing with traversal, removal and insertion, linked list problems can easily be prepared for, leaving you no excuse to not ace them.

One of the tricks used in many linked list solutions is the slow/fast pointer technique whose simple idea is as follows: use two pointers to iterate a list with one pointer ahead of the other. The fast mode pointer might be ahead by a fixed amount (helpful in determining whether a list has a loop, or to find the kth element) or might be skipping multiple nodes for each node that the slow pointer goes through (if the fast pointer goes twice as fast for example then by the time it reaches the end, the slow pointer will be in the middle).

Note that when interviewers talk about linked lists, they often mean singly linked lists but you should clarify anyways.

Stacks / Queues

Stacks and queues typically come up as part of the the data structures you’ll use to solve problems. You should know how to implement them with both linked lists and arrays.

As an added exercise implement a stack using two queues as well asimplement a queue using two stacks.

Trees / Binary Tree / BST / Trie / Heap

You may not see trees and graphs on a day-to-day basis but you’re prone to see them at your interviews, so thoroughly review those data structures.

The most general definition of a tree is that of a collection of nodes with zero or more references to other nodes, in practice though, when interviewers say “tree” they mean a special type of tree called a binary tree. A binary tree is a tree where each node has at most two children, commonly referred to as left and right.

A binary tree should not be confused with a binary search tree which is a special binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent. The advantage of binary search trees is that, if the tree is relatively balanced (ask your interviewer for clarification on this issue), lookup, insertion and deletion can be done in O(log n). Other important properties of binary search trees are that you can obtain the smallest element by following all the left children, and obtain the largest element by following all the right children.

Note that there are methods to always keep trees balanced; the most common are red-black trees and AVL trees. I wouldn’t bother knowing the exact implementation details, just know that those data structures exist.

You absolutely have to know tree traversal algorithms though: breadth-first-search, depth-first-search, and the difference between inorder,postorder and preorder traversal.

Here’s an example implementation in Java of an in-order traversal that prints out the values of a tree (preorder and postorder are nearly identical):

void inOrderTraversal(Node root) {
 if (root == null) return;
 inOrderTraversal(root.getLeft());
 // Do something with the value
 System.out.println(root.getValue());
 inOrderTraversal(root.getRight());
}

A trie (pronounced “tree”) often used for string problems is an n-ary tree in which each node besides the root represents a character or a partial or complete word and each path down the tree represents a word. It’s really less complicated than it sounds, just read the wiki page and learn how to construct one as well as how to look up values in it. Note that you can output all keys in the trie by means of pre-order traversal. As an exercise, think of how you could use a trie to implement an auto-complete function.

Finally, heaps, also called priority queues are the last tree data structure you should know. They are usually binary trees that satisfy the heap property: each child of a node has a value less than or equal to the node’s own value. Consequently the root node always has the max value which means that the max value can be found in constant time, but this comes at the cost of lookups of any other values which take O(n). Insertion and deletion are still O(log n).

Directed / Undirected / Weighted Graphs

Graphs, like trees, consist of nodes with children but unlike trees, those nodes can have multiple parents possibly creating a loop or cycle. In addition the links — also called edges — between the nodes may contain more information than just a pointer and may have values or weights. A graph with one-way edge edges is called a directed graph. A graph with only two-way pointers is called an undirected graph. A graph whose edges have weights, is called a weighted graph.

There are three ways of representing graphs, but only bother withadjacency matrices and adjacency lists. You should know their computational complexity, their tradeoffs, and how to implement them in real code. Which to use depends on the type of graph you have; for example, simple graphs that are well-connected might be better implemented by an adjacency matrix, while sparser graphs might be best represented by an adjacency list.

Note that if you’re implementing weighted graphs, you’ll probably want to define an Edge class.

Graph theory is such a broad subject that it’s unclear how many graph algorithms one should be familiar with for an interview so I’ll just list what I think would cover 90% of the graph questions: you absolutely must know to how to traverse a graph (DFS and BFS) and how to do topological sorting, you should know how to implement Dijkstra’s shortest path algorithm (this is a neat video explaining it) as well as Prim’s algorithm and finally, it’d be nice if you knew how to do the A* search algorithm.

Other data structures

You’ll be able to solve the vast majority of the problems using the above data structures but feel free to leave a public comment on this section and suggest other data structures to your fellow readers.

Bit Manipulation

To work with bits you first have to know that numbers are internally represented in binary two’s complement notation which is the same as plain binary notation except for negative numbers where you “flip each bit and add 1″. For example to get the number -1, start with 1, which is 00000001 in binary using an 8-bit integer. Flipping each bit results in 11111110 and adding 1 gives us 11111111 which is the two’s complement notation of -1.

The left shift operator “<<” shifts bits to the left, filling the exposed bits with 0’s.

The right shift operator “>>” shifts a bit pattern to the right but its behavior is different in different languages when right shifting a negative number; in Java’s case, right shifting performs sign extension filling the empty spaces with 1’s for negative numbers.

The logical right shift operator “>>>” is unique to Java and Javascript and fills the empty spaces with 0 no matter the value.

To set a bit: use the bitwise OR operator (|)

num |= 1 << x; // this will set bit x

To clear a bit: use the bitwise AND (&) combined with the NOT (~) operator to mask all the bits you don’t want to clear.

num &= ~(1 << x); // this will clear bit x

To clear all bits from the most significant bit through i inclusive do:

num &= (1 << (i + 1)) -1;

To toggle a bit: use the XOR operator (^)

num ^= 1 << x; // this will toggle bit x

To get a bit: AND the bit you want to check

bit = num & (1 << x);

Design Patterns / Object-Oriented Programming

Problems relating to object-oriented programming will involve designing sets of related classes so as to test your familiarity with OOP-concepts and get a handle on how you architect your code. Use interfaces and/or abstract classes and keep the Singleton, Factory and Strategy patterns in mind for such problems, they can go a long way towards demonstrating that you write elegant, maintainable code.

Programming things to know

Know how to read and write to files in the language in which you’re coding, and know how to generate random numbers.

Math

You’re not interviewing for a math position but considering that we’re surrounded by counting and measuring problems, there are a few mathematical concepts that are fair game in programming interviews, notably prime numbers, base conversions, and some elementary combinatorics.

For prime numbers, know generally why they’re important and know that every number can be decomposed into a product of primes. Also know how to implement the sieve of Eratosthenes.

As for elementary combinatorics you’ll want to know about permutations and combinations.

A permutation is an arrangement of members of a set into a particular sequence or ordering. For example, there are six permutations of the set {1,2,3}, namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). The number of permutations of n distinct objects is n!.

There is also something called partial permutations that are the ordered arrangements of k distinct elements selected from a set of size n and is expressed with the following formula:

A combination is a way of selecting members from a grouping, such that the order of selection does not matter. For example, a poker hand can be described as a 5-combination (k = 5) of cards from a 52 card deck (n = 52). The number of k-combinations in a set that has n elements is 0 whenever k > n and can otherwise be expressed as:

Concurrency

Concurrency questions aren’t very common but they do come up and you don’t want to be caught flatfooted, so review how to create threads, how to use synchronization as well as locks to access shared resources, and understand the conditions that lead to deadlocks. A good way to prepare for this topic is to implement synchronized versions of your favorite data structures.

Behavioral

• Do your homework and know the company, know yourself and know why you’re there. Understand what the company does, what your new role would entail and what excites you about it. Changing jobs is a big step so take it seriously and do your research beforehand.
• Keep it positive. Be in a good mood, smile, don’t talk negatively about your current or previous jobs and when describing challenges keep the tone upbeat and emphasize the positive things you’ve learned.
• As a corollary to the previous point don’t negatively prime your interviewers; some of them will ask you how things have been going so far, don’t say you struggled with one or two interviewers, say everything’s been going great.
• Be passionate! Let your excitement shine through and show your enthusiasm for software development, technology and solving big problems.
• Ask questions. Be genuinely interested in what your interviewer does on a day to day basis, ask about their challenges and opportunities, come prepared with a few pre-formulated questions and illustrate your interest in the company and the position. Whatever you do though, don’t ask how you did; first of all it’s unlikely you’ll receive anything else but a boilerplate answer and second it’s not a good idea to put your interviewers on the spot.
• Be gracious and close the loop. After you conclude the interview, send a short thank you note to your recruiter and let them know how you think things turned out.
• Reflect on what you learned. No matter the outcome, you will have learned some things — whether a gap in knowledge or new interview questions — so be self-reflective, and learn from your experience.

From: How to crush the coding interview