Thursday, January 24, 2019

Rod Cutting Problem

Problem Statement: 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).

GFG Link: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/

Practice Link: https://practice.geeksforgeeks.org/problems/rod-cutting/0

Solution:



Getting postorder traversal of a binary tree from inorder and preorder traversal

Problem Statement: Given inorder and preorder traversal of a binary tree, find its postorder traversal.

GFG Link : https://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/

Solution:


Wednesday, January 23, 2019

Matrix Chain Multiplication

Problem Statement: 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. There are many options to multiply a chain of matrices because matrix multiplication is associative i.e. no matter how one parenthesize the product, the result will be the same.

GfG Link : https://practice.geeksforgeeks.org/problems/matrix-chain-multiplication/0

Solution:

Similar to Parenthesization DP http://www.codebytes.in/2019/01/parenthesization-dp-problem.html


Shortest Common Supersequence

Printing the Longest Common Subsequence

Problem Statement: Given two strings, print their longest common subsequence.

GFG Link : https://www.geeksforgeeks.org/printing-longest-common-subsequence/

Solution:

Output:

1
AGGTAB GXTXAYB

4 3 3 2 2 0 0 
4 3 3 2 2 1 1 
0 3 3 2 2 1 1 
0 3 3 2 2 1 1 
0 2 2 2 2 1 1 
0 1 1 1 1 1 1 

len = 4
0, 0
1, 0
2, 1
2, 2
3, 2
4, 3
4, 4
5, 5
5, 6
GTAB

Parenthesization DP Problem

Problem Statement : https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/

Solution (Bottom-Up DP):



Tuesday, January 22, 2019

01 Knapsack Problem

Problem Statement:

Source : https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

Solution:



Thursday, January 17, 2019

Maximum sum path in matrix

Problem statement : Given a N X N  matrix Matrix[N][N] of positive integers.  There are only three possible moves from a cell Matrix[r][c].

1. Matrix[r+1][c]

2. Matrix[r+1][c-1]

3. Matrix[r+1][c+1]

Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.

GeeksForGeeks link : https://practice.geeksforgeeks.org/problems/path-in-matrix/0

Algorithm : DP

Solution:



Ways to cover distance, DP

