Minimum jumps to reach at end

Minimum jumps to reach end of array

Given an array of integers, find minimum jumps to reach end of the array. Condition is that you can maximum jump a[i] indices from index i.

For example, in following array, minimum jumps required are 2.

Original array

At index 1, we can either jump 0, 1 or 2 indices ahead. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4. So total number of jumps would be 3.

You jump maximum at start, but at the end, more number of jumps required.

However if we jump only 1 index ahead, next A[i] will allow us to jump 3 indices ahead, doing so we will reach at the end of the array. So minimum number of jumps to reach at the end of array is 2.

minimum jumps required
Not starting with maximum jump actually save one jump to reach at the end

Minimum number of jumps : thought process

What would be the brute force method to solve this? At each index, you try all possible jumps and get the combination which gives you the minimum jumps. This method will have exponential complexity which we do not want.

What is the original problem? It’s minJumps(start, end) Of all the jumps possible from start, let’s say we go to index k, then what how does problem reduces? Well, now we have to find minimum number of jumps from k to end. How to decide on k now? We try all k values from start+1 to start + a[i].

minJumps(start, end) = Min ( minJumps(k, end) )
for all k reachable from start 

Now, we have clear recursion relationship, what should be the base case? When k + A[k] > end, or k == end, we should return 1 as there would be only one jump required from k to end now.

package com.company;

/**
 * Created by sangar on 10.10.18.
 */
public class MinimumJumps {

    public int minimumNumberOfJump(int[] a, int start, int end){
        //If start == end, we reached the end, return 0.
        if(start == end) return 0;

        //if current element is 0, you cannot jump to end at all
        if(a[start] == 0) return Integer.MAX_VALUE;

        int minimumJumps = Integer.MAX_VALUE;

        for(int k=start+1; k<=start+a[start] && k<=end; k++){
            /*
            For each K from start+1 to end, find the minimum jumps.
             */
            int jumps = minimumNumberOfJump(a,k,end);
            if(jumps != Integer.MAX_VALUE && jumps + 1 <; minimumJumps){
                minimumJumps  = jumps + 1;
            }
        }
        return minimumJumps;
    }
}

Test cases for above function

package test;

import com.company.MinimumJumps;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MinimumJumpTest {

    MinimumJumps tester = new MinimumJumps();

    @Test
    public void baseTest() {

        int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        assertEquals(3,
			tester.minimumNumberOfJump(a,0, a.length-1));
    }

    @Test
    public void arrayContainsZeroTest() {

        int[] a = {1, 3, 0, 0, 0, 2, 6, 7, 6, 8, 9};
        assertEquals(Integer.MAX_VALUE, 	  
			tester.minimumNumberOfJump(a,0, a.length-1));
    }

    @Test
    public void nullArrayTest() {

        assertEquals(0, tester.minimumNumberOfJump(null,0, 0));
    }

    @Test
    public void arrayWithTwoElementsTest() {

        int[] a = {1, 0};
        assertEquals(1,
			tester.minimumNumberOfJump(a,0, a.length-1));
    }
}

Let’s see execution trace of above function for an input.

Nodes in red are re-calculated

From the above execution tree, we notice that some subproblems are calculated again and again. This is typically known as overlapping subproblems.
Also, optimal solution to subproblem actually lead us to optimal solution for original problem which is optimal subproblem structure. These two property are must to apply dynamic programming to a problem.

What if we store minimum number of jumps required to reach a particular index. To reach first index, jumps required is 0. Jump[i] represents the number of reach index i. Solution to reach at the end of the array would be Jump[n-1]. How do we feel this array? For each i,  from  j = 0 to i-1 and check if j+a[j] <= i, if yes, update jump[i] = min (jump[i], jump[j]+1).

Minimum number of jumps: dynamic programming approach

package com.company;

/**
 * Created by sangar on 10.10.18.
 */
public class MinimumJumps {

    public int minimumNumberOfJumpDP(int[] a){

        if(a == null || a.length == 0) return 0;

        if(a[0] == 0) return Integer.MAX_VALUE;

        int[] jump = new int[a.length];

        //no jumps required for first element
        jump[0] = 0;

        for(int i=1; i<a.length;i++){
            jump[i] = Integer.MAX_VALUE;

            for(int j=0; j<i; j++){
                if(j+a[j]>=i && jump[j] != Integer.MAX_VALUE ){
                    jump[i] = Integer.min(jump[i], 1 + jump[j]);
                }
            }
        }
        return jump[a.length-1];
    }
}

Complexity of dynamic programming approach to find minimum number of jumps to reach end of an array is O(n2) with space complexity of O(n)

If you are interested to solve this problem in O(n) time, please visit stack overflow discussion 

Please share if there is something wrong or missing. If you are interested in taking coaching from one of our experienced teachers, please reach out to us at communications@algorithmsandme.com

Find k number in sliding window problem

Sliding window problem

Given a large integer array of size x, window size of n and a random number k, find smallest k numbers in every window of n elements in array. This is commonly know as sliding window problem. For example: for an array [2,3,1,5,6,4,2,5,4,3,8] k = 2 and n = 6, output should be [1,2],[1,2],[1,3][1,4][1,3][1,3]. How? see below figure.

This problem regularly features in Amazon interviews.

Find k numbers in sliding window : thoughts

If we spit down the problem, it reduces to find k smallest elements in an array, which can easily be solve in multiple ways. All we have to take care of is moving the window and storing results for each window.

Quick sort method
First way is to use quick sort, we randomly pick a pivot and put it in right place. When pivot is at right place, all elements on the right side of pivot are greater than pivot and all elements on the left side are less than pivot. If pivot is a kth position in array, all elements on left side of pivot automatically become K smallest elements of given array. In worst case this method take O(n log n) for each window.

Using heaps
What are we interested in is k elements, what if from current window, we take out first k numbers and consider them as k smallest elements? This set of k numbers may change based value of following numbers in the window. Which way? If new number is smaller than any of the number chosen randomly, new number has to be added into the k smallest element set. However, we have only k spaces there, so someone has to move out.

If new number is less than any number in set, it must be less than maximum number in set

Given above fact, we can always swap new number with maximum of set. Now problem is how to find max in a set? This set will modified repeatedly, so we cannot just sort it once and find the max. For use cases when data is changing and we have to find max of that set, heaps are the best data structures to use. In this case we will use max heap. Max heap is kind of heap where children of root node are smaller than root node. Max heap will give us O(1) complexity to find max and O(log n) complexity to heapify on removal old max and insertion of new number.

