Question

Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

Solution

1. If current node have a right child, return the leftmost leaf of right child.

2. If current node have no right child:

   1. If current is parent’s left child, then return parent node.

   2. If current is parent’s right child, look all the way up until find a right-turning parent.

   3. If all parent is not right-turning. Return null.

Code

written by me

public static TreeNode inorderSucc(TreeNode e) {
    if (e == null)
        return null;
    if (e.right != null) {
        TreeNode p = e.right;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    } else {
        TreeNode p = e.parent;
        while (p != null && p.right == e) {
            e = p;
            p = e.parent;
        }
        return p;
    }
}

Question

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Solution 1

The best solution is to print inorder and preorder traversal of both trees. Find whether the 2 traversal string of T2 is substring of the traversal of T1. This is a very good idea of checking subtree of a Binary Tree.

Updated on Jan 26th, 2015: do we have to use sentinals for this purpose? Well, the answer is NO, cuz a preorder and a inorder can uniquely define a binary tree.

However, this solution is very memory intensive.

Solution 2

The alternative solution simply checks the tree similarity for each and every node.

Time complexity:

If k is the number of occurrences of T2’s root in T1, the worst case runtime can be characterized as O(n + k * m).

However, there can be a lot of pruning for this solution, so it’s NOT necessarily slower than Solution 1. There can be a lot of discussions on this (refer to CC150v5 Q4.8 for more).

Code

written by me

public static boolean containsTree(TreeNode t1, TreeNode t2) {
    if (t1 == null) {
        return false;
    } else if (matchTree(t1, t2)) {
        return true;
    } else {
        return containsTree(t1.left, t2) || containsTree(t1.right, t2);
    }
}

private static boolean matchTree(TreeNode t1, TreeNode t2) {
    if (t2 == null) {
        return true;
    } else if (t1 == null) {
        return false;
    } else if (t1.data != t2.data) {
        return false;
    } else {
        return matchTree(t1.left, t2.left) && matchTree(t1.right, t2.right);
    }
}

Question

link

Given a string, convert it into a palindrome with the lease number of insertions possible.

Solution

This is a DP question. There’re 2 approaches.

First, is direct DP. This is the nicest solution, not intuitive at first, but actually good.

P[i, j] = P[i+1, j-1], if S[i] = S[j]

P[i, j] = 1 + min(P[i,j-1], P[i+1,j]), otherwise

contributed by this guy.

Second approach is to calculate the longest palindrome subsequence, and the answer would be string length minus this value.

I wrote code for both apporaches.

According to G4G, we can actually calculate the Longest Common Subsequence of the string and its reverse, and this value shall be same as the longest palindrome subsequence that we got in second approach. It’s nice to know this idea.

Code

direct

