Dynamic Programming Interview Questions

No. 03 - Maximum Sum of All Sub-arrays
A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n).
For example, in the array {1, -2, 3, 10, -4, 7, 2, -5}, its sub-array {3, 10, -4, 7, 2} has the maximum sum 18.

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Implement a function which gets the edit distance of two input strings. There are three types of edit operations: insertion, deletion and substitution. Edit distance is the minimal number of edit operations to modify a string from one to the other.

Please implement a function which gets the minimal number of coins, whose value is v1, v2, …, vn, to make change for an amount of money with value t. Any coin with value vi may duplicate for any times to make change.
For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.

There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

No. 49 - Longest Substring without Duplication
Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’.

No. 52 - Maximal Product when Cutting Rope
Given a rope with length n, how to cut the rope into m parts with length n[0], n[1], ...,n[m-1], in order to get the maximal product of n[0]*n[1]* ... *n[m-1]? We have to cut once at least. Additionally, the length of the whole length of the rope, as well as the length of each part, are in integer value.

A board has n*m cells, and there is a gift with some value (value is greater than 0) in every cell. You can get gifts starting from the top-left cell, and move right or down in each step, and finally reach the cell at the bottom-right cell. What’s the maximal value of gifts you can get from the board?


  1. Check this link also they are also having some amazing interview questions
    c# interview questions @ http://skillgun.com

  2. This comment has been removed by the author.

  3. Hello Harry,

    These are some very good list of dynamic problems that one might encounter during interview.

    We have a startup which helps the developers to find the job they are most suited for. Our goal is to help candidate skip the phone screening process by solving coding challenges through our platform.

    Would love to hear your thoughts on what we do.

    Thanks for taking a look!

  4. Nice Website...
    Hey JOIN now fblikesbot.com and Increase Facebook Likes your profile and websites.
    Increase Facebook Likes and check your website worth worth my websites
    its may be very beneficial for you also really

  5. Tks very much for your post.

    Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

    You also find all interview questions at link at the end of this post.

    Source: Interview Questions & Answers:

    Best rgs