Algorithm

  1. Create a max heap with first k elements of window.
  2. Scan through remaining elements in window
    1. If root of max heap is less than new number, remove the root and add new element to heap
    2. All elements in heap at the end of processing are k smallest numbers in window.

    Sliding window algorithm to find k smallest elements : Implementation

    #include<stdio.h>
    #include<stdlib.h>
    #include <math.h>
    
    typedef struct node {
    	struct node * left;
    	struct node * right;
    	int data;
    } heapNode;
    
    int leftChild(int i){
    	return 2*i + 1;
    }
    
    int rightChild(int i){
    	return 2*i + 2;
    }
    
    void swapPtr(heapNode *a[], int i, int largest){
    	heapNode *temp = a[i];
    	a[i] = a[largest];
    	a[largest] = temp;
    }
    /* This function heapifies heap after removal of root  
    or at time of building heap from an array */
    void max_heapify_ptr(heapNode *a[], int i, int len){
            int largest = i;
            int left, right;
    
            left = leftChild(i);
            right = rightChild(i);
           
            if(left <= len && a[i]->data <a[left]->data){
                    largest = left;
            }
            if(right <= len && a[largest]->data < a[right]->data){
                    largest = right;
            }
            if(largest != i){
                    swapPtr(a, i, largest);
                    max_heapify_ptr(a, largest, len);
            }
    }
    
    /* Building heap from given elements */
    void build_max_heap_ptr(heapNode *a[], int len){
            int i = len/2 +1;
            for(; i>=0; i--){
                    max_heapify_ptr(a,i, len);
            }
    }
    
    /* This function allocates node of heap */
    heapNode * create_node(int data){
            heapNode *node = (heapNode *)(malloc)(sizeof(heapNode));
            if(node){
                    node->data = data;
            }
            return node;
    
    }
    
    /* This function is real implementation of 
    the sliding window algorithm */
    void slide_window(int buffer[], int N, int K, int buffer_len){
    
        int i =0, j =0,s;
        heapNode *max_heap[K+1];
        int num = K;
    
        for(j=0 ; j + N < buffer_len; j++){
          /* Window starts at index 0 and is of size N */
           printf("\nCurrent window :");
           for(s =j; s<j+N; s++){
               printf("%d ", buffer[s]);
           }
           printf("\n");
           /* Put K element from N element window */
           for(i=0;i<K; i++){
           /* Since we wold be doing for every window, 
              avoiding reallocation of node */
               if(max_heap[i]){
                    max_heap[i]->data = buffer[i+j];
                }
                else{
                    max_heap[i] = create_node(buffer[i+j]);
                }
            }
            /* Build min heap with those entered elements */
             build_max_heap_ptr(max_heap,K-1);
    
            /*Now for all remaining N-K-1 elements in window, 
             check if they fit in max heap */ 
             for(i=K+j; i< N+j; i++){
                 heapNode * root = max_heap[0];
                 if(buffer[i] < root->data){
                       root->data = buffer[i];
                       max_heapify_ptr(max_heap, 0, K-1);
                  }
              }
              
              /*Print the current max heap, it will contain K smallest 
                element in current window */
               printf("K minimum elements in this window :");
               for(int x=0; x< K; x++){
               	printf("%d ", max_heap[x]->data);
               }
               
               
            }
    }
    /* Driver Program to execute above code */
    int main(){
       int buffer[10] = {1,4,5,6,3,2,4,8,9,6};
    
       int K= 4;
       int N =5;
       
       int size = sizeof(buffer)/ sizeof(buffer[0]);
       
       slide_window(buffer,N, K,size);
       return 0;
    }
    

    Following figures explain how window slides and how heap is updated.
    1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap. Array is given in below picture with window size of 9 and k = 4.
    First step is to create a max heap with first 4 elements of window.

    sliding window problem

    Next we are looking at 4, which is less than max in max heap. So we remove the max from heap and add the new element(4) to heap.

    k smallest element in sliding window

    Next is 2, which is less than max in max heap. So we remove the max from heap and add the new element(2) to heap.

    Next is 3, which is less than max in max heap. So we remove the max from heap and add the new element(3) to heap.

    Next we have 10 and 11 which are greater than root of max heap, so nothing happens.

    We come to end of window. Therefore, 4 smallest element in window are [ 1,2,3,4 ]

    Next window moves one step ahead, that’s where you discard the max heap and create the new empty one and repeat the process.

    We can actually avoid discarding the entire heap when window moves, however complexity of overall algorithm will remain the same. This problem is asked in a different way, which is to find maximum in sliding window.

    #include <iostream>
    #include<deque>
    using namespace std;
    
    void slidingWindow(int buffer[], int n, int w, int output[])
    {
       deque<int> Q;
       int i;
       /*Initilize deque Q for first window, put all W elements, however also
       removing elements which cannot be maximum in this window */
       for (i = 0; i < w; i++)
       {
       	   //This is where we are removing all less than elements
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
           // Pushing the index
           Q.push_back(i);
       }
      
       for (i = w; i < n; i++)
       {
           output[i-w] = buffer[Q.front()];
    
           //update Q for new window
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
    
           //Pop older element outside window from Q    
           while (!Q.empty() && Q.front() <= i-w)
               Q.pop_front();
          
           //Insert current element in Q
           Q.push_back(i);
       }
       output[n-w] = buffer[Q.front()];
    }
    
    int main(){
    	int a[]={3,5,4,2,-1,4,0,-3};
    	int n = sizeof(a)/sizeof(a[0]);
    	int output[n];
    
    	slidingWindow(a,n,4,output);
    	return 0;
    }
    

    Worst case complexity of sliding window algorithm would be O(n2k). K is included as it takes O(k) complexity to build heap of k elements.

    Please share if there is something wrong or missing.

Complexity Analysis : Asymptotic Notation

First of all, how can we measure performance of any algorithm? 

We can implement algorithm and run it on computer, measure the time and space taken by program and gauge the performance. What’s wrong with this method?
There are two many variables which can affect the run time or performance of algorithm like what kind of machine it is running on, what is accuracy of the measurement, implementation language used, proficiency of programmer etc.

To avoid these problems, computer science has a notion to represent run time or complexity of an algorithm known as Asymptotic notation. Complexity or run time of algorithms are calculated without implementing or running the algorithms on computers.
Worst case behavior
When we are questioning run time of an algorithm, what are we interested in most? We ask what would be the longest time it would it take this algorithm to complete? That’s called worst case complexity.
Worst case complexity of an algorithm is maximum operations algorithm would do for given input size of N.

For example, if want to search for an element in an array and I use linear search, what would be the case when I do maximum number of operation? Yes, when element is not present in array at all. We would end comparing every element of array with given value to be searched. So worst case complexity would be N. 

Average case behavior
Other metric we might be interested in is average time an algorithm takes to complete. This is used in cases where the nature of input is known and we can mathematically calculate average case.

Best case  behavior Least used metric is best case i.e what would be the least number of comparisons one has to make in linear search?  One if element being searched is first element of array.

