Question

link

Given a very long list of URLs, find the first URL which is unique ( occurred exactly once ).

Must do it in one traversal.

Solution

Suggested by the top answer and second answer, using a combination of trie and linked list.

1. The leaf node of a trie maintains a flag to record duplicate urls and pointer to a node in a link list.

2. Use a doubly linked list to link all the unique ones

3. Remove the URL from the list if its count goes over 1
4. So after one traversal, the first one of your linked list is the desired one.

Alternatively, we can also use Hash instead of Trie.

Code

not written

Question

link

给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够流向任意海洋的点。 比如说

0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3

那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增 路线），当然也有可能找不到这样的点，或者找到多个点。

Solution

I read online and the best solution I come up with is Brute Force. I did not really understand the online discussions.

So if you are reading this and want to discuss with me, kindly leave me a comment!

Code

brute force

public void findSuperPeak(int[][] map) {
    int m = map.length;
    int n = map[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (check(map, new Pair(i, j), m, n)) {
                System.out.println("Found point (" + i + ", " + j
                        + ") with height of " + map[i][j]);
            }
        }
    }
}

private boolean check(int[][] originalMap, Pair p, int m, int n) {
    // check if point can flow to all oceans
    if (originalMap[p.x][p.y] == 0) {
        return false;
    }

    int[][] map = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = originalMap[i][j];
        }
    }

    Queue<Pair> q = new LinkedList<Pair>();
    q.offer(p);

    while (!q.isEmpty()) {
        Pair top = q.poll();
        int x = top.x;
        int y = top.y;
        if (map[x][y] == -1) {
            continue;
        }
        // add neighbor nodes who are visitable from here
        if (x - 1 >= 0 && map[x - 1][y] <= map[x][y]) {
            // water can flow from:
            // 1. high altitude to lower
            // 2. from ocean to ocean
            q.offer(new Pair(x - 1, y));
        }
        if (x + 1 < m && map[x + 1][y] <= map[x][y]) {
            q.offer(new Pair(x + 1, y));
        }
        if (y - 1 >= 0 && map[x][y - 1] <= map[x][y]) {
            q.offer(new Pair(x, y - 1));
        }
        if (y + 1 < n && map[x][y + 1] <= map[x][y]) {
            q.offer(new Pair(x, y + 1));
        }

        // visit this point
        map[x][y] = -1;
    }

    // now we finished BFS and the entire map with lower altitude is visited
    // (including all ocean points). We now check if there exists a 0 in map
    for (int[] arr : map)
        for (int i : arr)
            if (i == 0) // found an unvisited ocean point
                return false;
    return true;
}

Question

RT. This is a very very common requirements in the area of string manipulation. We want it to be done very efficiently.

Solution

Normally, we would use a hashmap. However, we can also use bitmask or bitmap.

Work for a-z only, we use 1 integer to represent each letter, and set an integer for each string.

We do (mask1 & mask2 == 0) to find no common letters. Read more at this question, [Google] Max prodcut of strings that have no common char.

Question

We have a history of match result of pingpong games, assume each match is <player1, player2, result, timestamp>, player1 and player2 are long type, result is a bit value (1 means player1 win).

design a algorithm to sort the players by their possibility to win future games.

Solution

For each play,

winning score = score_diff * {delay factor^{current time - winning time}};

Pagerank

PageRank is what Google uses to determine the importance of a web page.

It determines which pages appear in search results.

Named after Larry Page.

Details

1. PageRank thinks of links as votes to another page.

2. It also looks at the importance of the page that contains the link.

   1. Pages with higher PageRank have more weight in “voting”.

   2. Pages with smaller total number of links on the page have more weight.

Increase your PageRank?

If you’d like to increase your PageRank, you need to have “back-links,” or other people linking to your website. You can trade links with other people, but make sure you only trade relevant links, and make sure you’re not trading links with a link farm.

You can register your website with directories, such as the Open Directory Project, but use directories with high PageRank whenever possible.

You can create some of your own back-links by linking to relevant pages within your own website. However, remember that the number of links you create counts into the equation. Don’t overdo it.

Question

link

Give a list of documents, find the minimal document set that can cover all the characters in all the documents.

eg.

“a b c h j”,  
"c d”, 
“a b c” 
“a f g” 
“a h j”

The result should be

"a b c h j" 
"c d" and 
"a f g"

Solution

Set cover problem is NP.

DP solution is available here, with O(2 ^ n) time complexity.

T[i][X] denotes the minimal number of sets out of {S1, S2, … , Si} that covers X.

