3 sum

3 sum

First, 2 sum is needed.

/** first sort, then search target
 *  actually, the problem is as the same as search a target in Young matrix
 *  Notice: repeated number
 */

public class Solution {
    private ArrayList<ArrayList<Integer>> twoSum(int[] num, int startIndex, int target) {
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        int low = startIndex;
        int high = num.length - 1;
        while (low < high) {
            int sum = num[low] + num[high];
            if (sum < target) {
                while (++low < high && num[low] == num[low - 1]);
            } else if (sum > target) {
                while (--high > low && num[high] == num[high + 1]);
            } else {
                ArrayList<Integer> pair = new ArrayList<Integer>();
                pair.add(num[low]);
                pair.add(num[high]);
                rst.add(pair);
                while (++low < high && num[low] == num[low - 1]);
                while (--high > low && num[high] == num[high + 1]);
            }
        }
        return rst;
    }
    
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for (int i = 0; i < num.length - 2;) {
            ArrayList<ArrayList<Integer>> twoSum = twoSum(num, i + 1, -num[i]);
            for (ArrayList<Integer> pair : twoSum) {
                pair.add(0, num[i]);
                rst.add(pair);
            }
            while (++i < num.length - 2 && num[i] == num[i - 1]);
        }
        return rst;
    }
}

sqrt

sqrt

Babylonian method for square root

http://www.geeksforgeeks.org/square-root-of-a-perfect-square/

why (x + y)/2 is always bigger than square root of n:

http://en.wikipedia.org/wiki/Square_root#Geometric_construction_of_the_square_root

public double sqrt(double n) {

    double x = n;

    double y = 1;

    double e = 0.0001

    while (x - y > e) {

        x = x + (y - x) / 2;

        y = n / x;

    }

    return x;

}

BST的中序遍历每个node的next（）函数实现

First, let's write a program to inorder traverse BST using iterative way.

public void inorder(Node node) {
    Stack<Node> stack = new Stack<Node>();
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        visit(node);
        node = node.right;
    }
}

class InorderIterator {
    Stack<Node> stack;
    Node next;
    Node node;
    InorderIterator(Node root) {
        if (root== null) {
            throw new NullPointerException();
        }
        node = root;
        stack = new Stack<Node>();
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        next = stack.pop();
        node = node.right;
    }
    Node next() {
        Node temp = next;
        if (stack.isEmpty() && node == null) {
            thrwo new NoSuchElementException();
        } else {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            next = node;
            node = node.right;
        }
        return temp;
    }
}


public Node next(Node node) {
    if (node.right != null) {
        return leftMost(node.right);
    } else {
        while (node.p != null && node == node.p.right) {
            node = node.p;
        }
        return node.p;
    }
}

public Node next(Node root, Node node) {
    if (node.right != null) {
        return leftMost(node.right);
    } else {
        Node next = null;
        while (root != node) {
            if (node.val <= root.val) {
                next = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return next;
    }
}

Find the maximum repeating number in O(n) time and O(1) extra space

original post: http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). Modifications to array are allowed.

I solved it in Java. The key of this question is how to prove, after first scan, the max element's index is the maximum repeating element.

Prove: Assume mi * k + ai > mj * k + aj && mj > mi && 0 <= ai < k && 0 <= aj < k.
So, ai - aj > (mj - mi) * k. (mi - mj) * k >= k. Therefore, ai - aj > k, which is impossible. so mi >= mj

Note that the above solutions may cause overflow if adding k repeatedly makes the value more than INT_MAX.

800 interview question!

I will try to collect 800 interview question! The category follows the chapter of CC150

1. Arrays and Strings
2. Linked Lists
3. Stacks and Queues
4. Trees and Graphs
5. Bit Manipulation
6. Brain Teasers
7. Mathematics and Probability
8. Object-Oriented Design
9. Recursion and Dynamic Programming

Branch Prediction

original post

The question is 

Why is processing a sorted array faster than an unsorted array?

I got this question from mitbbs, it's a interview question.

在下面这个程序中，如果sort后的totalTime 总是比不sort的totalTime 小，
你可否解释是啥原因？

public class Work {

    public static void main(String args[]) {
    
        int a[] = new int[1000000000];
        
        //fill a
        
        //sort a 
        //do not sort a
        
        starttime=System.currentTimeMillis() 
        for (int i=0;i<a.length;i++) {
            process(a[i]);
        }
        endtime=System.currentTimeMillis() 
        
        totalTime = endtime-starttime;
    }
     
    process(int element) {

     if (element > 256) 
         System.out.println(element);
     else
         System.out.println(element);
     
    }
}