Problem Statement (https://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/):

Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.

Examples :

Input:  n = 3
Output: 4

Below are the four ways
 1 step + 1 step + 1 step
 1 step + 2 step
 2 step + 1 step
 3 step

Input:  n = 4
Output: 7

Explanation:

If we know the number of ways to reach the distances k-3, k-2, k-1, then the kth distance is just 3, 2 and 1 hops away respectively. So dp[k] = dp[k-3] + dp[k-2] + dp[k-1]

Code:



Minimum Sum Partition Problem

Statement: Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

Geeksforgeeks problem link : https://practice.geeksforgeeks.org/problems/minimum-sum-partition/0

Solution Explanation:

Simple recursive solution might be :

From index 0 start including each element into either of the partitions and recurse for the next index.
This is exponential complexity O(2^n)

What we can do is start from index 0. We either include it in first or second partition. For next index in the function call we include weight of first and second partition. When it reaches the end index it has a certain first partition and second partition sum and returns the difference between them. The indices previous to this receive the difference as return value and check to see if including the current index to the first or second partition gives overall less difference at the last index, given the current weight supplied by previous index.

A particular function call state is defined by the sum of first/second partition elements and the index we are seeing.

solve(int index, int firstPartitionSum, int secondPartitionSum)

DP[Index][FirstPartitionSum]

Code:



Wednesday, January 16, 2019

Minimum String Edit Distance DP Problem

Problem Statement : [SPOJ EDIST]

You are given two strings, A and B. Answer, what is the smallest number of operations you need to
transform A to B?

Operations are:

Delete one letter from one of strings
Insert one letter into one of strings
Replace one of letters from one of strings with another letter

Algorithm :

DP[str1.length][str2.length]

At each point pair (x, y) (x index in string 1 and y index in string 2), you either have matching values in strings or dont.

If you have matching values, you can proceed to x+1, y+1.

Otherwise, you have 3 choices:

1. Delete 1 letter from first string
2. Insert 1 letter to first string
3. Replace 1 letter to match second string

Each operation adds 1 to the cost of making strings equal.

if (str1[i] == str2[j])
return dp[i][j] = solve(i + 1, j + 1);
else return dp[i][j] = 1 + Math.min(Math.min(solve(i + 1, j), solve(i, j + 1)), solve(i + 1, j + 1));

Code:





Longest Increasing Subsequence

Problem Statement : The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

Quick Tutorial : https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

SPOJ Problem : ELIS

Time Complexity : O(N^2)

Solution :


Tuesday, January 15, 2019

Longest Common Subsequence

Longest common subsequence is a classic DP problem.

Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Solution:

1. Use DP:

Array : dp[first.length][second.length]
Function: compute(int x, int y)

A dp array of size DP[length(first)][length(second)] stores the state of the current computation.

At every function call compute(x, y) we are considering matching the char at xth index of first string with yth index of second string. If it matches we add 1 to the length of subsequence.

If it does not match, we have to skip it. We do so by just returning the value of sebsequent index matches:

skip current xth index in first string:
compute(x+1, y)

skip current yth index in second string:
compute(x, y+1)

Each of these calls return the max subsequence length  starting at their supplied indices.

At current x,y configuration since the characters don't match we consider max return value among these 2 calls and assign the current dp[x][y] state to this value. So subsequent calls to this function compute(x, y) return dp[x][y] value.

This is equivalent to saying that we have already computed what is the max common subsequence length is we start from x in first string and y in second string so just take the value and don't compute again.

This way we avoid a lot of unnecessary computation.

Time complexity:

O(MN)

where M = length(string1) N = length(string2)

For each x we match every y. Since results are stored in dp[][] we don't do the matching for particular x and y more than once.

Practice Problem SPOJ : EELCS

Code:

Loop Detection in a Linked List

Problem Statement: Given a linked list head pointer, you need to output 1 if the list contains a loop or 0 if it doesn't.

This is two pointer approach. You can also solve this using a HashSet of node addresses to see if same node address appeared again or not.

Function:


Decimal to Hex Conversion

Converting decimal to hexadecimal numbers.

Codechef problem link : https://www.codechef.com/problems/HEX

Solution:



Maximum sum subarray solution using Kadane's Algorithm

Maximum sum subarray problem :

Given a matrix of n rows and n coloums , consisting of integers , find the submatrix with maximum sum among all submatrices.

Online Judge Codechef link : https://www.codechef.com/problems/MXSUBMT

Quick video tutorial : https://www.youtube.com/watch?v=yCQN096CwWM

Explanation :

How to extend 1D kadane to this problem?

Consider a 2D array:

1 3
4 -1
2 4
5 6

Our requirement is to find max sum rectangle in this matrix. So either both of the elements of each column occur together or they don't.

To use Kadane in this problem create a new array with sum at each row equal to sum of the elements of each row in this matrix. Finding the max sum array in this 1D array is equal to a 2D array in this matrix.

For more number of columns in the matrix, we loop :

i=0, i<cols, ++i
    j=i, j<cols, ++j
        calc this sum 1D array using rows from i to j
        apply kadane to this squashed array to find corresponding 2D max sum matrix in rows from i to j
        check to see if this is max sum sub matrix overall

Max sum submatrix may or may not start at a particular i so we need to loop i upto number of cols with j from i to no of cols.

Implementation for codechef problem link:



Kadane's Algorithm for 1D Max Sum Subset in O(N)

Kadane's algorithm is used to find maximum sum subset in O(N) complexity.


  1. Begin iteration
  2. At each element the max sum subset can either be that element's value alone or max sum subset value at previous element + this elements value.
  3. Record a global max while iterating.
  4. Global max at end is the answer.

Consider an example array :

-1 5 6 -2 12

              cmax                          gmax
i = 0         -1                            -1
i = 1         max(-1+5, 5) = 5,             max(-1, 5) = 5
i = 2         max(5+6, 6) = 11,             max(5, 11) = 11
i = 3         max(11+(-2), -2) = 9,         max(11, 9) = 11
i = 4         max(9+12, 12) = 21,           max(11, 21) = 21

gmax = 21 is the answer

Quick Tutorial:

https://www.youtube.com/watch?v=86CQq3pKSUw

SPOJ.com Problem MAXSUMSU Link