Asymptotic Notation
What we really interested in is how the complexity function of an algorithm grows as input set grows. We do not care what constant preparation time is required. So what we are looking for dependency of algorithm on input size and not on implementation language or underlying machine architecture.
Asymptotic notations allow us to do so. There are three notations which are widely used for specifying complexity of an algorithm:

1.Theta Notation :
This notation binds the function from above and below both. If we want to convert a function in its omega representation, apply following steps Remove all constant and lower order terms from the function, Remove all leading multiplication factor. For example,
T(n) = n^2 + 6n + 8 = Theta(n^2)

It is to say that we are interested in term which grows faster as compared to other terms in function given large values of N. Mathematically, Theta(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <= f(n) = n0}

2.Big O Notation : This notation binds the complexity function from above, i.e. it gives the worst case complexity of algorithm. No matter what the input is algorithm will never perform worse than big O specified complexity. For example, insertion sort algorithm has worst case when input array is in reverse order where we execute inner loop for j times where j varies from 0 to N, which gives us worst case as O(N^2)
Mathematically, O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) = n0}

3.Omega Notation
This notation binds the complexity function from below, in other terms it represents the lower bound of the complexity or best case. Mathematically,

Omega(g(n)) = {f(n): there exist  positive constants c and n0    such that 0 <= cg(n) = n0}.

Complexity analysis cheat Sheet

Below is cheat sheet of complexity analysis of various data structures and their operations

Data structure Operation Complexity Analysis
Array
Insert
O(1)
Remove
O(N)
Search
O(N)
Binary Search
O(Log N)
Queue
Insert
O(1)
Remove
O(1)
Search
O(N)
Stack
Insert
O(1)
Remove
O(1)
Search
O(N)
Hash
Insert
O(1)
Delete
O(1)
Search
O(1)
Heap
Insert
O(Log N)
Delete
O(Log N)
Search
O(Log N)
Find Max/Min
O(1)
Binary Search Tree
Insert
O(N)
Delete
O(N)
Search
O(N) Usually we think worst case as O(log N) but worst case is O(N)
Algorithms
Binary Search
O(Log N)
Linear search
O(N)
Selection sort
O(N^2)
Insertion sort
O(N^2)
Quick sort
O(N^2), we think as O(N Log N ) but worst case is O(N^2)
Merge sort
O(N Log N)
Heap sort
O(N Log N)
Count sort
O(N)

This is not the end of list. I will keep on adding more algorithms as we go forward.

Find if there is subset with given sum

Subset sum problem

Given a set of integers, find if there is a subset which has a sum equal to S where s can be any integer. For example, in set = {2,4,5,3}, if  s= 6, answer should be True as there is a subset {2,4} which sum up to 6. However, for the same set if s = 10, answer would be False as there is no subset which adds up to 10.

Here, we need to find all elements (present in the set) whose sum does not exceed S. This condition is similar to what we have in knapsack problem. In Knapsack problem, we had a limited capacity and we could take anything which does not exceed the limit. However there is a difference, in knapsack problem, we were allowed to take items less than capacity if the value was greater than all others combinations. Here we need to discard subsets which have the sum less than S. So, what was the basic strategy for solving knapsack problem? Yes, take each item and check if it fits in the constraint. If it does, we would take that item and reduce the problem to a subproblem looking in N-1 items and reduced capacity of C-v where v was the value of item included.
If the chosen item does not satisfy the constraint, ignore it and reduce the problem to N-1 items and capacity C. The same principle applies here too.

Find subset with given sum: Algorithm

Algorithm for subset sum problem using recursion. For each integer in the set, there are two options:
1. Include current integer in solution.
2. Do not include the integer in solution
The choice we make above will reduce the original problem to subproblem with N-1 elements and either S-v or S as sum expected for those n-1 elements.

When do we stop reducing problems into sub-problems? What would be the base case? If sum expected out of remaining elements in sub-problem is equal to zero at any given time, the subset is found. If we have visited all elements of the set and yet not achieved expected sum S (In this case, we have not elements while expected sum is still greater than 0), there is no subset.

With help of some book keeping, we can also print all the subsets.

Subset sum problem: Implementation

#include<stdlb.h>
#include<stdio.h>

#define true 1
#define false 0
int isSubsetSum(int arr[], int n, int sum,
                int subset[], int count){
  int i;
  if(sum == 0) {
       printf("\n");
       for(i =0; i < count; i++)
           printf("%d  ",  subset[i]);
           return true;
       }
  if(n < 0  && sum != 0)  return false;
	
  subset[count] =  arr[n];
  return
         isSubsetSum(arr, n-1, sum-arr[n], subset, count + 1)
         || isSubsetSum(arr, n-1, sum, subset, count );
}

int main(){

  int set[] = {1,3,5,4,6};
  int n  =  sizeof(set)/sizeof(set[0]);
  int K = 10;
  int subset[n]
  printf("Is there subset with Sum = %d : %s",
          K, isSubsetSum(set, n, subset, K) ? "Yes": "No");
  return 0;
}

The complexity of the algorithm to find subset in an array with a given sum is (2N) as in worst case it has to go through all the a (of length 1 to N ) of the set.

Subset sum problem using dynamic programming

Two conditions which are must for application of dynamic programming are present in above problem. The optimal solution to subproblem actually leads to optimal solution for the original problem. At the same time, we are solving subproblems again and again. How can we use dynamic programming here then?

Let’s say we to find if j elements in the set which add up to sum i. What if there are no elements in the set, that means j = 0. In this case, no matter what, no sum except 0 is possible. If we store it in a table, T[0][0] = True, and T[i][0] = False for all i > 0 and i< S.

What if we have to find S = 0 for given j elements? In that case, it is always possible to find a set with zero elements (empty subset) which adds up to zero. Therefore, T[0][j] = True for all j >=0 and j <= n.

When would T[i][j] be True otherwise? It can be true in two conditions:

  1. If there is a subset with j-1 elements which already adds up to sum i.
  2. If there is a subset with j-1 elements which add up to i-a[j]. This means adding a[j] to that subset will give us a subset of j elements with sum i.
T[i][j] = T[i-a[j]][j-1] || T[i][j-1]

Make sure that i – a[j] >= 0. This recurrence relation will fill up the table and value T[n][S] will tell us if there is a subset with sum S in the set of n integers.

#include<stdlib.h>
#include<stdio.h>

