No. 56 - Maximal Value of Gifts

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

For example, the maximal value of gift from the board above is 53, and the path is highlighted in red.

Analysis: It is a typical problem about dynamic programming. Firstly let’s analyze it with recursion. A function f(i, j) is defined for the maximal value of gifts when reaching the cell (i, j). There are two possible cells before the cell (i, j) is reached: One is (i - 1, j), and the other is the cell (i, j-1). Therefore, f(i, j)= max(f(i-1, j), f(i, j-1)) + gift[i, j].

Even though it’s a recursive equation, it’s not a good idea to write code in recursion, because there might be many over-lapping sub-problems. A better solution is to solve is with iteration. A 2-D matrix is utilized, and the value in each cell (i, j) is the maximal value of gift when reaching the cell (i, j) on the board.

The iterative solution can be implemented in the following Java code:

public static int getMaxValue(int[][] values) {

    int rows = values.length;
    int cols = values[0].length;
    int[][] maxValues = new int[rows][cols];

    for(int i = 0; i < rows; ++i) {
        for(int j = 0; j < cols; ++j) {
            int left = 0;
            int up = 0;

            if(i > 0) {
                up = maxValues[i - 1][j];
            }

            if(j > 0) {
                left = maxValues[i][j - 1];
            }

            maxValues[i][j] = Math.max(left, up) + values[i][j];
        }
    }

    return maxValues[rows - 1][cols - 1];
}

Optimization

The maximal value of gifts when reaching the cell (i, j) depends on the cells (i-1, j) and (i, j-1) only, so it is not necessary to save the value of the cells in the rows i-2 and above. Therefore, we can replace the 2-D matrix with an array, as the following code shows:

public static int getMaxValue(int[][] values) {

    int rows = values.length;

    int cols = values[0].length;

    int[] maxValues = new int[cols];

    for (int i = 0; i < rows; ++i) {

        for (int j = 0; j < cols; ++j) {

            int left = 0;

            int up = 0;

            if (i > 0) {

                up = maxValues[j];

            }

            if (j > 0) {

                left = maxValues[j - 1];

            }

            maxValues[j] = Math.max(left, up) + values[i][j];

        }

    }

    return maxValues[cols - 1];

}

The source code with unit test cases is shared at http://ideone.com/2vLRMk.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress. 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.

No. 52 - Maximal Product when Cutting Rope

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

For example, if the length of the rope is 8, the maximal product of the part lengths is 18. In order to get the maximal product, the rope is cut into three parts with lengths 2, 3, and 3 respectively.

Analysis: There are two solutions to solve this problem. One is the traditional dynamic programming solution with O(n²) time and O(n) space, and the other is a quite creative and efficient solution with O(1) time and O(1) space.

Solution 1: Dynamic programming

Firstly let’s define a function f(n) for the maximal length product after cutting a rope with length n into parts. We have n-1 choice for the first cut on the rope, with the length of the first part 1, 2, … n-1 respectively. Therefore, f(n)=max(f(i)*f(n-i), where 0<i<n).

If the equation is resolved recursively in top-down order, there are lots of overlapping sub-problems and it’s a waste of recalculation.  It’s much more efficient to calculate in bottom-up order. That is to say, we firstly get f(2), and then f(3), then f(4), f(5). We continue till we get f(n).

The following Java code solves the problem in bottom-up order:

public static int maxProductAfterCutting_solution1(int length) {

    if(length < 2) {

        return 0;

    }

    if(length == 2) {

        return 1;

    }

    if(length == 3) {

        return 2;

    }

    int[] products = new int[length + 1];

    products[0] = 0;

    products[1] = 1;

    products[2] = 2;

    products[3] = 3;

    for(int i = 4; i <= length; ++i) {

        int max = 0;

        for(int j = 1; j <= i / 2; ++j) {

            int product = products[j] * products[i - j];

            if(max < product) {

                max = product;

            }

            products[i] = max;

        }

    }

    return products[length];

}

An array products with length n+1 is created, in order to store the maximal product of for ropes with length 0, 1, 2, …, n.

