An algorithm for algorithmic technical interview questions
After solving dozens of practice questions, I started to notice a strategy emerge for how I solve technical interview questions. This framework isn’t guaranteed to get you the job; however, the perspective will hopefully help in your practice regimen.
The algorithm is roughly as follows:
- Repeat the problem statement a few times in your head — clarifying (with your interviewer) any unknown terms or unclear clauses in the problem statement.
- Jot down key pieces of information: input domain (numbers, strings, etc), whether or not the inputs are sorted, the type of data structure we’re dealing with (binary search tree or not, singly or doubly linked list, a single or multi-dimensional array), a suggested traversal method (breadth-first or depth-first), or a desired implementation style (recursive or iterative).
- Actively think about edge cases (i.e., inputs that could break your solution) to clarify with the interviewer and run through when testing the solution you decide to code.
- Acknowledge the brute-force solution (that usually smacks you in the face).
- Analyze the (usually quadratic, factorial, or exponential) time and (typically constant) space complexity of that brute-force approach.
- Think about a solution that optimizes for time complexity (i.e., use more space for time savings). I usually ask myself: what are the redundant computations or what can I store (and in which data structure) to reduce the workload?
- Think about a solution that optimizes for space complexity (i.e., takes longer to run but uses less space). It’ll hopefully be more efficient (in time complexity) than the brute-force approach. If we’re dealing with a list of inputs, I usually ask myself: is there a way to (in-place) sort the inputs (if they’re not already sorted) to achieve an O(n log n) runtime with O(1) space? Or is there a way of using a few variables/pointers while iterating to achieve an O(n) time and O(1) space solution?
- Avoid committing to any solution — leaving a little time to see if any other approaches to come to mind. Typically the current problem resembles another problem that you’ve solved and a technique used in that solved problem can be applied.
- Ask the interviewer what we’re optimizing for (usually runtime) and narrow down your set of solutions to a single one to code.
- Outline the structure of the solution (I tend do it on the side of the whiteboard) either with high level functions (input, purpose of the method, and its output) or the order of loops and conditions.
- Start writing code (slowly and carefully) that models the outline.
- Do a light pass code review of my solution making sure it is syntactically correct and not introducing idioms that utilize extra space/time (i.e., creating intermediate arrays or doing implicit passes through the entire array) that result in a different (possibly quadratic) runtime complexity than desired.
- Run through your code with normal and edge-case inputs — correcting any bugs in your solution.
- If there is a follow-up tweak to the original problem, think about how to reuse the previously implemented method(s) to implement the tweak.
- Apply the same principles of analysis from this list to the follow-up question’s solution.
This algorithm reinforces the idea that you should explore multiple solutions and their trade-offs before writing any code. Programming is about solving a problem accurately and efficiently; code is only an implementation of your solution.