Monthly Archives: January 2016

Paint house II

Problem:

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example,costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Solution. This problem is pretty similar to Lowest cost to adjust integer array, adjacencies differ less than k.  dp[i][j] is calculated by each value in dp[i – 1] level.

We define dp[][]. Considering we already painted house [0,…,i], dp[i][j] means the minimum price when house i paints with color j.

Let minPos[i] is the color of the lowest price when we paint till house i
min1[i] is the lowest price when we paint till house i.
min2[i] is the second lowest price when we paint till house.

Then we have dp[i][j] = cost[i][j] + {
min1, when j != minPos[i – 1]
min2, when j == minPos[i – 1] }

dp[1][0] = cost[1][0] + min2[0] = 3 + 2

painthouse1

dp[1][1] = cost[1][1] + min1[0] = 2 + 1

painthouse2

No code for this problem because I don’t have premium access to leetcode or test cases.

Contain function() in hashSet

Today when I tried to solve a problem, I came across a weird problem. Look at below code:

public class test {

    static class Point {
        int a;
        public Point(int a) {
            this.a = a;
        }
    }

    public static void test1() {
        Point element = new Point(1);
        HashSet<Point> hs = new HashSet<Point>();
        hs.add(element);
        element.a = 2;
        System.out.println(hs.contains(element));
    }

    public static void test2() {
        HashSet<Integer> element = new HashSet<Integer>();
        HashSet<HashSet<Integer>> hs = new HashSet<HashSet<Integer>>();
        hs.add(element);
        element.add(2);
        System.out.println(hs.contains(element));
    }

    public static void main(String[] args) {
        test1();
        test2();
    }

}

test1 prints true, and test2 prints false. It is confusing. My friend junmin explained me the reason. Check code from JDK:

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

We can see contains() function both checks hashCode() and equals() function. Only when 2 functions return true, it will return true.

Accordingly, if I change the Point class to below, test1() will return false too.

static class Point {
    int a;
    public Point(int a) {
        this.a = a;
    }
    public int hashCode() {
        return a;
    }
}

Ideally, the element in HashSet() should be immutable. Or if we want to change, we should do remove, update, put operations.

Or another way is that we should guarantee that hashCode for new element should be the same as before, and new element should equal to before. But this is actually a worse way. Remember ideally, element in HashSet should be immutable.

 

Generate all combination of parenthesis

Given a number of pair parenthesis. Generate all combinations. For example n = 2, then should return ArrayList<String> = [“(())”, “()()”];

The solution is like below.

public static ArrayList<String> generateParenthesis(int n) {
    // Write your code here
    ArrayList<String> list = new ArrayList<String>();
    parenthesisHelper(0, 0, n, list, "");
    return list;
}

public static void parenthesisHelper(int open, int close, int pair, ArrayList<String> list, String ans) {
    if (close == pair) {
        list.add(ans);
        return;
    }
    if (open < pair) {
        parenthesisHelper(open + 1, close, pair, list, ans + "(");
    }
    if (close < open) {
        parenthesisHelper(open, close + 1, pair, list, ans + ")");
    }
}

This is a very beautiful recursion. Recursion rule is that number of open parenthesis should not be greater than pair number, number of close parenthesis shouldn’t be greater than number of open parenthesis.

my code on github: link

Number of Airplane in the sky

This problem is from lintcode.

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Have you met this question in a real interview?

Yes
Example

For interval list [[1,10],[2,3],[5,8],[4,7]], return 3

Note

If landing and flying happens at the same time, we consider landing should happen at first.

Solution. This is a very interesting problem. The solution is that we can treat start of interval as left parenthesis, end of interval as right parenthesis. The problem will change to find the deepest parenthesis. In order to find the deepest inside parenthesis, we count how many left parenthesis it has. Once there is a right parenthesis, number of left parenthesis decrease 1.

Below is an example to calculate. We can see the max left is 3.
numberofairplane

A tricky part is that we should take care of case of [[1, 3], [1, 3], [1, 3]]. This case return 3. In order to do that, I put <start, 1>, <end, -1> to a TreeMap. If there is already start in hashmap, then we should add <start, value_old + 1>. When we iterate all the parenthesis, we should add value instead 1 each time.

check my code on github: link

 

Longest Increasing Path in a Matrix

This one is from leetcode: link

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]

Solution. We can treat each element in matrix as a node. For 2 adjacent nodes, if node1.value < node2.value. Then there is an edge from node1 to node2. In this way, we can transform the matrix to a graph. The problem changes to find the longest path in a directed graph.

In order to find the longest path in graph, each time, we delete the node which out-degree is zero. The number of iteration is the result. Below is a process to calculate the longest path for the graph. The result is 4.
longestincreasingpathinamatrix

check my code on github: link

Palindrome Permutation II

This one is from leetcode. Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = “aabb”, return [“abba”, “baab”].

Given s = “abc”, return [].

Solution. We should get string where each unique char is only half number of original string. We permutate it. Then we add the result with the reverse part. For example, for “aabb”, we should get all permutation of “ab”, which are “ab” and “ba”. Then we add the reverse part, and we have “abba”, “baab”.

Besides, another case is when there is an odd char. We should put it in the middle position.

Check my code on github: link

Permutation II

https://leetcode.com/problems/permutations-ii/

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Solution. Solution is inspired from here. This is a very good one. First we sort the array. We should set a a used[] array. When we use num[i], if num[i] == num[i – 1], we should check if we move on. If num[i] == num[i – 1], and num[i – 1] is not used, then we shouldn’t move on.

This is a very good case for permutation. I have other permutation case from here.

check my code on github: link

Closest Binary Search Tree Value II

This one is from leetcode. Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

This is a very interesting problem. The best solution is that we maintain a k size window. We traverse tree in-orderly.  Let diffHead = abs(head – target), diffTail = abs(tail – target) and diff = max(diffHead, diffTail). So when k closest elements are in queue, we should have the minimum diff.

Suppose a below binary tree. When target  = 7, k = 3, the process is like:

closestinbt1

closestinbt2

closestinbt3

In this way, we know when nodes are [5, 7, 8], it gets the minimum diff.

check my code on github: link

h-index

https://leetcode.com/problems/h-index/

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Solution. This problem is a pretty easy one. 1st we sort the citation array in ascending order. Then we iterate from left to right in citation array, find the first position where its value is greater than the length between the position and array length.

Let’s think about below function. For point pi, its height is hi, the length from pi to right boundary is li. Basically, we need to find the first pi where hi is greater than li.
h_index

check my code on github: link

Find Celebrity

This one is from leetcode. http://www.cnblogs.com/easonliu/p/4785253.html

Suppose you are at a party with n people (labeled from 0 to n – 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n – 1people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

Solution. As is depicted in the question, celebrity doesn’t know anyone, but anyone knows the celebrity. And we have a know(A, B) function to find if A knows B. If we define that [A knows B] equals to [A > B], and [A doesn’t know B] equals to [A < B]. In this way, the problem transformed to find the lowest value in an array. In this way, we just compare n times.