Jan 182017

The most difficult problems in Coding competitions and interviews of companies like Google, Microsoft etc. are from Dynamic Programming.

DP as an approach to problem solving is discussed in almost all algorithm books. But, in most of the books, DP, as a concept is lost behind the difficult problems.

For example, in one of the best algorithm books, Cormen, chapter of dynamic programming discuss complex examples like Matrix chain multiplication. Student get more absorbed in solving the complex problem rather than getting into the crux of the concept.

I think following steps may help in approaching a complex DP problem:

1. Master Recursion

The logic of DP and recursion is usually same. Recursion is relatively easy to develop solution. DP usually use the same logic (from recursion) and change it to solve the problem bottom-up. You can read the sample chapter of my book on recursion at the below link:


2. Decide on the cache

DP problems usually demonstrate optimal substructure property. It literally means that solution of a larger problem requires us to solve smaller problem of the same type (hence recursion was a good tool). Recursion, stores the intermediate results in the function call stack.

Since we are not using recursion, in most cases, we end up using a cache to store the intermediate results. This cache is usually an array. In most cases, if there are two dimensions in the problem (eg. if we are talking about a grid then there are two dimensions along x and y axis).

3. Solve bottom up

There is a cost associated with solving a problem in top-down (using either recursion or memoization). DP reduce that cost by computing the problem in a bottom-up manner. Before solving the problem using DP or before even learning DP approach, we must be well informed of the cost that we are going to reduce.

I wanted to compute 80th term of the Fibonacci series. I wrote the rampant recursive function,

int fib(int n){
   return (1==n || 2==n) ? 1 : fib(n-1) + fib(n-2);

and waited for the result. I wait… and wait… and wait…

With an 8GB RAM and an Intel i5 CPU, why is it taking so long? I terminated the process and tried computing the 40th term. It took about a second. I put a check and was shocked to find that the above recursive function was called 204,668,309 times while computing the 40th term.

More than 200 million times? Is it reporting function calls or scam of some government?

The Dynamic Programming solution computes 100th Fibonacci term in less than fraction of a second, with a single function call, taking linear time and constant extra memory.

A recursive solution, usually, neither pass all test cases in a coding competition, nor does it impress the interviewer in an interview of company like Google, Microsoft, etc.

The most difficult questions asked in competitions and interviews, are from dynamic programming. This book takes Dynamic Programming head-on. It first explain the concepts with simple examples and then deep dives into complex DP problems.

4. Practice, Practice and Practice

As they say, “Do not practice until you get it right, but keep practicing until you can’t get it wrong.

Once you understand the concept, then search the internet, There are lot of questions available online. Apply your understanding on each question.

It’s not a good practice to see the solution and remember it from the internet. Because whether it is a competition or an interview, chances are that you will get a question, that you have not done till now. Only, if you are hands-on with the concept, you will be able to solve it.

While solving any question, I suggest everyone to also go thru the not-so-good solutions. I usually recommend to try all the three solutions for a DP problem:

  • Recursive
  • Memoized
  • Bottom-up Dynamic Programming

It helps us appreciate the benefits of DP more by comparing it with not-so-optimized solutions.


May 102016

Given two strings of size m and n respectively, find the minimum number of operations required to transform one string into another. The following thee operations are allowed

  • Insert(pos, ch) – Insert a character at a position in the string.
  • Delete(position) – Delete a character from a position in the string.
  • Replace(position, character) – Replace a particular character with some other character at a position in the string.

For example, If input strings are ‘KITTEN‘ and ‘SITTING‘ then the edit distance between them is 3.

  1. kitten -> sitten (Replace)
  2. sitten -> sittin (Replace)
  3. sittin -> sitting (Insert)

It can be used in applications like auto spell correction to correct a wrong spelling and replace it with the nearest (minim distance) word.

Continue reading »

Apr 292016

Given an array of integers, write a function that returns true if it can be divided in two parts having equal sum. For example:

If Input array is {10, 20 , 30 , 5 , 40 , 50 , 40 , 15}
Output: true
Divide the array in two parts {0, 20, 30, 5, 40} and {50, 40, 15} both having sum = 105.

If Input array is {10, 20, 30, 5, 40, 50, 40, 10}
Output: False
Array cannot be divided in two parts having same sum.

Continue reading »

Aug 192012

Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example:

      Array               Maximum Sub-Array         sum 
-----------------------  -----------------------   ----
{5, 7, 12, 0, -8, 6}        {5, 7, 12}              24
{6, -2, -3, 4, -1, 10 }  {6, -2, -3, 4, -1, 10 }    14
{-1, -3, 4, -7, 0, 2}       {2}                     2
{1, -5, 2, -1, 3}           {2, -1, 3}              4

Note: If all elements are positive, then the result is sum of entire array. If all elements are -ve then result is zero.
Continue reading »