int isSubsetSum(int arr[], int n, int sum)
{
  /* The value of subset[i][j] will be true if there is a
  subset of set[0..j-1] */
  int subset[sum+1][n+1];
  int i,j;

  /* If sum ==0, there will be empty set satisfying that condition
  hence row with sum = 0 will have all true values. */
  for (i = 0; i <= n; i++)
    subset[0][i] = true;

  /* If sum is not 0 and set is empty, no subset is there */
  for (i = 1; i <= sum; i++)
    subset[i][0] = false;

  for (i = 1; i <= sum; i++)
  {
    for ( j = 1; j <= n; j++)
    {
        /* If there is subset with j-1 elements, copy value */
        subset[i][j] = subset[i][j-1];

        /* Now if the latest element can be added */
        if (i <= arr[j-1])
            subset[i][j] = subset[i][j]
                           ||subset[i-arr[j-1]][j-1];
    }
  }
  return subset[sum][n];
}

/* Driver program */
int main(){

  int set[] = {1,3,5,4,6};
  int n  =  sizeof(set)/sizeof(set[0]);
  int K = 10;
  printf("Is there subset with Sum = %d : %s",
          K, isSubsetSum(set, n, K) ? "Yes" : "No");
  return 0;
}

Dynamic programming implementation of subset problem has the time complexity of O(nS) and uses O(nS) extra space.

Please share if there is something wrong or missing in the post. We would love to hear from you. If you are preparing for an interview and need preparation material, please signup to the website.

Word break problem

Word break problem

This problem is commonly asked in the Google and Amazon interview. We all know that if you typed string in Google search box does not make sense, Google breaks that into meaningful words and asks us back if we meant those words instead of a single word. This post discusses how can we find if the given string can be broken into meaningful dictionary words. For example, if I typed algorithmsandme and given dictionary is [“algorithms”, “and”, “me”], this string is breakable in meaningful words. but if the string is algorithmsorme this is not breakable into meaningful words. You can find this problem for practice at leetcode.

Word break problem : thoughts

We start with the first character of the string, check if the character itself is a word in the dictionary? If yes, then our problem reduces to the smaller problem, that is to check if substring from index 1 to s.length is breakable or not.
If not, then we check two characters and then three characters and so on till we can check the whole string. As with every character inclusion, the problem reduces in size but remains the same, so ideal case for recursive implementation.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakUtil(s, wordDict, 0, table);
    }

    private boolean wordBreakUtil(String s, 
                                   List<String> wordDict, 
                                   int index) {

        if (index == s.length()) return true;

        boolean isBreakable = false;
        for(int i=index; i<s.length(); i++) {
            isBreakable = isBreakable 
                   || wordDict.contains(s.substring(index, i+1))
                    && wordBreakUtil(s, wordDict, i + 1);
        }

        return isBreakable;
    }
}

If you notice we are solving the same problems again and again in recursive function wordBreakUtil, how can we save that repeated calculations? Best way to save the already solve problems in a cache, that way we can refer to the cache if the problem is already solved or not. If yes, do not solve it again and use the cached value. This approach is called a Top Down approach and uses memoization to avoid repeated subproblems.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        int [] table =  new int[s.length()];
        for(int i=0; i<s.length(); i++){
            table[i] = -1;
        }
        return wordBreakUtilTopDown(s, wordDict, 0, table);
    }

    private boolean wordBreakUtilTopDown(String s, 
                            List<String> wordDict,
                            int index,
                            int[] table) {

        if (index == s.length()) return true;

        if(table[index] < 0) {
            boolean isBreakable = false;
            for (int i = index; i < s.length(); i++) {
                isBreakable = isBreakable 
                        || wordDict.contains(s.substring(index, i + 1))
                        && wordBreakUtilTopDown(s, wordDict, i + 1);
            }
            table[index] = isBreakable ? 1 : 0;
        }
        return table[index] == 1 ? true : false;
    }
  }

If you run the first solution, it will exceed the time limit on leetcode, however, the second implementation should be accepted with 4ms as the time to run. Now you can appreciate the efficiency by memoization.

Word break problem using dynamic programming

In the last two implementations, two things are evident: first, the optimal solution of a subproblem leads to the optimal solution of the original problem. Second, there are overlapping subproblems. These are two must have conditions for applying dynamic programming. We already saw the memoization and top-down approach of DP to avoid repeated solving of subproblems. How can we do it bottom up?

What if store an information if the string till index i is breakable? What will be the base case? The string before index 0 is alway breakable as empty string. So table[0] can be always true. To check if string till index i is breakable or not, we check from index 0 to index i-1 if there is any index j till which string is breakable. If yes, then we just check if substring from index j to i, that will make table[i] as true.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakBottomUp(s, wordDict, 0, table);
    }

    private boolean wordBreakUtilBottomUp(String s, List<String> wordDict){

        if(s == null || s.length() == 0) return false;

        boolean[] table  = new boolean[s.length()+1];

        table[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (table[j] && wordDict.contains(s.substring(j, i))) {
                        table[i] = true;
                    }
                }
            }
        }
        return table[s.length()];
    }
}

The time complexity of the above implementation of the word break problem is O(n2)

If you want to store all the strings which can be generated by breaking a particular word, below is the code.

package AlgorithmsAndMe;

import java.util.*;

public class WordBreak2 {

    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<String, List<String>> map = new HashMap<>();
        return wordBreakUtil2(s, wordDict, map);
    }

    private List<String> wordBreakUtil2(String s,
                                        List<String> wordDict,
                                        Map<String, List<String>> map) {

        if(map.containsKey(s)){
            return map.get(s);
        }

        List<String> result = new ArrayList<String>();
        if (wordDict.contains(s)){
            result.add(s);
        }

        for(int i=1; i<=s.length(); i++) {
            String prefix = s.substring(0, i);
            if(wordDict.contains(prefix)){
                List<String> returnStringsList = wordBreakUtil2(s.substring(i), wordDict, map);

                for(String returnString :returnStringsList ){
                    result.add(prefix + " " + returnString);
                }
            }
        }
        map.put(s,result);

        return result;
    }
}

Please share if there is something is wrong or missing. If you are preparing for an interview and need any help with preparation, please reach out to us or book a free session.

LRU cache (Least Recently Used cache)

LRU cache implementation in Java

This is commonly asked question in interview, especially Microsoft and Amazon interviews. Problem statement is very simple

Implement LRU cache or Least Recently Used cache

Before going further into solution, first let’s understand what is cache?  In computer architectural terms, a cache is small buffer of pages OS maintains in-order to avoid more expensive main memory accesses.

Usually cache accesses are faster than main memory access, improving overall performance. Whenever process needs to access content from a specific memory location, it tries to search that page in cache first. If it finds page in cache, it uses it and does not access memory. It’s called cache hit.

However, caches are very small in size as compared to main memory, there is probability that page requested by process is not present in cache. In that case, new page is moved into cache and one of existing page is swapped out. When this happens, it is called cache miss.

Caching also happens at application layer too, for example, caching visited pages on browser, caching frequently accessed data from DB to in memory caches like Redis.

