Interview Flowchart

This material has been adapted from the book Cracking the Coding Interview (Chapter VII).

The flowchart below highlights a few steps that may help you structure your thought during the interviews. In a real interview, you don't necessarily have to follow this sequence if you have a different approach, but the general ideas should be present. For practice and grading purposes it's expected that you follow this flowchart.

flowchart LR subgraph Solve direction LR A(Listen) --> B(Example) B --> C(Brute force) end subgraph Reflect direction LR D(Optimize) --> E(Test) E --> F(Complexity) end subgraph Code direction LR G(Code) --> H(Test) H --> I(Edge cases) end Solve --> Reflect Reflect --> Code Code --> Reflect

The main idea is that you should find and state a solution as soon as you can. It is often the brute force solution. Once you have done that you are free to reflect on that solution and look for ways to optimize it. Discussing the complexity is a good way to show that you understand your solution at a deeper level and that it is better than the previous solution. Finally you can start writing some code. Postponing the code shows you are able to abstract the problem and also may save you some time if you decide to throw your solution and head to a different direction.

In the sections below we describe each step in more detail.

Listen

Start by paying close attention to the interviewer instructions. Try to identify details that are given during the introduction to the problem.

Tips

Write down the information you've got from the interviewer. It will be useful for you to:

Avoid missing details or restrictions when you are solving the problem;
Gain insight into how to optimize the code.

Before you decide that your solution is ready, review the notes you have taken during the introduction of the problem to make sure you haven't forgotten any of them.

Hint: if the interviewer said anything unusual: (1) it may be relevant for the optimal solution; or (2) they want you to discuss why that piece of information does not affect your solution.

Example

Before you try to solve the problem, write down a few examples. They will be useful to validate possible solutions.

Tips

Not every example is a good example. Actually, we tend to think of bad examples. Always debug your example: is it too short? Is it too long? Is it too specific (e.g. two strings with the same length, perfectly balanced trees, sorted arrays, strings without any repeated character)?

Brute Force

State a solution as soon as you can. Often it will be a brute force solution. No matter how obvious the solution is, the interviewer doesn't know you know that solution. However, don't code this solution yet!

Optimize

Now you can optimize your solution. If you run out of ideas, look for BUD:

Bottlenecks: it is not very helpful to optimize the parts of your solution that are not bottlenecks. For example, if the first part of the solution is $O(N)$ and the second is $O(N!)$, it is not the time to solve the first part in $O(1)$. The overall complexity will remain the same.
Unnecessary Work: check if you are not doing unnecessary work. For example, suppose you are looking for a number n in an array a of ordered numbers. If you know that the number in the middle of the array is less than n, it is unnecessary to look at the first half of a. It would be better to ignore it, i.e., do a binary search. The solution would go from $O(N)$ to $O(log(N))$.
Duplicated Work: look for duplicated work. For example, assume you need to find out if two strings s1 and s2 have characters in common. You could iterate through s2 for each character of s1 and check if they are equal. This would take $O(MN)$, where $M$ and $N$ are the lengths of the strings. Using some additional memory you could use a Set of characters in s1 (built in $O(M)$) and, check if any character in s2, is in the Set (this operation is $O(1)$ in sets). Thus, your new solution would take $O(M+N)$.

Test

Before rushing to the code, make sure you've understood every step of your solution and would be able to implement them. A practical way to do this is by testing your solution (still with no code!) with your examples. Quickly simulate all the steps with the example. This test doesn't have to be very careful, but it is useful to catch basic errors and detect problems in your solution.

Complexity

Discuss the complexity of your solution (time and space) with the interviewer. It's a good practice to do this before starting to code. This discussion may help you identify optimization points. In case you find any, return to the optimization step.

Code

Now you can finally start coding. You may be wondering why not start with the code. Some reasons are:

It shows you think about a solution before jumping straight to the first idea that came up to your mind (that's actually important whenever you are coding, not just for coding interviews);
The length of the interview is quite limited. It's not a good idea to spend too much time coding a solution that doesn't work. That is especially important in whiteboard interviews, because handwriting is often a lot slower than typing.

Test

Test your code using the examples you've created at the beginning of the interview. You should simulate your code line by line so you can find bugs.

Edge cases

If you still have some time, create more tests (preferably short ones) to validate your solution. Don't forget to check special cases (e.g. balanced trees, repeated characters in a string) and edge cases (shortest/longest possible inputs, negative numbers, zero, null/None).