Coursera-Algorithm Week4 Interview Questions

这次的interview questions有一道我觉得很有意思的题，之前没有遇到过。

Inorder traversal with constant extra space. Design an algorithm to perform an inorder traversal of a binary search tree using only a constant amount of extra space.

这道题是Leetcode #94题 Binary Tree Inorder Traversal, 在dicuss中大家的方法大多都是recurssion和iterative的。iterative的话用一个栈解决就可以了。但是没有想到可以用O(1)的空间复杂度就可以解决这个问题。查阅了一些资料之后发现这其实是Morris Traversal的应用。

Morris Traversal的大致思想就是找到当前节点A的左节点的最右子节点B, 将A作为B的右节点，这样避免了用栈来记录整个便利过程。

算法步骤

如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
重复以上1、2直到当前节点为空。

代码实现

// morris traversal
class Solution{
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode p = root;
        while(p != null){
            if(p.left == null){
                res.add(p.val);
                p = p.right;
            }else{
                TreeNode temp = p.left;
                while(temp.right != null && temp.right != p){
                    temp = temp.right;
                }
                if(temp.right == null){
                    temp.right = p;
                    p = p.left;
                }else{
                    res.add(p.val);
                    temp.right = null;
                    p = p.right;
                }
            }
        }
        return res;
    }

}

值得注意的是，尽管这个算法的空间复杂度为O(1)，但是相比于递归和iterative的方法，算法在找最右节点的时候多花费了一些时间。

Dynamic median. Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time. If the number of keys in the data type is even, find/remove the lower median.

这道题在leetcode中也有，可以用两个优先队列解决，一个队列存储比中位数小的数，一个存放更大的数。这两个优先数列一个使用大顶堆，一个使用小顶堆，这样的话获取中位数的时间复杂度只要O(1)。具体代码如下：

class MedianFinder {
    private PriorityQueue<Integer> maxQ = new PriorityQueue<Integer>();
    PriorityQueue<Integer> minQ = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o2 - o1;
			}
        });
    public void addNum(int num) {
        if(minQ.size() == 0 || minQ.peek() >= num){
            minQ.add(num);
        }else{
            maxQ.add(num);
        }
        if(maxQ.size() == minQ.size() + 1){
            minQ.add(maxQ.poll());
        }
        if(maxQ.size() + 2 == minQ.size()){
            maxQ.add(minQ.poll());
        }
    }
    
    public double findMedian() {
        return minQ.size() == maxQ.size() ? (minQ.peek() +maxQ.peek()) / 2.0 : minQ.peek();
    }
}

Randomized priority queue. Describe how to add the methods sample() and delRandom() to our binary heap implementation. The two methods return a key that is chosen uniformly at random among the remaining keys, with the latter method also removing that key. The sample() method should take constant time; the delRandom() method should take logarithmic time. Do not worry about resizing the underlying array.

sample()只要随机出一个随机数i即可；至于delRandom()，将随即出来的A[i]与A[N]交换，删除A[N],再调用swim或者sink函数。

Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of positive integers in two different ways: $a^{3} + b^{3} = c^{3} + d^{3}$. For example, 1729 is the smallest taxicab number: $9^{3}+ 10^{3} = 1^{3} + 12^{3}$. Design an algorithm to find all taxicab numbers with a, b, c, and d less than n.

Version 1: Use time proportional to $n^{2}log⁡n$ and space proportional to $n^{2}$.
Version 2: Use time proportional to $n^{2}log⁡n$ and space proportional to $n$.

Version 1很简单，就是一个4sum的变形。
对于Version2我找了很多资料最后找到了一个最佳解。首先我们将$a^{3} + b^{3}$制成一个矩阵，如图所示。

从图中可以看出每一行和每一列都在逐渐递增，而且我们只需要关注上三角或者下三角即可。利用优先队列来动态的寻找解。在整个过程中始终保持优先队列的size<=N.整个算法如下：
1.从上三角从上往下，从左往右的顺序加入优先队列，直至size为N。
2.弹出优先队列中的最小元素a，如果优先队列peek()仍等于a,则不断弹出并加入解集中。
3.假设上三角中遍历到的元素为b，则比较a与b，如果a=b则加入解集中，否则将b加入优先队列中。
参考网站：keweishang/algorithm_princeton
& stackoverflow

class Taxicab implements Comparable<Taxicab>{
        int n1;
        int n2;
        int cube;

        Taxicab(int n1, int n2) {
            this.n1 = n1;
            this.n2 = n2;
            this.cube = n1 * n1 * n1 + n2 * n2 * n2;
        }

        @Override
        public int compareTo(Taxicab that) {
            if (that.cube > this.cube) return -1;
            if (that.cube < this.cube) return 1;
            return 0;
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Taxicab) {
                if (((Taxicab)o).compareTo(this) == 0)
                return true;
            }
            return false;
        }

        @Override
        public String toString() {
            return "number: " + cube + " (" + n1 + ", " + n2 + ")";
        }
    }

    public void findTaxinumber(int N) {
        MinPQ<Taxicab> candidates = new MinPQ<Taxicab>();

        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                Taxicab t = new Taxicab(i, j);
                if (candidates.size() < N) {
                    candidates.insert(t);
                }
                else {
                    Queue<Taxicab> temp = new Queue<Taxicab>();
                    Taxicab min = candidates.delMin();
                    while (candidates.min().equals(min)) {
                        temp.enqueue(candidates.delMin());
                    }
                    if (!t.equals(min)) {
                        candidates.insert(t);
                    }
                    else {
                        temp.enqueue(t);
                    }
                    if (!temp.isEmpty()) {
                        for (Taxicab taxi: temp) {
                            System.out.println(taxi);
                        }
                        System.out.println(min);
                    }
                }
            }
        }
    }