So we have:

T[i][X] = min(1 + T[i − 1][X - Si], T[i − 1][X])

Code

not written

Publish–subscribe pattern

The publish–subscribe pattern is a messaging pattern where senders of messages, called publishers, do not send messages directly to specific subscribers. Instead, published messages are characterized into classes without knowledge of subscribers.

Similarly, subscribers express interest in one or more classes, without knowledge of what publishers there are.

1. greater network scalability
2. a more dynamic network topology
3. decreased flexibility to modify the Publisher and its structure of the data published.

Pub/sub is typically a part of a larger message-oriented middleware system. e.g. Java Message Service (JMS).

Difference w/ observer pattern

Refer to [Java OOP] Observer pattern or this link:

Observer, or Observable/Observer:

A design pattern by which an object is imbued with the ability to notify others of specific events - typically done using actual events, which are kind of like slots in the object with the shape of a specific function/method. The observable is the one who provides notifications, and the observer receives those notifications. In .net, the observable can expose an event and the observer subscribes to that event with an “event handler"shaped hook. No assumptions are made about the specific mechanism which notifications occur, nor about the number of observers one observable can notify.

Pub/Sub:

Another name (perhaps with more “broadcast” semantics) of the Observable/Observer pattern, which usually implies a more “dynamic” flavor - observers can subscribe or unsubscribe to notifications and one observable can “shout out” to multiple observers. In .net, one can use the standard events for this, since events are a form of MulticastDelegate, and so can support delivery of events to multiple subscribers, and also support unsubscription. Pub/sub has a slightly different meaning in certain contexts, usually involving more “anonymity” between event and eventer, which can be facilitated by any number of abstractions, usually involving some “middle man” (such as a message queue) who knows all parties, but the individual parties don’t know about each other.

Question

link

Multiple threads can publish and receive each other’s message:

1. whenever a thread publishes a message, all the other threads can receive and print out that message;

2. if multiple message get published, the messages should be queued or whatever recorded and other threads can print out the message one by one;

3. no published message should be missed by any other threads.

Solution

Suggested by level 13:

给每个thread分一个blocking queue就完了。这题延伸开来是个很好的设计题, pubsub, messaging framework etc.

Using a blocking queue to store messages for each server. It’s pretty much like consumer-producer. But here, the server takes on both roles. Read my code below, or [Java OOP] PubSub (Publish–subscribe) pattern to learn about PubSub.

Code

Below is my code, it may not be the correct solution. If you would like to discuss, please leave me a comment!

public class MessagingServer implements Runnable {

    String serverId;
    List<MessagingServer> servers;
    BlockingQueue<String> messages;
    boolean isFinished;

    public MessagingServer(String id, List<MessagingServer> list, int qSize) {
        this.serverId = id;
        this.servers = list;
        messages = new ArrayBlockingQueue<String>(qSize);
        isFinished = false;
    }