Based on how cache miss is handled in cache, there different type of caches like first in first out cache, least recently use cache, least frequently use cached.

In first in first out cache, in the event of cache miss, entity which came first into cache is evicted first; where as in least recently used cache, page which was used least recently gets evicted. In the same vain, least frequently used cache is where page which is least frequently used among all the pages in cache.

LRU cache implementation

Consider that you have a cache with space for additional page. If cache miss happens, we bring page from memory and put it in cache for future access.

Now, if cache is full, and cache miss happens, we have to bring in a new page and evict a page from cache. In LRU cache, this page will  be the page which accessed longest time ago.

What if a page was accessed at the start, and then accessed just before the cache miss? Is it the least recently used page? On the contrary, it is the most recently used page and hence should be last to evict. Question now is which page should we evict? In this case, page which came after the first page goes out.

If page is brought into cache first, it is first candidate for eviction, if it is not accessed again before cache miss happens.

Why queue?

In principle, LRU cache is first in first out cache with special case, that if a page is accessed again, it goes to end of eviction order. Which data structure is best to implement FIFO pattern? Of course it’s queue. So our LRU cache will be a queue where each node will store a page. This queue will have specific size as cache as limited size. Whenever a new page is brought in, it is added at the rear of queue. When eviction happens, it happens from the front of cache.

Why hash?

There is one requirement of LRU cache which does not map directly to queue data structure, which is to move a node corresponding recently accessed page to end of the queue. This poses two problems : First, how to find the node in the queue corresponding to page id being accessed? Second, how to move it to end as efficiently possible? Both problems are very similar to what we solved in first non repeated character in stream.

We will use hash which will store the node address in queue corresponding to page id. This will give us immediate access to the node to be reshuffled.

Why doubly linked list based queue?

Still problem remains to move nodes around with moving all elements of the queue. Which data structure removes an element in O(1), given the element? Doubly linked list it is. If we implement queue as doubly linked list, removing and adding pages from queue will be O(1) operation.

LRU cache algorithm

  • Cache miss happens :
    • If cache has free entry, enqueue page to queue.
    • If cache is full,  remove the page from from of queue and add new page at the end of queue.
  • Cache hit happens :
    • delete node from current location in queue.
    • Enqueue page at the end of queue.
  • If page is present in hash, it’s a cache hit, if page is not present in hash map, it’s a cache miss.

LRU cache implementation

Queue interface

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public interface Queue<E> {
    public ListNode<E> peek();
    public ListNode<E> remove();
    public ListNode<E> enqueue(E data);
    public ListNode<E> deleteNode(ListNode<E> node);
    public boolean isEmpty();
    public int size();
}

Queue implementation

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public class QueueImplementation<E> implements Queue<E>{
    ListNode<E> head;
    ListNode<E> tail;
    int size;

    public QueueImplementation(){
        head = null;
        tail = null;
        this.size = 0;
    }

    @Override
    public ListNode<E> deleteNode(ListNode<E> node){
        if(this.isEmpty()) {
            return null;
        }

        if(this.head == node){
            if(this.head.getNext() != null) this.head.getNext().setPrev(null);
            this.head = this.head.getNext();
            this.size--;
            return node;
        }

        if(this.tail == node){
            if(this.tail.getPrev() != null) this.tail.getPrev().setNext(null);
            this.tail = this.tail.getPrev();
            this.size--;
            return node;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        this.size--;
        return node;
    }


    @Override
    public ListNode peek() {
        if(this.isEmpty()) {
            return null;
        }
        return this.head;
    }

    @Override
    public ListNode remove() {
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<E> tempNode = this.head;
        this.head.setPrev(null);
        this.head = this.head.getNext();

        this.size--;
        return tempNode;
    }

    @Override
    public ListNode enqueue(E data) {
        if(this.isEmpty()) {
            this.head = new ListNode<E>(data);
            this.tail = this.head;
            this.size++;
            return this.head;
        }
        ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
        this.tail.setNext(newNode);
        this.tail = newNode;

        this.size++;
        return newNode;
    }

    @Override
    public boolean isEmpty() {
        return this.head == null;
    }

    @Override
    public int size() {
        return this.size;
    }
}

LRU cache implementation in java

package com.company;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created by sangar on 9.10.18.
 */
public class LRUCache {
    private Queue<Integer> queue;
    private HashMap<Integer, ListNode> pages;
    private int cacheSize;

    public LRUCache(int cacheSize){
        this.cacheSize = cacheSize;
        queue = new QueueImplementation<>();
        pages = new HashMap<>();
    }

    /* This function implements the LRU cache */
    public void readPage(int pageId) {

        /*Cache Miss and we can add the page in the cache */
        if (!pages.containsKey(pageId) && queue.size() < cacheSize) {
            pages.put(pageId, queue.enqueue(pageId));
            return;
        }

        /* Cache Miss and we cannot add new page to cache,
        remove the LRU page */
        if (!pages.containsKey(pageId) && queue.size() >= cacheSize) {
            //First remove it from the queue.
            ListNode evictedPage = queue.remove();
            //Remove node from hash table
            pages.remove(evictedPage.getData());
            //Enqueue new node and add it at tail
            queue.enqueue(pageId);
            return;
        }

        /* Cache is Hit */
        if (pages.containsKey(pageId)) {
            updateCache(pageId);
        }

        return;
    }

    /* This function modifies queue when there is cache hit */
    public void updateCache(int pageId){

        /* Case where queue may be empty - defensive programing*/
        if(queue.isEmpty() && queue.size() < cacheSize){
            pages.put(pageId,queue.enqueue(pageId));
        }
        /* Update the pointers of neighbor nodes and tail in dummy node */
        else{
            ListNode node = queue.deleteNode(pages.get(pageId));
            if(node != null){
                queue.enqueue((Integer)node.getData());
            }
        }
    }

    public ArrayList<Integer> cacheState(){
        ListNode current = queue.peek();
        ArrayList<Integer> cacheState = new ArrayList<>();
        while(current != null){
            cacheState.add((Integer)current.getData());
            current = current.getNext();
        }
        return cacheState;
    }
}

Test case for LRU cache implementation

package test;

import com.company.LRUCache;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LRUCacheTest {

    LRUCache tester = new LRUCache(5);

    @Test
    public void testCacheInsertion() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(1,2,3,4,5));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);

        assertEquals(cacheState, tester.cacheState());
    }

    @Test
    public void testCacheHit() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(1,4,5,2,3));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);
        tester.readPage(2);
        tester.readPage(3);

        assertEquals(cacheState, tester.cacheState());
    }

    @Test
    public void testCacheMiss() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(2,3,4,5,6));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);
        tester.readPage(6);

        assertEquals(cacheState, tester.cacheState());
    }

    @Test
    public void testEvictionAndInsertion() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(3,4,5,6,1));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);
        tester.readPage(6);
        tester.readPage(1);

        assertEquals(cacheState, tester.cacheState());
    }


    @Test
    public void testEmptyCache() {
        ArrayList<Integer> cacheState = new ArrayList<>();

        assertEquals(cacheState, tester.cacheState());
    }
}

