What are the top 10 most popular dynamic programming problems among interviewers? - My articles - Publisher - Information Technology
Sunday, 2016-12-04, 5:15 PM
ebooks Programming Computer Science
Welcome Guest | RSS
Site menu
Section categories
My articles [23]
Main » Articles » My articles

What are the top 10 most popular dynamic programming problems among interviewers?
http://www.geeksforgeeks.org/tag/dynamic-programming/

http://people.csail.mit.edu/bdean/6.046/dp/

Following questions are the most popular dynamic programming problems for interviews :

  1. Given a matrix consisting of 0's and 1's, find the maximum size sub-matrix consisting of only 1's.
  2. Given an array containing both positive and negative integers, find the contiguous array with the maximum sum.
  3. Longest Increasing Subsequence - Find the length of the longest subsequence of a given sequence such that all the elements are sorted in increasing/non-decreasing order.
    There are many problems which reduce to the this problem such as box stacking and the building bridges. These days the interviewers expect an NLogN solution.
  4. Edit Distance - Given two strings and a set of operations Change (C), insert (I) and delete (D) , find minimum number of edits (operations) required to transform one string into another.
  5. 0/1 Knapsack Problem - A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith item weigh wi and is worth vi dollars. What items should thief take?
  6. Balanced Partition - You have a set of n integers each in the range 0 … K. Partition these integers into two subsets such that you minimize |S1 – S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.
  7. Coin Change - Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change?
  8. Longest Common Subsequence - Find the longest common subsequence of two strings A and B where the elements are letters from the two strings and they should be in the same order.
  9. Longest Palindromic Subsequence - The question is same as above but the subsequence should be palindromic as well.
  10. Minimum Number of Jumps - Given an array of integers where each element represents the maximum number of steps that can be made forward from that element, find the minimum number of jumps to reach the end of the array (starting from the first element).
Category: My articles | Added by: Sumrat (2013-02-20)
Views: 1859 | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Our poll
Rate my site
Total of answers: 152
Statistics

Total online: 1
Guests: 1
Users: 0
Login form