Wednesday, March 23, 2016

Single Elimination Tournament Possibility Problem


This is a real Google onsite interview question.

Problem

Give you a winning rates matrix for each team vs each team, an initial sequence of rivals and a team index, then compute the possibility that this team could be the champion of the whole tournament. The team number would be 2^n.

For example, we have a 4 teams. [0, 1, 2, 3], we have a winning rate matrix:
      x   0.7   0.6   0.5
    0.3     x   0.1   0.2
    0.4   0.9     x   0.4
    0.5   0.8   0.6     x
Solution

Because a team itself will never match itself, so the diagonal of the matrix will not be used.



As the graph shows above, if team 1 wants to be the champion, they need to first beat team 0 and then beat team 3 or team 4. So in this 4 teams scenario, the possibility of team 1 finally win is:

The number on the lower right corner means the winning team and the failed team. P23 means the possibility team 2 beats team 3.

From the formula, we could see that for any round(final, semifinal etc.), for the half that contains the team we specified to be the champion, we just need the possibility that the team make here. But for the other half doesn't contain the specified team, we need all possibilities that any team in this part could make here. Then just compute the possibility as formula shows above.

Because in any round, the scenario is the same. We could use recursion to simplify our computation. The base condition is that we there are just two teams, just return the possibility that specified team beats the other one.

Below is the Python code to solve this question and some test cases.


def single_elimination(poss, matches, num):
    """
    poss: possibility matrix
    matches: intial team index
    num: wanted champion index
    rtype: float
    """

    # base case: when two teams available
    if len(matches) == 2:
        if num == matches[0]:
            return poss[matches[0]][matches[1]]
        else:
            return poss[matches[1]][matches[0]]
    half = len(matches) / 2
    # parts contains the specified team as east, the other part as west
    east = matches[:half] if num in matches[:half] else matches[half:]
    west = matches[half:] if num not in matches[half:] else matches[:half]

    # for the half that contains wanted team
    main = single_elimination(poss, east, num)
    # for the half that doesn't contains wanted team
    sub = [single_elimination(poss, west, team) for team in west]
    # p is the possibility that a team made there,
    # t is other teams index. 
    return sum([p * main * poss[num][t] for p, t in zip(sub, west)])

matrix2 = [
    [0.0, 0.9],
    [0.1, 0.0]
]

matches2 = [0, 1]

matrix4 = [
    [0.0, 0.1, 0.2, 0.3],
    [0.9, 0.0, 0.4, 0.5],
    [0.8, 0.6, 0.0, 0.6],
    [0.7, 0.5, 0.4, 0.0]
]

matches4 = [0, 1, 2, 3, ]
print(single_elimination(matrix2, matches2, 0))
print(single_elimination(matrix2, matches2, 1))


print(single_elimination(matrix4, matches4, 0))
print(single_elimination(matrix4, matches4, 1))
print(single_elimination(matrix4, matches4, 2))
print(single_elimination(matrix4, matches4, 3))

Sunday, April 5, 2015

LeetCode 159 Longest Substring with At Most Two Distinct Characters

problem

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

Solution

The solution is simple, but has a little bit more cases.
We maintain 3 pointer, "first", "second" and a pointer point to current position. Using a hash map, the key of it is the letter, the value is the times of appearances. And a integer record current longest length.
When the current letter is not a new letter for the hash map, just + 1 on its value in hash map.
When the current letter is new to hash map, and the size of hash map is one, put this element into hash map and set its value to 1.
When the current letter is new to hash map but it already has two elements on it, we need to
  1. compute the length once (add all value of the element in hash map together) and may need to update the result,
  2. delete the element not on the current letter's left (the letter that the first pointer pointed to) from hash map. Thinking about the string "aaabbaacccc" when current pointer point to the first "c". We need to delete "b" from hash map.
  3. update the value of the element that second pointer pointed to to (current - second). In the example above, we need to set the value of "a" in hash map from 5 to 2
  4. add new element to hash map and set its value to 1.
