Dynamic Programming for coding interviews


In college, I used to write a simple code to compute fibonacci numbers:

int fib(int n)
  if(1==n || 2==n) 
    return 1; 
    return fib(n-1) + fib(n-2);

This is a recursive function. Now we have seen how bad recursion may be in this post. But here we are witnessing the overlapping subproblems. We have seen the memoized and DP version of fibonacci problem in this post. Just to understand the impact of DP, the above function is called, 204,668,309 times if n=40.

i.e To compute the 40th term, the function calls itself more than 200 million times.

This is because one problem is solved many times. And this is where we see the value of Dynamic Programming. DP is one of the most important approaches to problem solving. I think it is given much less weightage in our curriculum than it deserve. A student can easily score good marks in algorithms, even if he choose to skip DP.

In online competitions and in the interview of high end product based companies like Google, Microsoft, Amazon or Facebook, DP problems are seen to be one of the most difficult ones. It is difficult because DP uses the bottom-up approach, which is counter intuitive.

What makes DP even more difficult is that in the books of algorithms, there is just one chapter dedicated for DP. And that chapter tend to discuss complex problems while explaining DP. The problem is that students are lost in solving those complex problems rather than understanding DP as a concept and approach.

This book of mine takes very simple examples to explain DP approach and then once the concept is clear in the mind, it discusses strategy to solve a DP problem with lot of complex real life interview questions.

If you are a student or professional of Computer science, then this is the book for you.