public int solve1(String str) {
    // direct dp
    if (str == null)
        return 0;
    int len = str.length();
    int[][] dp = new int[len][len];
    for (int i = len - 1; i >= 0; i--) {
        for (int j = i; j < len; j++) {
            if (i == j) {
                dp[i][j] = 0;
            } else if (i + 1 == j) {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? 0 : 1;
            } else {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? dp[i + 1][j - 1]
                        : 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][len - 1];
}

longest palindrome subsequence

public int solve2(String str) {
    // longest palindrome subsequence
    if (str == null)
        return 0;
    int len = str.length();
    int[][] dp = new int[len][len];
    for (int i = len - 1; i >= 0; i--) {
        for (int j = i; j < len; j++) {
            if (i == j) {
                dp[i][j] = 1;
            } else if (i + 1 == j) {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? 2 : 1;
            } else {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? 2 + dp[i + 1][j - 1]
                        : Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return len - dp[0][len - 1];
}

Question

link

UTF-8 is a variable-length encoding of letters or runes. If the most significant bit of the first byte is 0, the letter is 1 byte long. Otherwise, its length is the number of leading 1’s in the first byte. If a letter is more than one byte long, all subsequent runes start with 10. Here’s a chart:

UTF-8 encoding scheme is described below:

0XXXXXXX = this is the entire rune
10XXXXXX = this is a continuation of the rune from the previous byte
110XXXXX = this is the start of a 2-byte rune.
1110XXXX = this is the start of a 3-byte rune.
11110XXX = this is the start of a 4-byte rune.
111110XX = this is the start of a 5-byte rune.
1111110X = this is the start of a 6-byte rune.
11111110 = this is the start of a 7-byte rune.
11111111 = this is the start of a 8-byte rune.

For example, a 3-byte rune would be 1110XXXX 10XXXXXX 10XXXXXX.

Write a function that decides whether a given byte array (or string) is valid UTF-8 encoded text.

Solution

This is an easy question, just put here for reference.

Question

link

You are given a graph and an algorithm that can find the shortest path b/w any two nodes.

Now you have to find the second shortest path between same two nodes.

Solution

From the top answer:

Find the shortest path between any two nodes. Let them be A and B.

Now to get second shortest path between the same nodes, remove any one edge that is involved in the shortest path between the same nodes and calculate the shortest path.

Do the above process for each of the node involved in shortest path and keep track of the minimum second shortest path found.

Question

link

数组排序， 排成 a1a3a5。。。这种形式。

Solution

The are 2 solutions. The easy one is this:

sort first, then 把临近的奇数换到偶数(index)上, O(nlog n).

There’s a great O(n) solution however, not easy to think:

两两比较相邻数字，把大的数字放到下标为奇数的位置。 O(n).

Code

O(nlgn) solution

public void solutionOnlgn(int[] A) {
    // this is a O(nlgn) solution
    Arrays.sort(A);
    for (int i = 2; i < A.length; i += 2) {
        swap(A, i - 1, i);
    }
}

private void swap(int[] A, int a, int b) {
    A[a] ^= A[b];
    A[b] ^= A[a];
    A[a] ^= A[b];
}

O(n) solution

public void solutionOn(int[] A) {
    // this is a O(n) solution
    for (int i = 1; i < A.length; i++) {
        // compare (i)th with (i-1)th, and put the large value
        // at odd-indexed positions
        if ((A[i - 1] < A[i] && i % 2 == 0)
                || (A[i - 1] > A[i] && i % 2 == 1)) {
            swap(A, i - 1, i);
        }
    }
}

private void swap(int[] A, int a, int b) {
    A[a] ^= A[b];
    A[b] ^= A[a];
    A[a] ^= A[b];
}

Question

link

String replace, 给一个原string，一个target，一个替换的新str，把所有出现 target str的地方都换成新的str， 长度可以任意.

Solution

If the question asks for an in-place algo, then we can refer to Question 1.5 in CC150v4.

Question

1.5 Write a method to replace all spaces in a string with ‘%20’.

Solution

1. pre-processing, count the number of spaces in string
2. parse the string from end to beginning.

Need 2 pass.

Code

not written by me

public static void ReplaceFun(char[] str, int length) {
    int spaceCount = 0, newLength, i = 0;
    for (i = 0; i < length; i++) {
        if (str[i] == ' ') {
            spaceCount++;
        }
    }
    newLength = length + spaceCount * 2;
    str[newLength] = '\0';
    for (i = length - 1; i >= 0; i--) {
        if (str[i] == ' ') {
            str[newLength - 1] = '0';
            str[newLength - 2] = '2';
            str[newLength - 3] = '%';
            newLength = newLength - 3;
        } else {
            str[newLength - 1] = str[i];
            newLength = newLength - 1;
        }
    }
}

Question

(this question is from MIT handouts B)

Describe a technique to identify a “leader” among a group of 10 identical servers that are all connected to every other server.

There are no prior distinguishing characteristics of any of them and the same program to identify the leader starts running on all of them at the same time. After an answer is given, ask how much network traffic it requires and, if “ties” are possible, ask how you can break ties.

Leader Election

Leader Election is the process of designating a single process as the organizer of some task distributed among several computers. After running this algorithm, each node throughout the network recognizes a unique node as the task leader.

The good answer would be:

Have each server wait a random amount of time and then say “I’m it.” The “I’m it” announcement is time‐stamped, and the computer that time‐stamped its announcement first is elected the leader.

This approach requires sending out 9 messages. If there is a tie, the computers can repeat the procedure.

Observer pattern

The observer pattern is a software design pattern in which an object(subject) maintains a list of dependents(observers), and notifies them automatically of any state changes (usually by calling one of their methods).

The Observer pattern is mainly used to implement distributed event handling systems. It’s also a key part in MVC architectural pattern.

Example

A mailing list example.

Each student in the mailing list would be a listener/observer, and teacher would be announcer/subject.

So in the code, there’s a Listener Interface that all students implement. There’s a update() method in the interface, where each student define their own implementation.

Teacher would keep a list of Listeners. When there’s any news, teacher would call update() on each object.

Question

link

Imagine you had a dictionary. How would you print all anagrams of a word? What if you had to do this repeatedly? Could you optimize it?

Solution

A very nice solution:

1. Open dictionary

2. Create empty hashmap H

3. For each word in dictionary:

   1. Create a key that is the word’s letters sorted alphabetically (and forced to one case)

   2. Add the word to the list of words accessed by the hash key in H

There’s another very interesting idea, if the length of the word is not too long.

Another approach could be we can assign each letters from a..z a prime numbers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, .. so on)

and then for any word, we can calculate its key as the multiples of all the prime number corresponding to characters in the word.

The char -> int assignment may look like:

a=2, b=3, c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=29, 
k=31, l=37, m=41, n=43, o=47, p=53, q=59, r=61, s=67, t=71, 
u=73, v=79, w=83, x=89, y=97, z=101

Code

not written by me, link

private static HashMap<String, ArrayList<String>> anagramMap = new HashMap<String, ArrayList<String>>();

public static void findAnagrams(String[] dictionary) {
    int len = dictionary.length;

    for (int i = 0; i < len; i++) {
        String sortedWord = sortWordLexicographically(dictionary[i]);
        ArrayList<String> wordList = anagramMap.get(sortedWord);
        if (wordList == null) {
            wordList = new ArrayList<String>();
        }
        wordList.add(dictionary[i]);
        anagramMap.put(sortedWord, wordList);
    }
}

public ArrayList<String> getAnagrams(String word) {
    if (word == null) {
        return null;
    }

    String sortedWord = sortWordLexicographically(word);
    return anagramMap.get(sortedWord);
}

public void printAnagrams(String word) {
    if (word == null) {
        System.out.println("Input word is null!");
    } else {
        ArrayList<String> wordList = getAnagrams(word);
        if (wordList == null) {
            System.out.println("No anagrams exists for : " + word);
        } else {
            Iterator<String> iter = wordList.iterator();
            while (iter.hasNext()) {
                System.out.print(iter.next());
            }
        }
    }
}