Dynamic Programming: Formulas and Patterns.
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
boolean isMatch(String string, String pattern)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
Given an array arr[0 … n-1] containing n positive integers, a subsequence
of arr[] is called Bitonic if it is first increasing, then decreasing.
Write a function that takes an array as argument and returns the length of
the longest bitonic subsequence.
A sequence, sorted in increasing order is considered Bitonic with the
decreasing part as empty. Similarly, decreasing order sequence is considered
Bitonic with the increasing part as empty.
Examples:
Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)
Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)
Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)
Approach:
a. Find the max increasing subsequence from left to right.
b. find the max increasing subsequence from right to left.
c. max(left + right - 1) would be the ans.
//we are doing -1 because one element is counted twice - at intersection point of left & right.
Formula for max increasing subsequence.
if (A[i] < A[j]) {
T[j] = Max (T[j], 1 + T[i])
}
//j goes from i+1 to A.length;
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1 | 11 | 2 | 10 | 4 | 5 | 2 | 1 | |
| Left to Right | 1 | 2 | 2 | 3 | 3 | 4 | 2 | 1 |
| Right to Left | 1 | 5 | 2 | 4 | 3 | 3 | 2 | 1 |
| bitonic seq | 1 | 6 | 3 | 6 | 5 | 6 | 3 | 1 |
| max bitonic seq | 6 |
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Given an array of positive numbers, find the maximum sum of a subsequence
with the constraint that no 2 numbers in the sequence should be adjacent in
the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should
return 15 (sum of 3, 5 and 7).
public int maxSumIter(int [] A) {
int len = A.length;
int incl = A[0];
int excl = 0;
for (int i=1; i<len; i++) {
int tmp = incl;
incl = Math.max(incl, excl+A[i]);
excl = tmp;
}
return Math.max(incl, excl);
}
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| values | 4 | 1 | 1 | 4 | 2 | 1 |
| Inclusive | 4 | 4 | 5 | 8 | 8 | 9 |
| Exclusive | 0 | 4 | 4 | 5 | 8 | 8 |
Max Sum = max(inclusive, exclusive)
= max(9, 8)
= 9
- Time Complexity: O(n)
- Space Complexity: O(1)
Examples:
[2, 5, 3, 1, 7]
max sum: 12
[2, 10, 13, 4, 2, 15, 10]
max sum: 30
[5, 5, 10, 40, 50, 35]
max sum: 80
[5, 5, 10, 100, 10, 5]
max sum: 110
[3, 2, 7, 10]
max sum: 13
N pots, each with some number of gold coins, are arranged in a line.
You are playing a game against another player. You take turns picking a
pot of gold. You may pick a pot from either end of the line, remove the pot,
and keep the gold pieces. The player with the most gold at the end wins.
Develop a strategy for playing this game.
Formula:
for (int len=2; len<=size; len++) {
for (int i=0; i<=size-len; i++) {
int j = i + len - 1;
if (T[i+1][j].second + pots[i] > T[i][j-1].second + pots[j]) {
T[i][j].first = T[i+1][j].second + pots[i] ;
T[i][j].second = T[i+1][j].first;
T[i][j].pick = i;
} else {
T[i][j].first = T[i][j-1].second + pots[j];
T[i][j].second = T[i][j-1].first;
T[i][j].pick = j;
}
}
}
| Index | 0 | 1 | 2 | 3 | ||
| gold | 3 | 9 | 1 | 2 | ||
| 0 | 3 | (3,0) | (9,3) | (4,9) | (11,4) | <- ans |
| 1 | 9 | (9,0) | (9,1) | (10,2) | ||
| 2 | 1 | (1,0) | (2,1) | |||
| 3 | 2 | (2,0) |
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Given three strings A, B and C. Write a function that checks whether C is an
interleaving of A and B. C is said to be interleaving A and B, if it contains
all characters of A and B and order of all characters in individual strings is
preserved.
A = "XXY"
B = "XXZ"
C = "XXXXZY"
output: True.
Formula:
if (B[i] == C[i+j]) {
T[i][j] = T[i][j-1]
} else if (A[j] == C[i+j]) {
T[i][j] = T[i-1][j]
} else {
T[i][j] = false;
}
| 0 | X | X | Y | |
| 0 | T | T | T | F |
| X | T | T | T | F |
| X | T | T | T | F |
| Z | F | F | T | T(ans) |
- Time Complexity: O(n * m)
- Space Complexity: O(n * m)
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1
Formula:
if (M[i][j] == 0) {
T[i][j] = 0
} else {
T[i][j] = 1 + Min(T[i][j-1], T[i-1][j-1], T[i-1][j])
}
| M[][] | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | |
| T[][] | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 1 | 0 | |
| 1 | 1 | 2 | 2 | 0 | |
| 1 | 2 | 2 | 3 (ans) | 1 | |
| 0 | 0 | 0 | 0 | 0 |
- Time Complexity: O(row*col)
- Space Complexity: O(row*col)
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time
(ie, you must sell the stock before you buy again).
Formula:
T[i][j] = Max {
T[i][j-1], //not transacting on day j
T[i-1][m] + price[j] - price[m] for m = 0...j-1;
};
| index -> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| prices -> | 2 | 5 | 7 | 1 | 4 | 3 | 1 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 3 | 5 | 5 | 5 | 5 | 5 | 5 |
| 2 | 0 | 3 | 5 | 5 | 8 | 8 | 8 | 8 |
| 3 | 0 | 3 | 5 | 5 | 8 | 8 | 8 | 10 (ans) |
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Say you have an array for which the ith element is the price of a given stock
on day i.
Design an algorithm to find the maximum profit. You may complete at most
two transactions.
Note:
A transaction is a buy & a sell. You may not engage in multiple transactions
at the same time (ie, you must sell the stock before you buy again).
We use left[i] to track the maximum profit for transactions before i, and use right[i] to track the maximum profit for transactions after i. You can use the following example to understand the Java solution:
Prices: 1 4 5 7 6 3 2 9
left = [0, 3, 4, 6, 6, 6, 6, 8]
right= [8, 7, 7, 7, 7, 7, 7, 0]
The maximum profit = 13
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions
as you like (ie, buy one and sell one share of the stock multiple times). However,
you may not engage in multiple transactions at the same time (ie, you must sell the
stock before you buy again).
public int maxProfit(int[] prices) {
int profit = 0;
for(int i=1; i<prices.length; i++){
int diff = prices[i]-prices[i-1];
if(diff > 0){
profit += diff;
}
}
return profit;
}
Buy Sell - unlimited Transaction
- Time Complexity: O(n)
- Space Complexity: O(1)
Say you have an array for which the ith element is the price of a given
stock on day i.
If you were only permitted to complete at most one transaction
(ie, buy one and sell one share of the stock), design an algorithm
to find the maximum profit.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| prices | 2 | 5 | 7 | 1 | 4 | 3 | 1 | 3 |
| Max profit | null | 3 | 5 | 5 | 5 | 5 | 5 | 5 |
| min so far | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
min = prices[0];
profit = Integer.MIN_VALUE;
for (int i=1; i<prices.length; i++) {
profit = Max(profit, prices[i] - min);
min = Min(min, prices[i]);
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Given an array of n positive integers. Write a program to find the sum of
maximum sum subsequence of the given array such that the intgers in the subsequence
are sorted in increasing order. For example, if input is {1, 101, 2, 3, 100, 4, 5},
then output should be 106 (1 + 2 + 3 + 100), if the input array is {3, 4, 5, 10},
then output should be 22 (3 + 4 + 5 + 10) and if the input array is {10, 5, 4, 3},
then output should be 10
Formula:
if (A[i] < A[j]) {
T[j] = T[i] + A[j]
Parent[j] = i;
}
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 4 | 6 | 1 | 3 | 8 | 4 | 6 | |
| MSIS0 | 4 | 6 | 1 | 3 | 8 | 4 | 6 |
| Parent0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| MSIS1 | 4 | 10 | 1 | 3 | 12 | 4 | 6 |
| Parent1 | -1 | 0 | -1 | -1 | 0 | -1 | 0 |
| MSIS2 | 4 | 10 | 1 | 3 | 18 | 4 | 6 |
| Parent2 | -1 | 0 | -1 | -1 | 1 | -1 | 0 |
| MSIS3 | 4 | 10 | 1 | 4 | 18 | 5 | 7 |
| Parent3 | -1 | 0 | -1 | 2 | 1 | 2 | 2 |
| MSIS4 | 4 | 10 | 1 | 4 | 18 | 8 | 10 |
| Parent4 | -1 | 0 | -1 | 2 | 1 | 3 | 3 |
| MSIS5 | 4 | 10 | 1 | 4 | 18 | 8 | 10 |
| Parent5 | -1 | 0 | -1 | 2 | 1 | 3 | 3 |
| MSIS6 | 4 | 10 | 1 | 4 | 18 (ans) | 8 | 14 |
| Parent6 | -1 | 0 | -1 | 2 | 1 | 3 | 5 |
| seq -> | 4 | 6 | 8 | ||||
| index | 0 | 1 | 4 |
public int maxSumSubsequence(int [] A) {
if (A == null) {
return -1;
}
if (A.length < 1) {
return -1;
}
int len = A.length;
int [] T = new int[len];
for (int i = 0; i < T.length; i++) {
T[i] = A[i];
}
for(int i=1; i<len; i++) {
for (int j=0; j<i; j++) {
if (A[j] < A[i]) {
T[i] = Math.max(T[i], T[j] + A[i]);
}
}
}
int max = Integer.MIN_VALUE;
for (Integer x: T) {
if (x > max) {
max = x;
}
}
return max;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Formula:
if (isPalindrome(S[i...j]) {
T[i][j] = 0;
} else {
T[i][j] = Min (T[i][k] + T[k+1][j]) //for i <= k < j
}
| 0 | 1 | 2 | 3 | 4 | ||
|---|---|---|---|---|---|---|
| a | x | y | x | b | ||
| 0 | a | 0 | 1 | 2 | 1 | 2 (ans) |
| 1 | x | 0 | 1 | 0 | 1 | |
| 2 | y | 0 | 1 | 2 | ||
| 3 | x | 0 | 1 | |||
| 4 | b | 0 |
public int palindromicPartition(char [] input) {
int size = input.length;
int [][] T = new int[size][size];
for (int i=0; i<size; i++) {
Arrays.fill(T[i], Integer.MAX_VALUE);
T[i][i] = 0;
}
for (int len=1; len<=size; len++) {
for (int i=0; i<size-len+1; i++) {
int j = i + len - 1;
if (isPalindrome(input, i, j)) {
T[i][j] = 0;
continue;
}
int val = Integer.MAX_VALUE;
for (int k=i+1; k<=j; k++) {
val = Math.min(val, 1 + (T[i][k-1] + T[k][j]));
}
T[i][j] = val;
}
}
[Palindrome Partition] (https://github.com/mbhushan/injava/blob/master/DP_PalindromicPartition/src/PalindromicPartition.java)
- Time Complexity: O(n^3)
- Space Complexity: O(n^2)
Given a 2 dimensional matrix, find minimum cost path to reach bottom right
from top left provided you can only from down and right.
Formula:
T[0][0] = M[0][0]
First Row:
T[0][i] = T[0][i-1] + M[0][i]
First Col:
T[i][0] = T[i-1][0] + M[i][0]
Formula:
For (int i=1; i<row; i++) {
For (int j=1; j<col; j++) {
T[i][j] = M[i][j] + Math.min(T[i-1][j], T[i][j-1], T[i-1][j-1])
}
}
| input -> | 1 | 2 | 3 |
|---|---|---|---|
| 4 | 8 | 2 | |
| 1 | 5 | 3 | |
| T [][] -> | 1 | 3 | 6 |
| 5 | 9 | 5 | |
| 6 | 10 | 8 (ans) |
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Given a string and a dictionary, return true if string can be split into multiple
words such that each word is in dictionary. If not return false
DP Formula:
For every length (len=1; len<=len(str)) check if substring as a whole is part of dictionary
or there is a split point k where there are 2 strings which are part of
if( input[i...j] belongs in dictionary) DP[i][j] = i
} else{
DP[i][j] = k if (DP[i][k-1] != F && DP[k][j] != F)
}
In the below DP table,
DP[i][j] = T(x) means we can form the word of characters string[i...j] by splitting it at x position,
So string[i..x-1] & string[x...j] forms the valid string (you can find the embedded strings by referring
to the DP table, see code below:
int start = 0;
int end = dp[0][n-1];
List<String> result = new ArrayList<String>();
while (start != end) {
String buff = text.substring(start, end);
result.add(buff);
start = end;
end = dp[end][n-1];
if (start == end) {
result.add(text.substring(start, n));
}
}
return result.toString();
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||
|---|---|---|---|---|---|---|---|---|---|---|
| t | h | i | s | i | s | m | e | |||
| 0 | t | F | F | F | T(0) | T(4) | T(4) | F | T(4) | |
| 1 | h | F | T(1) | T(1) | T(4) | T(3) | F | T(4) | ||
| 2 | i | T | T(2) | T(4) | T(4) | F | T(4) | |||
| 3 | s | F | F | T(3) | F | T(6) | ||||
| 4 | i | T | T(4) | F | T(6) | |||||
| 5 | s | F | F | F | ||||||
| 6 | m | F | T(6) | |||||||
| 7 | e | F | ||||||||
| dictionary -> | this | is | me | it | in | my | i | hi | his | sis |
public String wordBreakDP(String text) {
if (text == null || text.length() < 1) {
return new String(text);
}
int n = text.length();
int [][] dp = new int[n][n];
for (int i=0; i<n; i++) {
Arrays.fill(dp[i], -1);
}
for (int len=1; len<=n; len++) {
for (int i=0; i<n-len+1; i++) {
int j = i + len -1;
String buff = text.substring(i, j+1);
if (dict.contains(buff)) {
dp[i][j] = i;
continue;
}
for (int k=i+1; k<=j; k++) {
if (dp[i][k-1] != -1 && dp[k][j] != -1) {
dp[i][j] = k;
break;
}
}
}
}
if (dp[0][n-1] != -1) {
System.out.println("word break possible!");
} else {
System.out.println("word break NOT possible!");
return null;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Given an array, find minimum number to jumps to reach end of array, given you
can jump at max as much as value at position in array.
Input:
A [] = {2, 3, 1, 1, 2, 4, 2, 0, 1, 1}
Formula:
// i goes from 0 to A.len-1;
// j goes from i+1 to A.len-1;
if (A[i] + i >= j) {
jump[j] = max (jump[j], 1 + jump[i])
}
public int minJumps(int [] A) {
int [] jumpNums = new int[A.length];
int [] jumpIndex = new int[A.length];
for (int i=0; i<A.length; i++) {
jumpIndex[i] = i;
}
Arrays.fill(jumpNums, Integer.MAX_VALUE);
jumpNums[0] = 0;
for (int i=1; i<A.length; i++) {
for (int j=0; j<i; j++) {
if (A[j] + j >= i) {
if (jumpNums[i] > 1 + jumpNums[j]) {
jumpNums[i] = 1 + jumpNums[j];
jumpIndex[i] = j;
}
}
}
}
| Indexes | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Jump Values | 2 | 3 | 1 | 1 | 2 | 4 | 2 | 0 | 1 | 1 |
| Max Jump (i=0) | 0 | 1 | 1 | inf | inf | inf | inf | inf | inf | inf |
| Actual Jump (i=0) | 0 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| Max Jump (i=1) | 0 | 1 | 1 | 2 | 2 | inf | inf | inf | inf | inf |
| Actual Jump (i=1) | 0 | 0 | 0 | 1 | 1 | -1 | -1 | -1 | -1 | -1 |
| Max Jump (i=2) | 0 | 1 | 1 | 2 | 2 | inf | inf | inf | inf | inf |
| Actual Jump (i=2) | 0 | 0 | 0 | 1 | 1 | -1 | -1 | -1 | -1 | -1 |
| Max Jump (i=3) | 0 | 1 | 1 | 2 | 2 | inf | inf | inf | inf | inf |
| Actual Jump (i=3) | 0 | 0 | 0 | 1 | 1 | -1 | -1 | -1 | -1 | -1 |
| Max Jump (i=4) | 0 | 1 | 1 | 2 | 2 | 3 | 3 | inf | inf | inf |
| Actual Jump (i=4) | 0 | 0 | 0 | 1 | 1 | 4 | 4 | inf | inf | inf |
| Max Jump (i=5) | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 |
| Actual Jump (i=5) | 0 | 0 | 0 | 1 | 1 | 4 | 4 | 5 | 5 | 5 |
| Max Jump (i=6) | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 (ans) |
| Actual Jump (i=6) | 0 | 0 | 0 | 1 | 1 | 4 | 4 | 5 | 5 | 5 |
I7, I8 and I9 doesnt change the state, so those iterations are not mentioned above.
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Given a sequence of words, and a limit on the number of characters that can be
put in one line (line width). Put line breaks in the given sequence such that
the lines are printed neatly. Assume that the length of each word is smaller
than the line width.
The extra spaces includes spaces put at the end of every line except the last one.
The problem is to minimize the following total cost.
Cost of a line = (Number of extra spaces in the line)^2
Total Cost = Sum of costs for all lines
Text = "this is a cool problem to solve"
width = 10
Possible arrangement:
this is 3 (extra space)
a cool 4 (extra space)
problem 3 (extra space)
to solve 2 (extra space)
Total cost = (3^2) + (4^2) + (3^2) + (2^2)
= 9 + 16 + 9 + 4
= 38
Formula:
M[i] = M[j] + C[j+1][i]
C[][] is the cost matrix below.
M[] is the min cost array.
Indices keeps track of the split indices.
| this | is | a | cool | problem | to | solve | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| 0 | 36 | 9 | 1 | inf | inf | inf | inf | |
| 1 | 64 | 36 | 1 | inf | inf | inf | ||
| 2 | 81 | 16 | inf | inf | inf | |||
| 3 | 36 | inf | inf | inf | ||||
| 4 | 9 | 0 | inf | |||||
| 5 | 64 | 4 | ||||||
| 6 | 25 | |||||||
| Width | 10 | |||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Min Cost | 36 | 9 | 1 | 25 | 34 | 25 | 38 | <- final cost |
| Indices | 0 | 0 | 2 | 2 | 4 | 4 | 5 | |
| 0-1 | this | is | ||||||
| 2-3 | a | cool | ||||||
| 4-4 | Problem | |||||||
| 5-6 | to | Solve |
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Given a 2D matrix of 0s and 1s, find maximum size rectangle of all 1s in this matrix.
Maintain a temp array of same size as number of columns.
Copy first row to this temp array and find largest rectangular area
for histogram. Then keep adding elements of next row to this temp
array if they are not zero. If they are zero then put zero there.
Every time calculate max area in histogram.
MAX AREA IN HISTOGRAM.
* If stack is empty or A[index] >= stack.peek(), push *index* into stack.
* else keep popping from stack while A[stack.peek()] > A[index]
* While removing value from stack calculate area as follows:
Max Histogram Formula:
if (stack.isEmpty()) {
area = input[top] * i;
} else {
area = input[top] * (i - stack.peek() - 1)
}
maxArea = Math.max(maxArea, area);
| c0 | c1 | c2 | c3 | c4 | c5 | Max Area (based on histogram area) | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| r0 | 1 | 0 | 0 | 1 | 1 | 1 | sum(r0,r0) | 1 | 0 | 0 | 1 | 1 | 1 | 3 |
| r1 | 1 | 0 | 1 | 1 | 0 | 1 | sum(r0,r1) | 1 | 0 | 1 | 2 | 0 | 2 | 2 |
| r2 | 0 | 1 | 1 | 1 | 1 | 1 | sum(r0,r2) | 0 | 1 | 2 | 3 | 1 | 3 | 5 |
| r3 | 0 | 0 | 1 | 1 | 1 | 1 | sum(r0,r3) | 0 | 0 | 3 | 4 | 2 | 4 | 8 |
| Ans = 8 |
- Time Complexity: (row * col)
- Space Complexity: O(row)
You are given a set of n types of rectangular 3-D boxes, where the i^th box has
height h(i), width w(i) and depth d(i) (all real numbers). You want to create a
stack of boxes which is as tall as possible, but you can only stack a box on top of
another box if the dimensions of the 2-D base of the lower box are each strictly larger
than those of the 2-D base of the higher box. Of course, you can rotate a box so that
any side functions as its base. It is also allowable to use multiple instances of the
same type of box.
Boxes = (1, 2, 4) and (3, 2, 5)
Get All Rotation of boxes and sort them by base area, in decreasing order.
Apply the LIS (longest increasing subsequence) algorithm on the list of
sorted boxes based on condition of
len(i) > len(j) && width(i) > width(j) where j < i.
** in the below matrix:
I0, I1, I2 etc -> Iteration 0, Iteration 1 etc.
P0, P1, P2 etc -> Parent data Iterations 0, 1, 2 etc.
I0,P0 col pairs represent the iteration of LIS algorithm on the (len, wid, ht) col.
| Index | (len, wid, ht) | Max Height | I0 | P0 | I1 | P1 | I2 | P2 | I3 | P3 | I4 | P4 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | (5,3,2) | 2 | 2 | -1 | 2 | -1 | 2 | -1 | 2 | -1 | 2 | -1 |
| 1 | (5,2,3) | 3 | 3 | -1 | 3 | -1 | 3 | -1 | 3 | -1 | 3 | -1 |
| 2 | (4,2,1) | 1 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 |
| 3 | (3,2,5) | 5 | 7 | 0 | 7 | 0 | 7 | 0 | 7 | 0 | 7 | 0 |
| 4 | (4,1,2) | 2 | 4 | 0 | 5 | 1 | 5 | 1 | 5 | 1 | 5 | 1 |
| 5 | (2,1,4) | 4 | 6 | 0 | 7 | 1 | 7 | 2 | 11 | 3 | 11 | 3 |
| Max Ht | ||||||||||||
| Final Ans: | (2,1,4) | |||||||||||
| (3,2,5) | ||||||||||||
| (5,3,2) |
public int maxHeight(int [][] input) {
Box [] boxes = createBoxes(input);
Arrays.sort(boxes, new BoxComparator());
printBoxes(boxes);
int [] height = new int[boxes.length];
int [] result = new int[boxes.length];
for (int i=0; i<boxes.length; i++) {
height[i] = boxes[i].height;
result[i] = i;
}
for (int i=1; i<boxes.length; i++) {
for (int j=0; j<i; j++) {
if ((boxes[i].length < boxes[j].length) && (boxes[i].width < boxes[j].width)) {
height[i] = Math.max(height[i], + height[j]);
result[i] = j;
}
}
}
int maxHeight = 0;
int index = 0;
for (int i=0; i<height.length; i++) {
if (height[i] > maxHeight) {
maxHeight = height[i];
index = i;
}
}
ArrayList<Box> boxList = new ArrayList<Box>();
boxList.add(boxes[index]);
while (index != result[index]) {
index = result[index];
boxList.add(boxes[index]);
}
System.out.println("list of final boxes are: ");
for (Box box: boxList) {
System.out.println(box.toString());
}
return maxHeight;
}
- Time Complexity: O(n^2)
####(16). Longest Common Substring.
Given two strings, find longest common substring between them.
String X = abcdaf
String Y = zbcdf
Longest common substring: 3 (bcd)
Formula:
if (Y[i] == X[j]) {
T[i][j] = T[i-1][j-1] + 1;
} else {
T[i][j] = 0;
}
| 0 | a | b | c | d | a | f | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| z | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| c | 0 | 0 | 0 | 2 | 0 | 0 | 0 |
| d | 0 | 0 | 0 | 0 | 3 | 0 | 0 |
| f | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
- Time Complexity: O(n * m)
- Space Complexity: O(n * m)
Given two strings, find longest common subsequence between them.
String Y = abcdaf
String X = zbcdf
LCS = bcdf (len -> 4)
Formula:
if (X[i] == Y[j]) {
T[i][j] = T[i-1][j-1] + 1;
} else {
T[i][j] = Max(T[i-1][j], T[i][j-1])
}
| 0 | a | b | c | d | a | f | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| z | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| c | 0 | 0 | 1 | 2 | 2 | 2 | 2 |
| d | 0 | 0 | 1 | 2 | 3 | 3 | 3 |
| f | 0 | 0 | 1 | 2 | 3 | 3 | 4 |
- Time Complexity: O(n * m)
- Space Complexity: O(n * m)
Given a 2D array, find the maximum sum subarray in it. For example, in
the following 2D array, the maximum sum subarray is highlighted with blue
rectangle and sum of this subarray is 29.
This problem is mainly an extension of Largest Sum Contiguous Subarray for 1D array.
public class MaxRectangleMatrix {
public static void main(String[] args) {
MaxRectangleMatrix mrm = new MaxRectangleMatrix();
//int [] A = {-2, -3, 4, -1, -2, 1, 5, -3};
//int [] A = {2, 0, 2, -3};
//KadaneResult kr = mrm.kadane(A);
//System.out.println(kr.toString());
int [][] M = {
{ 2, 1, -3, -4, 5},
{ 0, 6, 3, 4, 1},
{ 2, -2, -1, 4, -5},
{-3, 3, 1, 0, 3}
};
Result result = mrm.maxRectangleInMatrix(M);
System.out.println(result.toString());
}
public Result maxRectangleInMatrix(int [][] M) {
int maxSum = 0;
int leftIndex = 0;
int rightIndex = 0;
int up = 0;
int down = 0;
int row = M.length;
int col = M[0].length;
for (int left = 0; left<col; left++) {
int [] aux = new int[row];
for (int right = left; right<col; right++) {
for (int i=0; i<row; i++) {
aux[i] += M[i][right];
}
KadaneResult kr = kadane(aux);
if (kr.maxSum > maxSum) {
maxSum = kr.maxSum;
up = kr.start;
down = kr.end;
leftIndex = left;
rightIndex = right;
}
}
}
Result result = new Result(maxSum, leftIndex, rightIndex, up, down);
return result;
}
public KadaneResult kadane(int [] A) {
int maxSum = 0;
int start = 0;
int end = 0;
int runningSum = 0;
for (int i=0; i<A.length; i++) {
runningSum += A[i];
if (runningSum > maxSum) {
maxSum = runningSum;
end = i;
}
if (runningSum < 0) {
runningSum = 0;
start = i+1;
}
}
KadaneResult result = new KadaneResult(maxSum, start, end);
return result;
}
}
class Result {
int maxSum;
int left;
int right;
int up;
int down;
public Result(int maxSum, int left, int right, int up, int down) {
this.maxSum = maxSum;
this.left = left;
this.right = right;
this.up = up;
this.down = down;
}
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("[max sum: " + maxSum + ", ");
sb.append("left index: " + left + ", ");
sb.append("right index: " + right + ", ");
sb.append("up index: " + up + ", ");
sb.append("down index: " + down + "]");
return sb.toString();
}
}
class KadaneResult {
int maxSum;
int start;
int end;
public KadaneResult(int maxSum, int start, int end) {
this.maxSum = maxSum;
this.start = start;
this.end = end;
}
public String toString() {
String result = "[maxSum: " + maxSum +", start Index: " + start + ", end index: " + end +"]";
return result;
}
}
- Time complexity of this algorithm is O(row * col * col)
- Space complexity of this algorithm is O(row)
Given certain jobs with start and end time and amount you make on finishing the job, find the maximum value you can make by scheduling jobs in non-overlapping way.
Formula:
Jobs [] = {(1,3), (2,5), (4,6), (6,7), (5,8), (7,9)};
Weights = {5, 6, 5, 4, 11, 2};
for (int i=0; i<jobs.len; i++) {
for (int j=i+1; j<jobs.len; j++) {
if (!overlap(jobs[i], jobs[j]) {
values[i] = Max (value[j], value[i] + weights[j]);
parent[j] = i;
}
}
}
I0 = Iteration 0
I1 = Iteration 1
etc..
| Index -> | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Jobs -> | (1, 3) | (2, 5) | (4, 6) | (6, 7) | (5, 8) | (7, 9) |
| weights -> | 5 | 6 | 5 | 4 | 11 | 2 |
| Iterations 0 | 5 | 6 | 10 | 9 | 16 | 7 |
| I1 | 5 | 6 | 10 | 10 | 17 | 8 |
| I2 | 5 | 6 | 10 | 14 | 17 | 12 |
| I3 | 5 | 6 | 10 | 14 | 17 | 16 |
| I4 | 5 | 6 | 10 | 14 | 17 | 16 |
| Parents | -1 | -1 | -1 | -1 | -1 | -1 |
| I0 | -1 | -1 | 0 | 0 | 0 | 0 |
| I1 | -1 | -1 | 0 | 1 | 1 | 1 |
| I2 | -1 | -1 | 0 | 2 | 1 | 2 |
| I4 | -1 | -1 | 0 | 2 | 1 | 3 |
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Given a rod of length n inches and an array of prices that contains prices of
all pieces of size smaller than n. Determine the maximum value obtainable by
cutting up the rod and selling the pieces. For example, if length of the rod
is 8 and the values of different pieces are given as following, then the maximum
obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20
And if the prices are as following, then the maximum obtainable value is 24
(by cutting in eight pieces of length 1)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20
Formula:
j <- rod length
len(i) <- rod of len i
val(i) <- value of rod of len i
if (j >= i) {
T[i][j] = Max (
T[i-1][j], T[i][j-len(i)] + val(i);
)
} else {
T[i][j] = T[i-1][j];
}
Example:
len [] = {1, 2, 3, 4};
prices [] = {2, 5, 7, 8};
target len = 5;
| len(price) | 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|---|
| 1 (2) | 0 | 2 | 4 | 6 | 8 | 10 | |
| 2 (5) | 0 | 2 | 5 | 7 | 10 | 12 | |
| 3 (7) | 0 | 2 | 5 | 7 | 10 | 12 | |
| 4 (8) | 0 | 2 | 5 | 7 | 10 | 12 | <- max profit |
- Time Complexity: O(len * size(rods))
- Space Complexity: O(len * size(rods))
Given some number of floors and some number of eggs, what is the minimum
number of attempts it will take to find out from which floor egg will break.
Formula:
i <- egg
j <- floor
if (i > j) { //eggs > floors
T[i][j] = T[i-1][j]
} else {
// Min ( 1 + Max(Break case, No Break case) for all k in range of [1, j] )
T[i][j] = 1 + Min (
Max (T[i-1][k-1], T[i][j-k] // 1 <= k <= j;
);
}
public int calculate(int eggs, int floors) {
int T[][] = new int[eggs + 1][floors + 1];
int c = 0;
for (int i = 0; i <= floors; i++) {
T[1][i] = i;
}
for (int e = 2; e <= eggs; e++) {
for (int f = 1; f <= floors; f++) {
T[e][f] = Integer.MAX_VALUE;
for (int k = 1; k <= f; k++) {
c = 1 + Math.max(T[e - 1][k - 1], T[e][f - k]);
if (c < T[e][f]) {
T[e][f] = c;
}
}
}
}
return T[eggs][floors];
}
| (egg, floor) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
- Time Complexity: (eggs * floors * floors)
- Space Complexity: (eggs * floors)
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? The order of coins doesn’t matter.
For example,
for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},
{1,1,2},{2,2},{1,3}. So output should be 4.
For N = 10 and S = {2, 5, 3, 6},
there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
So the output should be 5.
Example:
coins[] = {2, 3, 4, 5}
total = 10;
*** please refer below matrix for trace with DP formula.
Formula:
j <- column
coins(i) <- row
If (j >= coins[i]) {
T[i][j] = T[i-1][j] + T[i][j - coins[i]]);
} else {
T[i][j] = T[i-1][j]
}
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| 3 | 1 | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2 | 2 | |
| 4 | 1 | 0 | 1 | 1 | 2 | 1 | 3 | 2 | 4 | 3 | 5 | |
| 5 | 1 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 5 | 5 | 7 | <- Total Ways |
- Time Complexity: O(Total * len(coins))
- Space Complexity: O(Total * len(coins))
Given a sequence, find the length of the longest palindromic subsequence in it.
For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as
“BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are
also palindromic subsequences of the given sequence, but not the longest ones.
Formula:
for (int len=2; len<=size(S); len++) {
for (int i=0; i<=size(S)-len; i++) {
int j = i + len - 1;
if (S[i] == S[j]) {
T[i][j] = Max (T[i][j], 2 + T[i+1][j-1])
} else {
T[i][j] = Max (T[i][j], T[i+1][j], T[i][j-1])
}
}
}
| Indexes | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Char | B | B | A | B | C | B | C | A | B | ||
| 0 | B | 1 | 2 | 2 | 3 | 3 | 5 | 5 | 5 | 7 | <- longest palindrome |
| 1 | B | 1 | 1 | 3 | 3 | 5 | 5 | 5 | 7 | ||
| 2 | A | 1 | 1 | 1 | 3 | 3 | 5 | 5 | |||
| 3 | B | 1 | 1 | 3 | 3 | 3 | 5 | ||||
| 4 | C | 1 | 1 | 3 | 3 | 3 | |||||
| 5 | B | 1 | 1 | 1 | 3 | ||||||
| 6 | C | 1 | 1 | 1 | |||||||
| 7 | A | 1 | 1 | ||||||||
| 8 | B | 1 |
public int maxPalindromicSubsequence(int [] A) {
if (A == null || A.length < 1) {
return 0;
}
int [][] dp = new int[A.length][A.length];
for (int i=0; i<A.length; i++) {
dp[i][i] = 1;
}
for (int len=2; len<=A.length; len++) {
for (int i=0; i<=A.length-len; i++) {
int j = i + len -1;
if (A[i] == A[j]) {
dp[i][j] = Math.max(dp[i][j], 2 + dp[i+1][j-1]);
} else {
dp[i][j] = Math.max(dp[i][j], dp[i+1][j]);
dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
}
}
}
return dp[0][A.length-1];
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Given two strings A & B and operations edit, delete and add, how many minimum
operations would it take to convert string B to string A.
Formula:
if (A[i] == B[j]) {
T[i][j] = T[i-1][j-1]
} else {
T[i][j] = Min (T[i-1][j-1], T[i-1][j], T[i][j-1]) + 1
}
Example Strings:
A = COMMITER
B = COMPUTERS
Min Edit Distance (A, B) = 3
| Indexes | 0 | C | O | M | P | U | T | E | R | S |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| C | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| O | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| M | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| M | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| I | 5 | 4 | 3 | 2 | 2 | 2 | 3 | 4 | 5 | 6 |
| T | 6 | 5 | 4 | 3 | 3 | 3 | 2 | 3 | 4 | 5 |
| E | 7 | 6 | 5 | 4 | 4 | 4 | 3 | 2 | 3 | 4 |
| R | 8 | 7 | 6 | 5 | 5 | 5 | 4 | 3 | 2 | 3 |
- Time complexity is O(m*n)
- Space complexity is O(m*n)
Given keys and frequency at which these keys are searched, how would you create
binary search tree from these keys such that cost of searching is minimum.
Input:
Keys[] = {10, 12, 16, 21}
frequency [] = {4, 2, 6, 3}
We take the bottoms up approach here and keep track of the cost of BST of
len=1 to len=size(A).
T[i][j] = Min (
T[i][j],
sum + min(T[i][k-1] + T[k+1][j]) for all i <= k <= j
//where sum is Sum(freqency[i] .. frequency[j])
);
- T[i][j] = cost(x) means total cost of BST with x as root
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Keys | 10 | 12 | 16 | 21 |
| Frequency | 4 | 2 | 6 | 3 |
| Index | 0 | 1 | 2 | 3 |
| 0 | 4 | 8(0) | 20(2) | 26(2) |
| 1 | 2 | 10(2) | 16(2) | |
| 2 | 6 | 12(2) | ||
| 3 | 3 |
//Formula and code below:
public int minCost(int [] keys, int [] freq) {
int [][] T = new int[keys.length][keys.length];
for(int i=0; i < T.length; i++){
T[i][i] = freq[i];
}
for (int L=2; L <= keys.length; L++) {
for (int i=0; i<=keys.length-L; i++) {
int j = i + L -1;
T[i][j] = Integer.MAX_VALUE;
int sum = getSum(freq, i, j);
for (int k=i; k<=j; k++) {
int val = sum + (k-1 < i? 0: T[i][k-1]) +
(k+1 > j ? 0: T[k+1][j]);
if (val < T[i][j]) {
T[i][j] = val;
}
}
}
}
return T[0][keys.length-1];
}
private int getSum(int [] freq, int i, int j) {
int total = 0;
for (int x=i; x<=j; x++) {
total += freq[x];
}
return total;
}
- Time Complexity: O(n^3)
- Space Complexity: O(n^2)
Find the longest increasing subsequence in an array.
Input:
int [] A = {3, 4, -1, 0, 6, 2, 3}
Output:
LIS: 4 (-1, 0, 2, 3)
Formula:
if (A[j] < A[i]) {
T[i] = Max (T[i], T[j] + 1);
}
Time complexity: O(n^2)
Space complexity: O(n)
int [] T = new int[A.length];
for (int i=0; i<T.length; i++) {
T[i] = 1;
}
for (int i=1; i<A.length; i++) {
for (int j=0; j<i; j++) {
if (A[j] < A[i]) {
T[i] = Math.max(T[i], T[j] + 1);
}
}
}
| Input | 3 | 4 | -1 | 0 | 6 | 2 | 3 | ||
|---|---|---|---|---|---|---|---|---|---|
| LIS - iteration0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||
| LIS - iteration1 | 1 | 2 | 1 | 1 | 2 | 1 | 1 | j=0 | i=len(A) |
| LIS - iteration2 | 1 | 2 | 1 | 1 | 3 | 1 | 1 | j=1 | i=len(A) |
| LIS - iteration3 | 1 | 2 | 1 | 2 | 3 | 2 | 2 | j=2 | i=len(A) |
| LIS - iteration4 | 1 | 2 | 1 | 2 | 3 | 3 | 3 | j=3 | i=len(A) |
| LIS - iteration5 | 1 | 2 | 1 | 2 | 3 | 3 | 3 | j=4 | i=len(A) |
| LIS - iteration6 | 1 | 2 | 1 | 2 | 3 | 3 | 4 | j=5 | i=len(A) |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Parent-Iteration0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | ||
| Parent-Iteration1 | -1 | 0 | -1 | -1 | 0 | -1 | -1 | ||
| Parent-Iteration2 | -1 | 0 | -1 | -1 | 1 | -1 | -1 | ||
| Parent-Iteration3 | -1 | 0 | -1 | 2 | 1 | 2 | 2 | ||
| Parent-Iteration4 | -1 | 0 | -1 | 2 | 1 | 3 | 3 | ||
| Parent-Iteration5 | -1 | 0 | -1 | 2 | 1 | 3 | 3 | ||
| Final LIS | 4 |
Given a total and coins of certain denomination with infinite supply, what is the
minimum number of coins it takes to form this total V.
int [] coins = {2, 3, 6, 7};
int V = 13;
Formula:
if (coins[i] >= j) {
T[i][j] = Min (T[i-1][j], T[i][j-coins[i]]+1)
} else {
T[i][j] = T[i-1][j]
}
OR
T[i] = Min(T[i], 1 + T[i - Coins[j]]
If we are maintaining one array to maintain min coin count and another array for
keeping track of parents.
refer here: coin change
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 0 | inf | 1 | inf | 2 | inf | 3 | inf | 4 | inf | 5 | inf | 6 | inf |
| 3 | 0 | inf | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 5 |
| 6 | 0 | inf | 1 | 1 | 2 | 2 | 1 | 3 | 2 | 2 | 3 | 3 | 2 | 4 |
| 7 | 0 | inf | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 2 | 3 | 2 | 2 |
- Time complexity - O(coins.size * total)
- Space complexity - O(coins.size * total)
Given an array of non negative numbers and a total, is there subset of numbers in this
array which adds up to given total. Another variation is given an array is it possible
to split it up into 2 equal sum partitions. Partition need not be equal sized. Just
equal sum.
Input:
int [] A = {2, 3, 7, 8, 10}
int target = 11
Formula:
if (A[i] <= j) {
T[i][j] = T[i-1][j-A[i]] || T[i-1][j]
} else {
T[i][j] = T[i-1][j]
}
Time complexity - O(input.size * total_sum)
Space complexity - O(input.size * total_sum)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | T | F | T | F | F | F | F | F | F | F | F | F |
| 3 | T | F | T | T | F | T | F | F | F | F | F | F |
| 7 | T | F | T | T | F | T | F | T | F | T | T | F |
| 8 | T | F | T | T | F | T | F | T | T | F | T | T |
| 10 | T | F | T | T | F | T | F | T | T | F | T | T |
Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
We have many options to multiply a chain of matrices because matrix multiplication is associative.
In other words, no matter how we parenthesize the product, the result will be the same.
For example, if we had four matrices A, B, C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = ....
However, the order in which we parenthesize the product affects the number of simple arithmetic
operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix,
B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly the first parenthesization requires less number of operations.
Input:
int [] M = {2, 3, 6, 4, 5};
There are 4 matrices of dimensions (2, 3) (3, 6) (6, 4) and (4, 5)
Formula is:
T[i][j] = Min (
T[i][k] + T[k][j] + (M[i] * M[k] * M[j]); //for i+1 <= k < j
);
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 36 | 84 | 124 |
| 1 | 0 | 72 | 132 | |
| 2 | 0 | 120 | ||
| 3 | 0 |
public int matrixMulChainCost(int [] M) {
int len = M.length;
/* m[i,j] = Minimum number of scalar multiplications needed
to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
dimension of A[i] is p[i-1] x p[i] */
int [][] T = new int[len][len];
int value = 0;
for (int n=2; n<len; n++) {
for (int i=0; i<len-n; i++) {
int j = i + n;
T[i][j] = Integer.MAX_VALUE;
for (int k=i+1; k<j; k++) {
value = T[i][k] + T[k][j] + (M[i] * M[k] * M[j]);
if (value < T[i][j]) {
T[i][j] = value;
}
}
}
}
return T[0][len-1];
}
Time Complexity: O(n^3)
Space Complexity: O(n^2)
Given two strings A & B, find longest common subsequence between them.
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.
| 0 | A | G | G | T | A | B | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| G | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| X | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| T | 0 | 0 | 1 | 1 | 2 | 2 | 2 |
| X | 0 | 0 | 1 | 1 | 2 | 2 | 2 |
| A | 0 | 1 | 1 | 1 | 2 | 3 | 3 |
| Y | 0 | 1 | 1 | 1 | 2 | 3 | 3 |
| B | 0 | 1 | 1 | 1 | 2 | 3 | 4 |
Formula:
if (S1[i] == S2[j]) {
T[i][j] = T[i-1][j-1] + 1;
} else {
T[i][j] = Max (T[i-1][j], T[i][j-1]);
}
Time Complexity: O(n*m)
Space Complexity:O(n*m)
Given a bag with weight W and a list of items having a certain weight and value, how would you fill the bag so that you have maximum value?
Another variation of this problem is unbounded knapsack problem where an item can be repeated which is much simpler in the sense just take the value/weight ratio for each item then sort them in decreasing order and keep adding the item until you have no capacity left.
| (Weight, Value) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| (1, 1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| (3, 4) | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
| (4, 5) | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
| (5, 7) | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
Formula:
i denotes row and j column.
Row would be the list of items. wt(i),val(i)
Col would be weights from 0 to W (capacity of the bag).
If (wt[i] > j) {
T[i][j] = T[i-1][j]
} else {
T[i][j] = Max(
T[i-1][j - wt[i]] + val[i],
T[i-1][j]
);
}
*Time complexity - O(W*total items)