Solution 2: Tricky cutting strategy

There is a strategy to cut the rope to get maximal product: We cut the parts with length either 3 or 2. Additionally, we try to keeping cut parts with length 3 as many as possible. Therefore, we could solve the problem with the following Java code:

public static int maxProductAfterCutting_solution2(int length) {

    if(length < 2) {

        return 0;

    }

    if(length == 2) {

        return 1;

    }

    if(length == 3) {

        return 2;

    }

    int timesOf3 = length / 3;

    if((length - timesOf3 * 3) % 2 == 1) {

        timesOf3 -= 1;

    }

    int timesOf2 = (length - timesOf3 * 3) / 2;

    return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));

}

This solution sounds a bit tricky, and it does not make sense if we can’t prove it mathematically. Let’s try to demonstrate its correctness.

When n≥5, we could prove that 2(n-2)>n and 3(n-3)>n. Therefore, we continue to cut rope into parts with length 3 or 2 when the length is greater than 5. Additionally, 3(n-3) ≥ 2(n-2) when n≥5, so we cut parts with length 3 as many as possible.

The prerequisite of the proof above is n≥5. How about n is 4? There are only two approaches to cut when the length of the rope is 4: Cut into two parts with lengths 1 and 3, or with lengths 2 and 2. In our strategy, the rope will be cut into two parts with length 2 and 2. The other approach is discarded because a part with length 1 is not allowed. Notice that 4=2*2, and 2*2>1*3. That’s to say, it’s no harm to cut a rope with length 4 into two parts with same length 2.

Therefore, our strategy to cut ropes is correct.

Code with unit tests is shared at http://ideone.com/wGvr86.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

No. 49 - Longest Substring without Duplication

Problem: Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’.

Analysis: It’s not difficult to get all substrings of a string, and to check whether a substring has duplicated characters. The only concern about this brute-force strategy is performance. A string with n characters has O(n²) substrings, and it costs O(n) time to check whether a substring has duplication. Therefore, the overall cost is O(n³).

We may improve the efficiency with dynamic programming. Let’s denote the length of longest substring ending with the i^th character by L(i).

We scan the string one character after another. When the i^th character is scanned, L(i-1) is already know. If the i^th character has not appeared before, L(i) should be L(i-1)+1. It’s more complex when the i^th character is duplicated. Firstly we get the distance between the i^th character and its previous occurrence. If the distance is greater than L(i-1), the character is not in longest substring without duplication ending with the (i-1)^th character, so L(i) should also be L(i-1)+1. If the distance is less than L(i-1), L(i) is the distance, and it means between the two occurrence of the i^th character there are no other duplicated characters.

This solution can be implemented in Java as the following code:

public static int longestSubstringWithoutDuplication(String str) {

    int curLength = 0;

    int maxLength = 0;

    int position[] = new int[26];

    for(int i = 0; i < 26; ++i) {

        position[i] = -1;

    }

    for(int i = 0; i < str.length(); ++i) {

        int prevIndex = position[str.charAt(i) - 'a'];

        if(prevIndex < 0 || i - prevIndex > curLength) {

            ++curLength;

        }

        else {

            if(curLength > maxLength) {

                maxLength = curLength;

            }

            curLength = i - prevIndex;

        }

        position[str.charAt(i) - 'a'] = i;

    }

    if(curLength > maxLength) {

        maxLength = curLength;

    }

    return maxLength;

}

L(i) is implemented as curLength in the code above. An integer array is used to store the positions of each character.

Code with unit tests is shared at http://ideone.com/CmY3xN.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

No. 44 - Dynamic Programming on Stolen Values

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

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

Analysis: A function f(i) is defined to denote the maximal stolen value from the first house to the i^th house, and the value contained in the i^th house is denoted as v_i. When the thief reaches the i^th house, he has two choices: to steal or not. Therefore, f(i) can be defined with the following equation:

It would be much more efficient to calculate in bottom-up order than to calculate recursively. It looks like a 1D array with size n is needed, but actually it is only necessary to cache two values for f(i-1) and f(i-2) to calculate f(i).

