Programming Interview Problems: Dynamic Programming (with solutions in Python)
Leonardo Rossi
Programming Interview Problems: Dynamic Programming (with solutions in Python)
Preface
Over the last decade, many companies have adopted the FANG-style interview process for software engineer positions: programming questions that involve an algorithm design step, and often require competitive programming solving techniques.
The advantages and disadvantages of this style of interview questions are highly debated, and outside the scope of this book. What is important is that the questions that are asked pose serious challenges to candidates, thus require thorough preparation.
The class of problems that are by far the most challenging is dynamic programming . This is due to a combination of dynamic programming being rarely used in day-to-day work, and the difficulty of finding a solution in a short amount of time, when not having prior experience with this method.
This book presents 25 dynamic programming problems that are most commonly encountered in interviews, and several of their variants. For each problem, multiple solutions are given, including a gradual walkthrough that shows how one may reach the answer. The goal is not to memorize solutions, but to understand how they work and learn the fundamental techniques, such that new, previously unseen problems can be solved with ease.
The solutions are very detailed, showing example walkthrougs, verbal explanations of the solutions, and many diagrams and drawings. These were designed in a way that helps both verbal and visual learners grasp the material with ease. The code implementation usually comes last, accompanied by unit tests and complexity/performance analysis.
A particular focus has been put on code clarity and readability: during the interview, we are expected to write code as we would on the job. This means that the code must be tidy, with well-named variables, short functions that do one thing, modularity, comments describing why we do certain things etc. This is, sadly, unlike most other material on dynamic programming that one may find online, in competitive programming resources, or even in well-known algorithm design textbooks. In fact, the poor state of the material on this topic is the main reason I wrote this book.
I hope that you find this book useful for preparing to get the job you wish for. Whether you like the book or not, I would appreciate your feedback through a book review.
Good luck with your interviews!
General advice for the interview
Find out in advance what kind of questions will be asked. Usually, they are in one or more of the following categories: coding, algorithm design (with or without implementation), domain-specific questions, theoretical questions, behavioral questions, live coding, debugging, one-day assignments or pair programming. You should know what you need to prepare for.
For programming questions, do not jump directly to writing code, even if the solution looks obvious. First, ask clarification questions and go over some simple examples, to make sure you understand the requirements well. Then, you may sketch a solution and discuss it with the interviewer. Several iterations might be needed in case of correctness or performance issues. Only once they agree that the solution looks fine, proceed with implementing it.
Treat the interview questions not like problems, but real job assignments. Take them seriously and solve them thoroughly, like a professional.
Treat your interviewers as colleagues, with whom you must work together to solve the assignment. Shift into the mindset that you are already on the same team. Discuss and interact with them the same way you would with colleagues on the job.
Write tidy, clean codeas much as possible given the time you have. Try to follow typical coding style guidelines for your language. For Python, you can find good guidelines at www.python.org/dev/peps/pep-0008 and google.github.io/styleguide/pyguide.html.
Do not forget to ask about the size of the data your code needs to handlethis is important to determine the time complexity of your solution.
If you cannot find the fastest algorithm needed to solve the problem, propose a slower one. Sometimes you might get an idea (or a hint from the interviewer) to make it faster once you write it. But even if you do not, any solution is better than no solution.
Try to be quick in your answer. Interviewers usually plan to ask follow-up questions. If you do not have sufficient time left for these, your result may be poor, even if you answered the original question well.
The Fibonacci sequence
Return the n-th number in the Fibonacci sequence. The first two numbers in the Fibonacci sequence are equal to 1; any other number is equal to the sum of the preceding two numbers.
Example: for n = 6, the first 6 numbers of the sequence are [1, 1, 2, 3, 5, 8] so the result is 8.
Solution 1: brute force,
O(2n)
time
A straightforward solution is to implement the function recursively:
def fibonacci(n):
if n <= :
return
return fibonacci(n - ) + fibonacci(n - )
The above code is correct but too slow due to redundancies. We can see this if we add logging to the function:
import inspect
def stack_depth():
return len (inspect.getouterframes(inspect.currentframe())) -
def fibonacci(n):
print ( "{indent}fibonacci({n}) called" . format (
indent =" " * stack_depth(), n = n))
if n <= :
return
return fibonacci(n - ) + fibonacci(n - )
fibonacci()
We changed the code to print the argument passed to the fibonacci function. The message is indented by the call stack depth, so that we can see better which function call is causing which subsequent calls. Running the above code prints:
fibonacci(6) called
fibonacci(5) called
fibonacci(4) called
fibonacci(3) called
fibonacci(2) called
fibonacci(1) called
fibonacci(2) called
fibonacci(3) called
fibonacci(2) called
fibonacci(1) called
fibonacci(4) called
fibonacci(3) called
fibonacci(2) called
fibonacci(1) called
fibonacci(2) called
Thats a lot of calls! If we draw the call graph, we can see that its an almost full binary tree:
Notice that the height of the binary tree is n (in this case, 6). The tree is almost full, thus it has
O(2n)
nodes. Since each node represends a call of our function, our algorithm has exponential complexity.
Solution 2: dynamic programming, top-down
We can optimize the previous solution by avoiding redundant computations. These redundancies are visible in the call graph:
- fibonacci(4) is called twice, once by fibonacci(5) and once by fibonacci(6) ;
- fibonacci(3) is called 3 times;
- fibonacci(2) is called 5 times;
- fibonacci(1) is called 3 times.
It does not make sense to compute, for example, the 4-th Fibonacci number twice, since it does not change. We should compute it only once and cache the result.
Lets use a dictionary to store the cache:
fibonacci_cache = {}
def fibonacci(n):
if n <= :
return
if n not in fibonacci_cache:
fibonacci_cache[n] = fibonacci(n - ) + fibonacci(n - )
return fibonacci_cache[n]
The call graph of the optimized code looks like this:
