Leetcode OJ: Recover Binary Search Tree

Recover Binary Search Tree

 

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure. 

An O(n) space algorithm is straight-forward. One can write the in-order traversal of the BST to a linear array, then find the two swapped elements and swap them back.

A better solution is to not explicitly write the in-order traversal to an array. In fact, we can just do an in-order traversal on the BST itself and find the swapped elements in the process. Notice that if we exchange two adjacent (in terms of in-order) nodes, then the logic to find swapped elements is a little different, but this is handled subtly in the code.


However, since the previous solution uses recursion, then the worst case space complexity is the depth of the tree, which could be as bad as O(n).

A tree O(1) space solution requires the used of Threaded Binary Tree, which I learned from other's solution. A threaded binary tree allows one to truly traverse a binary tree with constant space. In our case, we want a forward traversal, so the right child of any node who doesn't have a right child points to its in-order successor. Since we want to preserve the structure, we make that pointing on the fly and recover it after that pointing after use. A threaded binary tree solution is as follows. Notice that we need to find the in-order predecessor of each node twice. The total complexity of finding in-order predecessor of all nodes is O(n), since it's easy to see that every edge is traversed only once. So it is not too bad.

LeetCode OJ: Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

A typical DP. However, a naive O(N^3) time, O(N^2) space solution can not path large test cases. So 3 optimizations are used.

(1) Suppose s and p are of length n and m respectively, then we want to compute a m by n boolean matrix F, where F(i, j) is true if the first i letters of the pattern matches the first j letters of the string. However, we do not need to store then entire matrix, as we can compute the matrix row by row, where the computation of any row only relies on the previous row. Only 2 rows are needed at any time and the space complexity is reduced to O(2*N)

(2) It's easy to see that the '*' is the cause of the O(N^3) complexity, so a simple optimization is to collapse all adjacent '*' into one, which will not change the language represented by the pattern.

(3) When N is very large, like tens of thousand, then even O(N^2) is too slow. We say a non '*' character in the pattern as a hard character, as it must match at least one character from the input string. If we have k hard characters among first i characters of the pattern, then we know F(i, j) must be false if j < k. In this way, we can find a lower and upper bound of j between which F(i, j) can be true for any fixed i. This optimization is especially useful when the pattern is very long, but most of characters in the pattern are hard.

An solution using the above three optimizations is as follows.

LeetCode OJ: Word Ladder I/II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

The above description is for Word Ladder II. Word Ladder one only require you to return the length of shortest path, which will be 5 in the above example.

The output part is basic DFS, and the key part is to find a parent map for the single source shortest path problem. Normally, when we have a graph G(V, E) and a single source s, Dijkstra's algorithm will build a parent map P: V -> V, which can be used to find the shortest path to any destination t from s. P(t) is simply the vetex v, such that path s->...->v->t is the shortest path from s to u. In Word Ladder II, since we are interested in not only one shortest path, but all shortest path, this parent map must be mapping from V to a subset of V, i.e. P: V -> V^2, as there might be more than one parent of a given vertex and we want to get all of them.

A simple modification of Dijkstra will work. Usually, when the temporary minimum distance of a vertex u is updated, we let the vertex v that updates it to be its parent. Now, we add the v to the parent set instead. When the minimum distance is decreased, we clear the original parent set and then add v; when the new distance is the same as the minimum distance, we add the v.

An accepted implementation is as follows:

Notice that we used the adjacency list and priority queue for optimal performance. Otherwise it can not pass the large test cases.

Suppose we have n words in the dictionary, each word is at most m characters long, then a naive way to create the adjacency list by comparing each pair of words suffers O(m*n^2) complexity, which is unacceptable for large n like 20000. In my implementation, we instead find neighbors of a word w by trying to change each of its letters to another one, and the complexity is reduces to (m*n*26).

For the PriorityQueue implementation in Java, decreaseKey operation (decrease the priority of a node given its reference, the priority queue shall rearrange to keep heap property), which is used in Dijkstra's algorithm is not supported. Rather than implement my own priority queue with this operation, I simply insert a node with the decreased key instead. In this way, there will be more than one node for the same vertex in the priority queue, one with the newest/smallest key, whereas the rest are with previous large keys. Since we can keep track of the smallest temporary distance of all the vertices, we can simply ignore a node with key larger than that when doing a removeMin operation. A simple analysis show that this will potential result in larger heap, so the complexity is increased from O(E + VlogV) to O(E + VlogE), which is essentially the same since logE is at most 2logV.

BFS can also be used for this problem since edge weights are uniformly one. Similar, one need to maintain a parent map that is one to many instead of one to one. An BFS implementation is as follows. The running time on LeetCode is not better that the Dijkstra one. Both of them takes more than 1000 ms. Maybe Java is too slow?

LeetCode OJ: Max Points on a Line

This LeetCode problem has the second lowest AC rate. It deserves some attention as it asks for the use of hash table and choice of hash function that requires some thought.

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
note: the points have integer coordinates.

A naive O(n^3) algorithm will consider all pairs of points (p_i, p_j), then for all k != i or j, check whether p_k is on the line defined by p_i and p_j. Identical points needs to be taken care of. An implementation of O(n^3) algorithm is as follows:

A better O(n^2) solution is possible by using hash tables. Notice that this problem is known to be 3SUM-hard so a non-parallel, non-randomized algorithm is unlikely to be better than O(n^2).

To implement a O(n^2) algorithm, one need to create a hash table whose key is encoding of line. One way to encode a line in 2D plan is using slope-intercept form: y = mx + b. However, a and b could be float numbers even if x and y are integers and it is well-known that equality test for float number is error-prone. Instead, I choose to use the standard form: ax + by + c = 0. If we have two distinct points (x1, y1) and (x2, y2), then we can set a = y2 - y1, b = x1 - x2, c = y2 * x1 - y1 * x2, and all of a, b and c will be integers. However, this (a, b, c) is not unique as any integral multiple of it represents the same line. To guarantee uniqueness, we require b to be nonnegative. If b is zero, i.e. the line is vertical, then we require a to be positive. Notice that a and b can not both be zero.

We need to find a good hash function in order to use this (a, b, c) representation as key of hash table. The hash function for hashing integer vectors mentioned in my last post is a good candidate. In particular for the problem at hand, I used:

h(a, b, c) = a + b * 31 + c * 31 ^ 2.

The algorithm itself is straightforward. For each point p_i, we consider all points after it {p_i+1, ..., p_n}. We create a hash table whose key is (a, b, c) tuple and whose value is the number of points in {p_i+1, ..., p_n} that connects to p_i by the line represented by the corresponding key. The the largest value in the constructed hash table is the maximum number of points that lie on the same straight line if the smallest index of those points is i. An implementation is as follows:

Interestingly, the running time of O(n^2) and O(n^3) solutions are not very different on LeetCode OJ, which is probably due to large overhead and small testing cases.

Choice of Hash functions for integer k-tuple in Java

In theory classes, we learn about Universal Hashing, Perfect Hashing, Cuckoo Hashing, Tabulation Hashing, so on and so forth. Most of those techniques enjoy great theoretical value, yet face difficulties in practice. For example, Universal Hashing asks as to encode some randomness into the hashcode() method, which is hard to achieve and we would rather just hard code some coefficient a and b. On the other hand, we rarely in practice need to consider adversarial guarantees. For another example, we simply don't want to afford the creation time and large constant factor of a Perfect Hashing.

We often find ourself just want a hashcode() function for a class whose object is uniquely identified by a k-tuple of integers (a1, a2, ..., ak). Since the HashMap in Java already has a CRC style Hash function to map integer to bins, the hashcode() function only need to convert the k-tuple into a single integer. The following one is what Java uses to hash a String, and is what I suggest to use for hashing k-tuple of integers:

h((a1, a2, ..., ak))
= a1 + a2 * p + a3 * p^2 + ... + ak * p^(k-1)

There is an implicit module operation due to potential integer overflow. Also, it seems people often choose a Mersenne prime for p, such as 31.

Auto Encoder and Matlab tricks

Today, I went through the Auto Encoder exercise by Andrew Ng's CS294A class at Stanford: http://ufldl.stanford.edu/wiki/index.php/Exercise:Sparse_Autoencoder.

The idea of auto encoder is unsupervised feature learning by learning a identity function with sparsity constraints. This idea is very cool by itself, and the exercise is extremely well written. What surprised me is that the quality of the Matlab skeleton code provided and how many Matlab tricks are there that I don't know before. Here is a few of them:

• It turns out that you can do currying in Matlab.
• If you call a function that returns multiple values and receive the return using only one value, then the first returned value is received. This is quite handy sometimes.
• You can add a search path for scripts/functions, so you don't need to put all scripts/functions in the current directory!
• You can save plots to file simply using the 'print' command.

Random Java Tips (1)

This series of blog posts consists of various Java tips and language features that are illusive to normal programmers.

Throwing of exceptions
In Java, there are two types of exceptions, checked exception and unchecked exception. Checked exception, such as FileNotFoundException, must be either caught or re-thrown. However, for unchecked exception, you do not need to do that. But it is still syntactically OK to declare the throwing of them. In fact, you can add "throws X" to any method if X is subclass of Throwable, even if X is an unchecked exception, or if X is an checked exception that is not really thrown at all.

Initialization of arrays
In Java, an array can be declared and initialized at the same time, in the following syntax:
int[] a = new int[] {1, 2, 3, 4}
or
int[] a = {1, 2, 3, 4}  // short-hand of previous one

However, if you can not initialize and designate array size at the same time. I.e. you can not write
int[] a = new int[4] {1, 2, 3, 4}

Syntax for array type
When denoting a variable a of array of type X in Java, you can write either 'X[] a' or 'X a[]'.

For example we can write
int a [] = {1, 2, 3, 4}
But this is not preferred and thought as less readable by most programmers.

Using Bitmap to store canvas paint to optimize UI fluency in Android

This week, I was writing an android program where I have an ImageView that is being updated very frequently. The MVC pattern is used there. Basically, I have a model that stores the location and color of many circles and the ImageView will repaint each of them on its onDraw method, which looks like this: Unfortunately, this scales badly and gets really slow when the circle list in the model gets large. The key to a better solution is that the model only changes a little each time in most cases. In my case, I am removing one circle and adding 4 new circles each time. A better solution will be creating a Bitmap and store it either in the model or the view, so that it is regularly updated when the model changes. Each time the model is changed, we only need to erase one circle and draw another 4 on this Bitmap. For the ImageView, the onDraw method simply load the bitmap, which internally is just a memcpy and takes only a few millisecond. In other words, you don't redraw what is not changed. Finally, you can draw circle on the Bitmap easily by first create a Canvas onto it then draws on the Canvas in exactly the same way you normally do in an onDraw method. The following code snippet is what I used in my program. When I create a Bitmap: When the model changes: This will modify the underlying Bitmap. Of course, the Bitmap must be mutable.

CharSequence in Java

As the first blog in the series, I will start with a rather simple concept, CharSequence in Java.

CharSequence is an interface, that is implemented by useful classes that represent an array of characters, such as CharBuffer, Segment, String , StringBuffer and StringBuilder.

An implementation of CharSequence needs to support only 4 methods, charAt(), length(), substring() and toString(). For method that takes a parameter which is a merely a sequence of characters and if the logic of that method doesn't care about the underlying implementation for that sequence of characters, then a CharSequence shall be used. For example, String class has the following method:

public boolean contains (CharSequence s) 

You can pass any object whose class implemented the CharSequence interface. If String is used as the parameter type, then you have to convert the actual parameter to String if it is not already, which might be a waste of CPU time.

Given its convenience, one shall not use CharSequence as key to map or hash table, because the equals() and hashCode() of CharSequence are not refined by the interface. The original equals() and hashCode() of the class that implements CharSequence is likely to fail when comparing against object of another class that implements CharSequence.

Unlike what its name suggests, a char array, i.e. char[], is not a CharSequence for obvious reason (one is an array of primitive type, the other is an object). There are two ways to convert a char[] carray to a CharSequence:

• CharSequence cs = new String(carray)
• CharSequence cs = CharBuffer.wrap(carray)