    public void run() {
        // this would be the consumer
        // everything that is added to BlockingQueue<String> messages is printed
        while (!isFinished) {
            String msg;
            try {
                msg = messages.take();
                System.out.println(serverId + " says: " + msg);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public void sendMessage(String msg) {
        // this is the producer

        // insert this msg in the blockingQ of all other servers
        for (MessagingServer server : servers) {
            server.messages.add(msg + " (received from " + this.serverId + ")");
        }
    }

    public void terminate() {
        this.isFinished = true;
    }
}

Question

link

Implement a Blocking queue.

Solution

First thing first, the most important characteristic of a BlockingQueue is:

thread-safe BlockingQueue

Second, we need to make sure to handle the following 2 methods:

notifyAll();

wait();

Last, remember that wait() has got a checked exception(InterruptedException). We end up with the code:

public synchronized void enqueue(Object item) throws InterruptedException {
    while (this.queue.size() == this.size) {
        wait();
    }
    if (this.queue.size() == 0) {
        notifyAll();
    }
    this.queue.add(item);
}

Code

The entire class, refer to [Java OOP] Java BlockingQueue (2):

public class MyBlockingQueue {

    private List<Object> queue = new LinkedList<Object>();
    private int size = 10;

    public MyBlockingQueue(int size) {
        this.size = size;
    }

    public synchronized void enqueue(Object item) throws InterruptedException {
        while (this.queue.size() == this.size) {
            wait();
        }
        if (this.queue.size() == 0) {
            notifyAll();
        }
        this.queue.add(item);
    }

    public synchronized Object dequeue() throws InterruptedException {
        while (this.queue.size() == 0) {
            wait();
        }
        if (this.queue.size() == this.size) {
            notifyAll();
        }

        return this.queue.remove(0);
    }

    public boolean isEmpty() {
        return this.queue.isEmpty();
    }
}

Question

link

Given a board of snakes and ladders game, provide an algorithm to find the minimum number of dice rolls required to reach 100 from 1.

Solution 1

Recommended: Graph (shortest path). ref:

1. k is linked to k + 1 k + 2, k + 3, k + 4, k + 5, k +6.

2. If has a ladder, connect it too.

3. Find shortest path.

Solution 2 is DP.

Variant

If the question asks: find the way to climb as many ladder as possible. Then this question would be solved differently.

Any ideas?

Solution below.

…

…

…

Read [Greedy] Activity Selection Problem.

Code

not written

Question

link

an arbitrary tree. split it into as many subtrees as you can. the number of nodes of the subtree must be even.

Solution

This is a difficult question. The idea is recursive solution, but be cautious deadling with NULL.

NULL can be regarded as a child branch of even node (0), but NULL could not be seen as a subtreee.

1. traverse each and every node in the tree
2. for each node, take it as root, and find left and right branch with total sum of odd count of nodes.
3. we do above step recursively
4. include NULL as a subtree of EVEN number of nodes.

The code below is my code and I haven’t seen any reference to this question. If you read this, please comment and discuss with me!

Code

public void traverseAndFindEvenSubstrees(List<TreeNode> ans, TreeNode node) {
    if (node == null) {
        return;
    }
    List<TreeNode> evenSubtrees = this.getSubtrees(node, true);
    evenSubtrees.remove(null);
    ans.addAll(evenSubtrees);

    traverseAndFindEvenSubstrees(ans, node.left);
    traverseAndFindEvenSubstrees(ans, node.right);
}

private List<TreeNode> getSubtrees(TreeNode root, boolean isEven) {
    List<TreeNode> ans = new ArrayList<TreeNode>();
    if (root == null) {
        if (isEven) {
            // NULL is considered as a subtree with even number (0) of nodes
            ans.add(null);
        }
        return ans;
    }
    if (isEven) {
        // we need 2 subtrees to have a combined nodes of odd numbers
        for (int i = 0; i <= 1; i++) {
            List<TreeNode> leftGroup = getSubtrees(root.left, i == 0);
            List<TreeNode> rightGroup = getSubtrees(root.right, i != 0);
            // what we do here, is to make leftGroup and rightGroup have
            // different boolean parameter, thus a total of odd count
            for (TreeNode ln : leftGroup) {
                for (TreeNode rn : rightGroup) {
                    // note that NULL is included in either leftGroup or
                    // rightGroup. we'll use that
                    TreeNode newSubtree = new TreeNode(root.val);
                    newSubtree.left = ln;
                    newSubtree.right = rn;
                    ans.add(newSubtree);
                }
            }
        }
        // now we've added all subtrees into ans, whose head is the root
        // this means we does not inlcude NULL
    } else {
        for (int i = 0; i <= 1; i++) {
            List<TreeNode> leftGroup = getSubtrees(root.left, i == 0);
            List<TreeNode> rightGroup = getSubtrees(root.right, i == 0);
            for (TreeNode ln : leftGroup) {
                for (TreeNode rn : rightGroup) {
                    TreeNode newSubtree = new TreeNode(root.val);
                    newSubtree.left = ln;
                    newSubtree.right = rn;
                    ans.add(newSubtree);
                }
            }
        }
    }
    // now last step, add NULL (important)
    if (isEven) {
        ans.add(null);
    }
    return ans;
}

Test data:

Test start
Input is a BST with this structure: 
4 
2 6 
1 3 5 7 

Total subtree count = 16
They are: 
Tree 1:
4 
2 6 
3 
Tree 2:
4 
2 6 
3 5 7 
Tree 3:
4 
2 6 
1 
Tree 4:
4 
2 6 
1 5 7 
Tree 5:
4 
6 
Tree 6:
4 
6 
5 7 
Tree 7:
4 
2 6 
7 
Tree 8:
4 
2 6 
5 
Tree 9:
4 
2 
Tree 10:
4 
2 6 
1 3 7 
Tree 11:
4 
2 6 
1 3 5 
Tree 12:
4 
2 
1 3 
Tree 13:
2 
3 
Tree 14:
2 
1 
Tree 15:
6 
7 
Tree 16:
6 
5 
Total time = 0.006