This algorithm can be implemented with the following C++ code:

int maxStolenValue(const vector<int>& values)

{

    int length = values.size();

    if(length == 0)

        return 0;

    int value1 = values[0];

    if(length == 1)

        return value1;

    int value2 = max<int>(values[0], values[1]);

    if(length == 2)

        return value2;

    int value;

    for(int i = 2; i < length; ++i)

    {

        value = max<int>(value2, value1 + values[i]);

        value1 = value2;

        value2 = value;

    }

    return value;

}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

No. 28 - A Pair with the Maximal Difference

Problem: A pair contains two numbers, and its second number is on the right side of the first one in an array. The difference of a pair is the minus result while subtracting the second number from the first one. Please implement a function which gets the maximal difference of all pairs in an array. For example, the maximal difference in the array {2, 4, 1, 16, 7, 5, 11, 9} is 11, which is the minus result of pair (16, 5).

Analysis: A naïve solution with brute force is quite straightforward: We can get the result for each number minus every number on its right side, and then get the maximal difference after comparisons. Since O(n) minus operations are required for each number in an array with n numbers, the overall time complexity is O(n²). Brutal force solution usually is not the best solution. Let us try to reduce the times of minus operations.

Solution 1: via divide and conquer

We divide an array into two sub-arrays with same size. The maximal difference of all pairs occurs in one of the three following situations: (1) two numbers of a pair are both in the first sub-array; (2) two numbers of a pair are both in the second sub-array; (3) the minuend is in the greatest number in the first sub-array, and the subtrahend is the least number in the second sub-array.  

It is not a difficult to get the maximal number in the first sub-array and the minimal number in the second sub-array. How about to get the maximal difference of all pairs in two sub-arrays? They are actually sub-problems of the original problem, and we can solve them via recursion. The following are the sample code of this solution:

int MaxDiff_Solution1(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

    int max, min;

    return MaxDiffCore(numbers, numbers + length - 1, &max, &min);

}

int MaxDiffCore(int* start, int* end, int* max, int* min)

{

    if(end == start)

    {

        *max = *min = *start;

        return 0x80000000;

    }

    int* middle = start + (end - start) / 2;

    int maxLeft, minLeft;

    int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);

    int maxRight, minRight;

    int rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);

    int crossDiff = maxLeft - minRight;

    *max = (maxLeft > maxRight) ? maxLeft : maxRight;

    *min = (minLeft < minRight) ? minLeft : minRight;

    int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;

    maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;

    return maxDiff;

}

In the function MaxDiffCore, we get the maximal difference of pairs in the first sub-array (leftDiff), and then get the maximal difference of pairs in the second sub-array (rightDiff). We continue to calculate the difference between the maximum in the first sub-array and the minimal number in the second sub-array (crossDiff). The greatest value of the three differences is the maximal difference of the whole array.

We can get the minimal and maximal numbers, as well as their difference in O(1) time, based on the result of two sub-arrays, so the time complexity of the recursive solution is T(n)=2(n/2)+O(1). We can demonstrate its time complexity is O(n).

Solution 2: get the maximum numbers while scanning

Let us define diff[i] for the difference of a pair whose subtrahend is the i^th number in an array. The minuend corresponding to the maximal diff[i] should be the maximum of all numbers on the left side of i^th number in an array. We can get the maximal numbers on the left side of each i^th number in an array while scanning the array once, and subtract the i^th number for them. The following code is based on this solution:

int MaxDiff_Solution3(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

    int max = numbers[0];

    int maxDiff =  max - numbers[1];

    for(int i = 2; i < length; ++i)

    {

        if(numbers[i - 1] > max)

            max = numbers[i - 1];

        int currentDiff = max - numbers[i];

        if(currentDiff > maxDiff)

            maxDiff = currentDiff;

    }

    return maxDiff;

}

It is obviously that its time complexity is O(n) since it is only necessary to scan an array with length n once. It is more efficient than the first solution on memory requirement, which requires O(logn) memory for call stack for the recursion.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.