Question

link

Analysis

The key of solving this problem is to do DP from bottom right to top left.

Solution

dp[i][j] means the minimum initial value of each position. As suggested by, the DP equation is:

dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).

Code

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null) return 1;
        int m = dungeon.length;
        int n = dungeon[0].length;

        int[][] dp = new int[m][n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                } else if (i == m - 1) {
                    dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
                } else if (j == n - 1) {
                    dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
                } else {
                    dp[i][j] = Math.max(1,
                        Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}

Question

link

Analysis

This is an extremely important question, if you are going for an interview. I repeat: this is an extremely important question, if you are going for an interview. If you do not remember it by heart, I will repeat again.

The solution of the iterator applies to a lot of related questions. So make sure you practise this question until you are perfect. You WILL BE ASKED this question at times.

You could read my other post [Question] Iterator of Binary Search Tree.

Solution

We only need to keep 1 variable in RAM, that is a stack.

Code

public class BSTIterator {

    Stack<TreeNode> stack = new Stack<TreeNode>();

    public BSTIterator(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        if (!hasNext()) {
            return 0;
        }
        TreeNode next = stack.pop();
        TreeNode node = next.right;
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        return next.val;
    }
}

Question

link

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

• The setup time for the first wooden stick is 1 minute.
• Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l <=l' and w <=w' .

Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4) then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n, 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l₁, w₁, l₂, w₂, …, l_n, w_n, each of magnitude at most 10000, where l_i and w_i are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output 

The output should contain the minimum setup time in minutes, one per line.

Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

Sample Output 

2
1
3

Analysis

This question is a little similar to [CC150v5] 9.10 Stack Up the Boxes, yet different.

Solution

Solution quoted from 脚本百事通:

按长度从小到大排序, 若长度相同, 则按重量从小到大排序(先按重量再按长度也行)

然后, 我们针对当前木棍, 与剩下的木棍比较, 满足 w1 <= w2 && l1 <= l2 的, 就更新一下当前棍, 并标记~

当所有木棍都被编组后 输出到底设置了几次~

ref1, ref2

Code

The following Java code is written by me

public int count(Pair[] points) {
    Arrays.sort(points, new PointComparator());
    // now the array is sorted with Point.x
    int total = 0;
    int p = 0;
    int len = points.length;

    while (p < len) {
        // find the next non-null point
        while (p < len && points[p] == null) {
            p++;
        }
        if (p == len) {
            break;
        }
        // use points[p] as the first elements in the queue
        Pair temp = copy(points[p]);
        points[p] = null;
        total++;

        // then mark all elements that follow points[p]
        for (int k = p + 1; k < len; k++) {
            if (points[k] == null || points[k].y < temp.y) {
                continue;
            }
            temp = copy(points[k]);
            points[k] = null;
        }
        p++;
    }
    return total;
}

Pair copy(Pair p) {
    Pair newP = new Pair(p.x, p.y);
    return newP;
}

class PointComparator implements Comparator<Pair> {

    @Override
    public int compare(Pair p1, Pair p2) {
        return p1.x - p2.x;
    }
}

Question

link

N块石头排成一行，两个玩家依次取石头，每个玩家可以取其中任意一块或者相邻的两块，最后能将剩下的石头一次取光的玩家获胜。

Solution

1. when n = 1, first move wins
2. when n = 2, first move wins
3. when n = 3, first move removes middle stone, wins
4. when n = 4, first move removes 2 stones from middle, wins
5. when n = 5, first move removes middle stone, which leaves 2 piles of stones of count 2. First move wins.

So to conclude the above, we will have:

先取者只要取中间的元素，N为奇数取中间一个，偶数取中间两个，将石头分为两部分，然后无论第二个人怎么取，先取者只要在另一部分的同样位置取走同样多的石头，则最后先取者必胜

Quoted from 王川的私房菜 .

Question

link

Solution

Analysis

I have already covered this question in [LintCode] Majority Number. However, I have also discovered a few other very interesting solution. Check below.

Solution

The best solution is of course the voting algorithm. Read code below.

Second solution presented by offical answer, is to do sorting:

public int majorityElement(int[] num) {
    if (num.length == 1) {
        return num[0];
    }

    Arrays.sort(num);
    return num[num.length / 2];
}

Third interesting solution is doing bit manipulation. Read Yanyulin’s blog for more.

Code

public class Solution {
    public int majorityElement(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        int major = num[0];
        long count = 1;

        for (int i = 1; i < num.length; i++) {
            if (major == num[i]) {
                count++;
            } else if (count == 0) {
                major = num[i];
                count = 1;
            } else {
                count--;
            }
        }

        return major;
    }
}

Question

link

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Analysis

This is pretty much a similar question. It’s pretty easy.

Code

public class Solution {
    public int titleToNumber(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int sum = 0;
        for (char ch: s.toCharArray()) {
            sum *= 26;
            sum += (int) (ch - 'A' + 1);
        }
        return sum;
    }
}

Question

link

Analysis

This is an extremely difficult question of bucket sort. I refered to programcreek and tgic’s blog for reference.

Solution

Basic idea is to put elements into buckets. The number of bucket is (almost) same as the number of elements in the input. In this way, each bucket ideally will contain 1 element.

We then know that the max gap must be cross-bucket instead of within bucket. So we simply keep track of max and min value within each bucket for the purpose of calculating gap.

Why did I say “number of bucket is (almost) same as the number of elements in the input”? Well, consider this case: 3 values and (maxVal - minVal) == 100. We can make 3 bucket with size = 34. How about 5 values and (maxVal - minVal) == 6? Bucket size shall be either 1 or 2. So we’ll have either 3 or 6 bucket.

So, in the code below, you can see I make bucket size “larger by 1”:

// bSize is size of bucket (should be larger by 1)
int bSize = (maxVal - minVal + 1) / num.length + 1;

// calcualte number of buckets needed
int bCount = (maxVal - minVal) / bSize + 1;
Bucket[] buckets = new Bucket[bCount];

Note that simply use input.length as bucket count is wrong.

Code

My code written in Java:

public class Solution {
    public int maximumGap(int[] num) {
        if (num == null || num.length < 2) {
            return 0;
        }

        // find out max and min values of input
        int minVal = num[0];
        int maxVal = num[0];
        for (int n: num) {
            minVal = Math.min(minVal, n);
            maxVal = Math.max(maxVal, n);
        }
        // bSize is size of bucket (should be larger by 1)
        int bSize = (maxVal - minVal + 1) / num.length + 1;

        // calcualte number of buckets needed
        int bCount = (maxVal - minVal) / bSize + 1;
        Bucket[] buckets = new Bucket[bCount];

        // match every value into a bucket
        // bucket maintains the max/min within the bucket
        for (int n: num) {
            int bIndex = (n - minVal) / bSize;
            if (buckets[bIndex] == null) {
                buckets[bIndex] = new Bucket(n, n);
            } else {
                buckets[bIndex].updateVal(n);
            }
        }

        // for every bucket, check in sequence and get max gap
        int gap = 0;
        int pre = 0;
        int cur = 1;
        while (cur < bCount) {
            // skip all empty buckets
            while (cur < bCount && buckets[cur] == null) {
                cur++;
            }
            if (cur == bCount) break;
            // update gap, pre and cur
            gap = Math.max(gap, buckets[cur].min - buckets[pre].max);
            pre = cur;
            cur++;
        }

        return gap;
    }

    class Bucket {
        int min;
        int max;

        public Bucket(int a, int b) {
            min = a;
            max = b;
        }

        public void updateVal(int val) {
            min = Math.min(min, val);
            max = Math.max(max, val);
        }
    }
}

Question

link

Analysis

This question I’ve seen it quite a few time, also. We’re basically count the number of factor 5s.

Eg.

n = 5, count = 1

n = 6, count = 1

n = 10, count = 2

n = 24, count = 4

n = 25, count = 6

n = 26, count = 6

Solution

Please read this post [LintCode] Trailing Zeros of Factorial.

Code

public class Solution {
    public int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        }
        int res = 0;
        long base = 5;
        while (n >= base) {
            res += n / base;
            base *= 5;
        }
        return res;
    }
}

another pretty good solution:

public class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (int i = n / 5; i > 0; i = i / 5) {
            count = count + i;
        }
        return count;
    }
}

Question

link

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Analysis

This question I’ve seen it quite a few time. It’s very standard integer conversion question.

Solution

Please read this post [ItInt5] Excel Decimal Conversion.

Code

recursively:

public class Solution {
    public String convertToTitle(int n) {
        if (n < 1) {
            return "";
        }
        n--;
        char ch = (char) ((n % 26) + 'A');
        return convertToTitle(n / 26) + ch;
    }
}

Question

link

Explain how you would implement a multi-map in Java without using any collections?

Solution

This question is pretty strange in a tech interview. But still, if you are asked, I think the most obvious solution is pointed out by careercup user Abhi.

The basic idea is to build a nested list structure ourselves, without considering the time complexity. See code below.

Code

public class Node {
    Object key;
    Node next;
    ValueNode vnode;
}
public class ValueNode {
    Object Value;
    ValueNode next;
}