Let’s take an example and see how whole thing works. Let’s say we have cache of size 5, which is empty to start with. Application accesses page id 1,2,3,4 and 5. As they are all cache miss to start with and there is space in cache, all these pages are brought into cache.

implement lru cache in java
Cache state after reading first 5 pages

Now, application accesses page 6. We have a cache miss. What happens? As cache is full, we evict the page which is at the front and add page 6 to it.

Page 1 is evicted, and page 6 added to queue

Application accesses page 2 again, which is already present in cache, it’s a cache hit. As page 2 is most recently used page, it has to go to end of the queue.

implement lru cache
Page 2 moves at the end

Let’s say next page accessed is page 7, it is cache miss. Evict a page from cache, which is the first node in queue (3).

lru cache implementation
New page 7 added to end after evicting page 3 from front

Insertion and removal from queue is O(1) complexity.

Please share if there is something wrong or missing. If you are interested in taking personal coaching from our expert teachers, please contact us at communications@algorithmsandme.com

Matching parenthesis problem

Matching parenthesis problem

We understood the concept of stack data structure in last post. Let’s discuss matching parenthesis problemwhich applies those concept. Problem statement is :

Given a string of parenthesis ‘(‘ and ‘)’, write a function which returns true if there are matching pairs and false if there are not. A matching pair means, there should be a closing parenthesis for an opening one, in correct order.

For example : '((()))', function should return TRUE, but ')(())' will return FALSE. Special case would be when there are equal number of parenthesis, closing and opening, but they are not in perfect order, hence function should return false in that case.

Parenthesis matching problem : Line of thoughts

For each closing parenthesis, we need a corresponding opening parenthesis. There are two possibilities : Either we find one or we do not find one. If we do not find one, we can say that string does not contain matching parenthesis.
If there is corresponding opening parenthesis, then that opening parenthesis cannot be matched with any other closing parenthesis.

Also, note that every closing parenthesis will match with the most recent opening parenthesis if there is one. That means we are looking at a order where the parenthesis which came last needs to be fetched first, typical last in first out pattern, which is best implemented by stack.

For asserting that the current closing parenthesis is in sync with what we have already seen, we just need to check if current parenthesis completes a pair with opening parenthesis we last seen. Next closing parenthesis should complete pair with the one prior to last and so on.

Parenthesis matching problem : Algorithm

  1. For each character of input string
  2. If character is opening parenthesis '(', put it on stack.
  3. If character is closing parenthesis ')'
    1. Check top of stack, if it is '(' , pop and move to next character.
    2. If it is not '(', return false
  4. After scanning the entire string, check if stack is empty. If stack is empty, return true else return false.

Matching parenthesis problem : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 21.9.18.
 */
public class ParenthesisMatch {

    public static boolean isMatchingParenthesis(String s) {
        Stack<Character> stack = new Stack<>();

        if (s == null) return true;

        int len = s.length();
        for(int i=0; i<len; i++){
            switch(s.charAt(i)){
                case '(' :
                    stack.push(s.charAt(i));
                    break;
                case ')':
                    //If stack is empty, then there is an extra closing parenthesis
                    if(stack.isEmpty()) return false;
                    stack.pop();
                    break;
                default:
                    return false;
            }
        }
        //If stack is empty that means it's a matching parenthesis
        return stack.empty();
    }

    public static void main(String[] args) {
        String s = "()))";
        System.out.println(isMatchingParenthesis(s));
    }
}

Complexity of parenthesis matching algorithm is O(N) time to scan N length string and O(N) extra space for stack.
This problem is quite simple to solve, so if you are asked this question in interview, most probably interviewer wants to understand can you think of good test cases and put your code to test against them. Below are the few test cases you can try your code on.
Test cases