At the end of every loop, current letter is not equal to its left letter, set first pointer to the position second pointer point to and set second point to current position.
After the loop, we need to do a extra compute to update the longest length.
The time complexity is O(n) for one pass of the string. Space complexity is O(1) because the hash map at most has two elements.
Here is code with some comment.
public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s == null || s.length() == 0) return 0;
    HashMap map = new HashMap<>(); // Character and number of its appearance
    int first = 0;
    int second = 0;
    int length = 0;
    map.put(s.charAt(0), 1);
    for (int i = 1; i < s.length(); i++) {
        
        // no new letter comes in, just update appearance times
        if (map.containsKey(s.charAt(i))) {
            map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        }
        else {
            // new letter comes in, and just one letter in map
            // simply add the new letter and give value 1
            if (map.size() < 2) { 
                map.put(s.charAt(i), 1); // when less than two elements
            }
            else { 
                // third new element appeared
                // compute how many times the last two letters appeared. 
                int tmpLength = 0;
                for (char letter : map.keySet())
                    tmpLength += map.get(letter);
                length = Math.max(length, tmpLength);
                // delete letter not one the close left of current new letter
                map.remove(s.charAt(first));
                // update the value of the letter close to new letter. 
                map.put(s.charAt(second), i - second);
                // put new letter into map
                map.put(s.charAt(i), 1);
            }
        }
        if (s.charAt(i) != s.charAt(i-1)) {
            first = second;
            second = i;
        }
    }
    // the last two elements haven't count 
    int tmpLength = 0;
    for (char letter : map.keySet())
        tmpLength += map.get(letter);
    return Math.max(length, tmpLength);
}
Written with StackEdit.

Sunday, February 8, 2015

See My Name on neurolab's Contributor List

Last semester, I used neurolab to finish some of my Machine Learning assignments. In the process of using it, I find there are some incomplete and vague on the document. So I sent email to the author of that project and want to help him fix those problems.

The understanding of some function of neurolab is not an easy job because of the document. So after being authorized , I added some sentence to the function I have difficult to understand before.

Several weeks after I made change on document, the author sent me email said that he thanks my contribution and a new version released. Now, you can see my name on change log. This is the first time I actually contribute to a famous (at least to some degree) open source project. I feel good.

Written with StackEdit.

Monday, January 12, 2015

Need a summer internship!

In recent month, I've sent 15 or 20 resumes to different IT companies, but what I have now is only deny. I have to say that a student just learned one semester computer science is pretty hard to get an internship. But I don't just stay at home or library in my 3 months summer vocation or just get an unpaid internship that even impossible to cover foods and traffic cost. $1000 is enough for me.

The most important is to work in industry and know what the feel is when working in a company.

Written with StackEdit.

Friday, January 2, 2015

Binary Inorder Traversal Iterator

Problem

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


For a binary search tree, kept returning the next smallest element is inorder traversal. Wikipedia has some great picture to show how to traversal in "preorder", "inorder" and "postorder". If you are not familiar with this, just go to Wikipedia.

The LeetCode always encourage us use loop other than recursion to solve tree traversal, because recursion may cost more extra space time for program stack and easy to understand.

When I see the problem, my first idea is push all the elements in the tree to a stack. But this cost O(n) memory. So a idea result is pop one from stack and push one to stack. Most method didn't do this precisely, just an amortized O(1) time and O(h) space. If the tree is pretty unbalanced, it is as same as push all the elements in stack. Here is code: private Stack nodes = new Stack<>();

public BSTIterator(TreeNode root) {
    pushToStack(root);
}

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

/** @return the next smallest number */
public int next() {
    TreeNode tmp = nodes.pop();
    pushToStack(tmp.right);
    return tmp.val;
}

private void pushToStack(TreeNode node) {
    while (node != null) {
        nodes.push(node);
        node = node.left;
    }
}

The idea is keep going left until no more elements in left, than to right element and keep going left again. Redo above until no elements in the stack. The problems need to return elements inorder is the same idea. Binary Tree Inorder Tracersal could be solve use the same code structure:

public List<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> nodes = new Stack<>();
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null)
        return result;

    pushToStack(root, nodes);

    while (!nodes.isEmpty()) {
        TreeNode tmp = nodes.pop();
        pushToStack(tmp.right, nodes);
        result.add(tmp.val);
    }
    return result;
}

public void pushToStack(TreeNode node, Stack<TreeNode> nodes) {
    while (node != null) {
        nodes.push(node);
        node = node.left;
    }
}

Written with StackEdit.

Tuesday, December 30, 2014

LeetCode 59 Spiral Matrix

Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].


Solution

Code first:

vector<int> spiralOrder(vector<vector<int> > &matrix) {
    vector<int> result;
    if (matrix.size() < 1) 
        return result;
    int top = 0;
    int button = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while (top <= button && left <= right) {
        for (int x = left; x <= right; x++) { //left to right
            result.push_back(matrix[top][x]);
        }
        top++;

        for (int y = top; y <= button; y++) { //top to button
            result.push_back(matrix[y][right]);
        }
        right--;
        if (button >= top) { // check if the button line haven't been pushed
            for (int x = right; x >= left; x--) {
                result.push_back(matrix[button][x]);
            }
            button--;
        }

        if (right >= left) { //check if the left line haven't been pushed
            for (int y = button; y >= top; y--) {
                result.push_back(matrix[y][left]);
            }
            left++;
        }

    }
    return result;
}

The solution is easy to understand, just iterate upper left -> upper right -> lower right -> lower -> left -> upper left. So we need four variable top, button, left, right to shrink to center step by step. The only tricky part is when we move from right to left and button to top, we should check if there are still space for this two operations. In fact, when I implement this, I debugged almost one hour and than find this.


Written with StackEdit.

LeetCode Rotated Sorted Array Problems

There are 4 problems about rotated sorted array, the sorted array is like [0 , 1, 2, 3, 4, 5], and the rotated sorted array is separating the sorted array to two parts and exchange the position of them. So one rotated array of above is [3, 4, 5, 0, 1, 2]. The fist two problems is Search in Rotated Sorted Array and Search in Rotated Sorted Array II. The difference is the first one's array have no duplicate and the second one may have duplicated elements. The method to solve the two question is the same. Here is the code for first question:

int search(int A[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    int mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (target == A[mid]) {
            return mid;
        }
        if (A[lo] < A[mid]) {// target in left part, when no duplicate, change "<" to "<=".
            if (A[lo] <= target && target <= A[mid]) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
        else if (A[lo] > A[mid]) { //target in right part. when no duplicate, change to else here.
            if (A[mid] <= target && target <= A[hi]) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        else { // handle duplicated cases
            lo++;
        }
    }
    return -1;
}

In fact, the code above also could handle the cases contain duplicated elements. When there are duplicated elements, we do know target in which part, so just let "lo" increase by one. If there have no duplicates, the time complexity is O(logn), just like binary search for a sorted array. if there are duplicated cases, the worst time complexity is O(n) for a array like [3, 3, 3, 3, 1, 3, 3].

The other two problem is Find Minimum in Rotated Sorted Array and Find Minimum in Rotated Sorted Array II. These two questions also could use binary search to solve, and just like the above two problems, the difference is whether there are duplicated elements. Here is the code:

int findMin(vector<int> &num) {
    int lo = 0;
    int hi = num.size() - 1;
    int mid = 0;

    while(lo < hi) {
        mid = lo + (hi - lo) / 2;

        if (num[mid] > num[hi]) { //minimum in right side
            lo = mid + 1;
        }
        else if (num[mid] < num[hi]) { //mininum in left side
            hi = mid;
        }
        else { // when num[mid] and num[hi] are same
            hi--;
        }
    }
    return num[lo];
}

Just as first two questions, this could handle the duplicated elements. This part of problems compare middle elements with "hi" elements, we also could compare middle and "lo" elements.

Written with StackEdit.