1. ((())) : True
2. ())) : False
3. )((( : False
4. ( : False
5 Empty string : True
6. NULL pointer : False

Can you try solving this problem now on HackerEarth

Please share if there is something wrong or missing. If you are interested to take personal coaching from our experience teachers, please reach out to us at communications@algorithmsandme.com

Longest Common Subsequence

Longest common subseuence

A subsequence of a string is set of all the characters which are left to right order and not necessarily contiguous. For example, string ABCDEG has ABC, ADG, EG, BCDEG subsequences; whereas BDA is not a subsequence of the given string, even though all the characters are present in the string, they do not appear in the same order.

longest common subsequence lcs

Given two strings X and Y, find longest common subsequence (LCS) Z. For example, X = ABCDSEFGD Y = ACFEFXVGAB; LCS Z would be ACEFG.

Longest common subsequence: line of thoughts

First of all, notice that it is an optimization problem, it is a hint that it may be a dynamic programming problem but we are not sure yet.

Let’s say that the length of the string 1 and the string of 2 are N and M. Can I know the longest common subsequence in length N and M if I already know the LCS in N-1 and M-1? The direct question is can I divide the original problem into subproblems and solve those subproblems to get the answer for original problem? In this case, the answer is yes. (This is the second hint towards dynamic programming application, optimal subproblem substructure).

How can we divide the problem into subproblems? The length of X is N and length of Y as M. Start from the end of both strings. Check if X[N] == Y[M]. If yes, the problem reduces to find the longest common subsequence in X[1..N-1] and Y[1..M-1].

What if they are not equal? Then one by one we have to exclude character from string X and Y. Why?
First, we exclude the character from the X and find LCS in remaining characters of X and all the characters of Y. The problem reduces to X[1..N-1] and Y[1..M]. Next, we exclude a character from Y, the problem reduces to X[1..N] and Y[1..M-1]. Any of the two choices can give us the longest common subsequence, so we would take maximum from both the cases.

LCS(i,j)  =  1 + LCS[i-1, j-1] if X[i] == Y[j]
  =   MAX (LCS[i-1,j], LCS[i, j-1]) if X[i] != Y[j]
=   0 if i or j is 0

Interesting to see why LCS(i,j) is 0 when either i or j is 0? Because the longest common subsequence in two strings, when one string is empty is 0.

Can we implement the recursive function?

    public int longestCommonSubsequence(String s1, String s2, int i, int j){

        //If any of the string is nul return 0
        if(s1 == null || s2 == null) return 0;

        //We reached at the end of one of the string
        if(i == s1.length() ||  j == s2.length())
            return 0;

        if(s1.charAt(i) ==  s2.charAt(j)){
            return  1 + longestCommonSubsequence(s1, s2, i+1, j+1);
        }

        return Integer.max(longestCommonSubsequence(s1, s2, i+1, j),
                longestCommonSubsequence(s1, s2, i, j+1));

If we follow the execution cycle of the above code, we will see something like below

longest common subsequence lcs

It is evident from the partial tree that there are some problems which are solved again and again. This is the third hint (overlapping subproblems) that we can apply dynamic programming.

It will be more evident if you implement the recursive function with reverse traversal of the strings. In that implementation, the base case will be when one of the string is empty, and at that point, LCS of two strings will be 0. If we take a two dimensional table such that T[i][j] represents longest common subsequence till ith and jth characters of string S1 and S2 then T[0][i] = 0 and T[i][0] = 0.

T[i][j] = T[i-1][j-1] + 1 if X[i] = Y[j]
T[i][j] = max(T[i-1][j], T[i][j-1]) if X[i] != Y[j]

Dynamic programming implementation of LCS

package com.company;

/**
 * Created by sangar on 4.2.19.
 */
public class LongestCommonSubsequence {

    public int longestCommonSubsequenceDP(String s1, String s2){

        //If any of the string is nul return 0
        if(s1 == null || s2 == null) return 0;

        int len1 = s1.length();
        int len2 = s2.length();

        int[][] table = new int[len1+1][len2+1];

        for (int i=0; i<=len1; i++){
            for (int j=0; j<=len2; j++) {
                if (j == 0 || i == 0) {
                    table[i][j] =  0;
                }

                else if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    table[i][j] = 1 + table[i - 1][j - 1];
                } else {
                    table[i][j] = Integer.max(table[i - 1][j], table[i][j - 1]);
                }
            }
        }

        return table[len1][len2];
    }
}

Above implementation has time and space complexity of O(n2). Please share if there is anything wrong or missing.

What is dynamic programming?

What is Dynamic Programming or DP

Dynamic programming is an approach to solve a larger problem with the help of the results of smaller subproblems. It is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm. I find a lot of students asking me question around, how do I know this problem is a dynamic programming problem? There is a definite way to arrive at the conclusion if a problem is a dynamic programming problem or not?

The first thing I would recommend you to read before going down is this beautiful explanation of dynamic programming to 4 years old.

The first thing you will notice about dynamic programming problems (not all problems) is they are optimization problem. Either it will be finding minimum or maximum of some entity. For example, find minimum edit between two strings or find longest common subsequence etc. However, problems like Fibonacci series are not exactly like an optimization problem, these are more like Combinatorial problems. Still, this can be a good hint that a problem can be a DP problem.

Second, you will notice that the problem can be divided into a pattern like an fn(n) = C + fn(n-k) where k can be anything between 1 and n.
This property is called optimum subproblem structure, where an optimum solution to the subproblem leads to the optimum solution to the larger problem.
Once you get the equation, it is very easy to come with a recursive solution to the problem. I would advise you to write the recursive solution and try to calculate the complexity of the solution. It will exponential in big-O notation.

Then why did recursion work so well with a divide and conquer approach? The key point is that in divide and conquer, a problem is expressed in terms of subproblems that are substantially smaller, say half the size. For instance, mergesort sorts an array of size n by recursively sorting two subarrays of size n/2. Because of this sharp drop in problem size, the full recursion tree has only logarithmic depth and a polynomial number of nodes. In contrast, in a typical dynamic programming formulation, a problem is reduced to subproblems that are only slightly smaller than the original. For instance, fn(j) relies on fn(j − 1). Thus the full recursion tree generally has polynomial depth and an exponential number of nodes.
However, it turns out that most of these nodes are repeats, that there are not too many distinct subproblems among them. Efficiency is therefore obtained by explicitly enumerating the distinct subproblems and solving them in the right order.
Reference

This will lead us to the third property, which is overlapping subproblems. Once, you draw the execution tree of the recursive solution of the problem, it will appear that a lot of problems are being solved again and again at different levels of recursion.

The intuition behind dynamic programming is that we trade space for time, i.e. to say that instead of calculating all the subproblems taking a lot of time but no space, we take up space to store the results of all the subproblems to save time later. The typical characteristics of a dynamic programming problem are optimization problems, optimal substructure property, overlapping subproblems, trade space for time, implementation via bottom-up/memoization.

Dynamic programming in action

Enough of theory, let’s take an example and see how dynamic programming works on real problems. I will take a very commonly used but most effective problem to explain DP in action. Problem is known as the Fibonacci series. Fibonacci series is a series of integers where each integer is the sum of previous two integers. For example, 1,1,2,3,5,8,13,17 is a Fibonacci series of eight integers. Now, the question is given a number n, output the integer which will be at the nth integer in Fibonacci series. For example for n = 4, the output should be 3 and for n=6, it should 8.

First hint: It is a combinatorial problem, so maybe a DP problem. Second, it is already given in the problem that current integer depends on the sum of previous two integers, that means f(n) = f(n-1) + f(n-2). This implies that the solution to subproblems will lead to a solution to the bigger problem which is optimal substructure property.

Next step is to implement the recursive function.

 public int fibonacci (int n) {
    if (n < 2) //base case
        return 1;

    return fibonacci(n-1) + fibonacci(n-2);
 }

Great, next step is to draw the execution tree of this function. It looks like below for n = 6. It is apparent how many times the same problem is solved at different levels.

what is dynamic programming
Recursive tree of Fibonacci series function

So, now we know three things about the Fibonacci problem: It is combinatorial problem, there is optimal substructure and there are overlapping subproblems. As in dynamic programming, we side with more space than time, we will try to use extra space to avoid recalculating subproblems.

The first way is to use a case, which stores the value of fab(n) if it is already calculated. This is called memoization or top-down approach.

Map<Integer, Integer> cache = new HashMap<>();

public int fibonacci(int n){
    if (n == 0)
       return 0;
    if (n == 1)
        return 1;

    if(cache.containsKey(n))
        return cache.get(n);

    cache.put(n, fibonacci(n - 1) + fibonacci(n - 2));

    return cache.get(n);
}

Another approach is bottom up, where the smaller problems are solved in an order which helps us with solving bigger problems. Here also, we use memoization but in a different way. We store the solution of smaller subproblems and directly use this to build the solution.

int[] fib = new int[n];
fib[0] = fib[1] = 1;
public int fibonacci(int n){
   for(int i=2; i<=n; i++){
       fib[n] = fib[n-1] + fib[n-2];
   }
   return fib[n];
}

Above solution requires extra O(n) space, however, the time complexity is also reduced to O(n) with each subproblem solved only once.

Follow longest increasing subsequence problem, how we have applied the same pattern while we solved the problem.

Final thoughts
Where to apply dynamic programming : If you solution is based on optimal substructure and overlapping sub problem then in that case using the earlier calculated value will be useful so you do not have to recompute it. It is bottom up approach. Suppose you need to calculate fib(n) in that case all you need to do is add the previous calculated value of fib(n-1) and fib(n-2)

Recursion : Basically subdividing you problem into smaller part to solve it with ease but keep it in mind it does not avoid re computation if we have same value calculated previously in other recursion call.

Memoization : Basically storing the old calculated recursion value in table is known as memoization which will avoid re-computation if its already been calculated by some previous call so any value will be calculated once. So before calculating we check whether this value has already been calculated or not if already calculated then we return the same from table instead of recomputing. It is also top down approach.
Reference: Answer by Endeavour

Please share if there is something wrong or missing. If you are preparing for an interview and need help with preparation, please book a free session with us to guide you through it.

0/1 knapsack problem using dynamic programming

0/1 Knapsack problem

0/1 Knapsack is typical problem which is used to demonstrate application of greedy algorithm as well as dynamic programming. There are cases when applying greedy algorithm does not give optimal solution. There are many flavors in which Knapsack problem can be asked.  

1. A thief enters a museum and want to steal artifacts from there. Every artifact has a weight and value associated with it. Thief carries a knapsack (bag) which can take only a specific weight. Problem is to find the combination of artifacts thief steals so that he gets maximum value and weight of all taken artifacts is less capacity of  knapsack he has. Thief cannot take any artifact partially. Either he takes it or leaves it. Hence the problem is 0/1 knapsack.

2. We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be stored re-computation cost is Vi. Problem is to store as many files on storage that combined size of all files is less than W and their re-computation value is maximum. We can either store or leave a file, we cannot store partial file. Hence this is a case of 0/1 knapsack problem.

0/1 knapsack problem : Line of thoughts

Brute force method would try all subsets of set of items, whose weight adds up to maximum capacity of knapsack and see which one gives maximum value. Complexity of brute force algorithm would be of exponential order as there will be 2n possible subsets for n items.

Can we do better?  If we consider each item, there are two possibilities associated with it.
First, current item is included in optimal subset. Then we need to find out all the items in remaining N-1 items which can optimize the subproblem for weight W-wk. Value of this item is added to candidate maximum value.

Second, current item is not included in optimal subset. In that case, we need to find out items in remaining N-1 items which can optimize the the original problem. Value of current item is not added into candidate maximum value.

Inclusion depends on two conditions :

  1. Weight of the item is less than the total capacity of knapsack.
  2. Inclusion of item increases current max value with K-1 items with W-Wk weight.  

Since every steps reduces the problem to a smaller problem in terms of items of weight, recursive solution would be our first refuge. To implement this problem, what are the base cases? First, we cannot add any items to knapsack capacity is zero i.e. W == 0. Second, no item can be taken if there are no items remaining, i.e. n == 0.

Recursive implementation of 0/1 knapsack problem

package com.company;
/**
	* Created by sangar on 19.8.18.
*/
public class KnapsackProblem {
	static int knapSack(int W, int[] weights, int[] val, int n) {
		/*
			If there is no item or weight that can be carried is
			zero, return zero
		*/
		if (n &lt; 0 || W == 0)
			return 0;

		/* 
			If weight of the nth item is more than Knapsack 
			capacity W,then this item cannot be included
			in the optimal solution
		*/
		if (weights[n] &gt; W)
			return knapSack(W, weights, val, n - 1);

		/* Consider two cases, including item and excluding item.*/
		else return Integer.max(
			(val[n]
				+ knapSack(W - weights[n], weights, val, n - 1)),
			(knapSack(W, weights, val, n - 1))
		);
	}

	public static void main(String args[]) {
		int[] val = {60, 100, 120};
		int[] wt = {10, 20, 30};
		int W = 50;
	
		int n = val.length;
		System.out.println(knapSack(W, wt, val, n - 1));
	}
}

If we look at the execution trace of the function, it looks like this.

0/1 knapsack problem

There are seven problems to be solved at the leaf level. For N = 3, there are 7 problems to be solved before we start optimizing for the max value. For N, in general, it will take 2N subproblems to be solved. Hence, complexity of recursive implementation is O(2N).

If we take another example, it will become evident that there are some subproblems which are solved again and again. Overlapping subproblems is one of the criteria, we should be thinking about dynamic programming. Also, notice that optimal solution to a smaller problem leads to optimal solution to bigger problem, which is second condition for DP.  This problem satisfy both these conditions, hence let’s design DP solution for it.

0/1 knapsack problem : Dynamic programming approach

We define two dimensional array V[N,W] where N is number of items and W is capacity. For 1<= i <= n and  0<=w<=W, V[i,w] represents the optimal solution for items I1, I2, ..In with maximum weight of w.  If we can compute all the entries of this array, then the array entry V[N,W] is the solution to our problem

For i =0 and w=0, all values will be zero. So, first column and first row will be filled with all zero values.
Recursively, we can fill the table bottom up as follows.

V[i, w ] = max (V[i-1, w], V[i-1, w-w[i]) + V[i] )
V[0, w ] = 0; there are no items
V[i, 0 ] = 0; no items can be picked.
package com.company;

/**
	* Created by sangar on 19.8.18.
*/
public class KnapsackProblem {
	public static int knapsackDP(int W, int[] weights, int[] val, int n) {
		int[][] V = new int[n+1][W + 1];
		for(int i = 1 ; i &lt; V[0].length; i++){
			/*
				If weight of item is less than current value
				we can achieve minimum value V[i] with 1..i items
			*/
			if(weights[0] &lte; i){
				V[0][i] = val[0];
			}else{
				V[0][i] = 0;
			}
		}

		//Loop for all items
		for (int i = 1; i &lt; V.length; i++) {
			for (int j = 1; j &lt; V[i].length; j++) {
				/*if a weight is more than the allowed weight, 
				that weight cannot be picked. */
				if(weights[i] &gt; j){
					V[i][j] = V[i-1][j];
				}else{
					V[i][j] = Math.max(V[i-1][j], 
							val[i] + V[i-1][j-weights[i]]);
				}
			}
		}
		return V[V.length-1][W];
	}

	public static void main(String args[]) {
		int[] val = {60, 100, 120};
		int[] wt = {10, 20, 30};
		int W = 50;

		int n = val.length;
		System.out.println(knapsackDP(W, wt, val, n - 1));
	}
}

One similar problem which can be solved with same approach is minimum number of coins to be used to get change of a particular amount. I am skipping the whole analysis and directly pasting the code here.  

Complexity of the dynamic programming implementation of knapsack problem is O(N *W). Space complexity is again O(N*W). It is thumb rule that we trade space for time in dynamic programming.

Please share if there is something is wrong or missing. If you want to contribute to website, please reach out to us at communications@algorithmsandme.com