Design interview general approach -- tiny url example

1. Understand requirement:
Start from understanding basic functionality. For example, If we need to design a tiny url, we know we want to map a long url to a shorter one.

2. Figure out what data we need to store:
In the tiny url example, it's quite simple: we need to store the actual url and the shorter one (ID).

3. Figure out your database:
Different data requires different DB. It would be easier for  you to start with some relational database and then compare it with NoSQL DB.

In this example, since the structure is so easy, there may not be lots of relations between data, so NoSQL may be a good choice. Here, key may be our generated ID (the tiny url) and the value can be the original url.

4. Think about your API:
How to grab data from DB? How to operate data? How to connect with front end? How to display to your user?
Let's walk through our tiny url example. When we receive a long url, our TinyUrlService interface calls createId(URL url) method to create a new id as the tiny url. There can be multiple ways to implement this method. The easiest one can be having incremental ID. However, as incremental ID only contains numbers, which means there can be at most 100 thousand ones (0 - 99999), and it's hard to scale. One way to optimize is to use Base 64 encoding, and we can increase representation to 64^5 = 2^30 ids. The implementation can be found in my previous post, and you can take a look if you are interested.

Now when the client request the page with the tiny url, our TinyUrlService interface will call getId(ID id) to retrieve the original url from the DB, if it matches, we redirect the page to the original url, otherwise we return code 404.

5. Now think about scalability, reliability and reduce latency:
We have mentioned to use Base 64 encoding to allow more tiny urls, that can be one way for scalability. Using NoSQL for fast query is another way when you have lots of data.

Now another common approach is to use cache. In the tiny url example, Least Frequent Use (LFU) can be a good one. Also you can use some other in-memory storage (e.g., Memcached) for actual caching implementation.

If we have lots of data, we need to think about sharding. Here, since we already have a key, we can just shard by this key. Moreover, think about consistent hash (check this post) so that it's easy to add more machines. (scalability!)

Now if we only have incremental key (with base 64 encoding), it has security issues. So we need to use some hashing mechanism so that the actual key doesn't look like the one shown to the client.

Design chat server

Explain how you would design a chat server. In particular, provide details about the various backend components, classes, and methods. What would be the hardest problems to solve?

1. Understand requirement

When given such a problem, you probably want to discuss with the interviewer what may be the requirements for the chat server. Some ideas can be as follows:

• Personal messaging
• Group messaging
• Sign on/sign off
• Add friend requests

2. Figure out what data we need to store

User relation: User and all his/her friends that he/she can send message to
    user_id, list of friends
Message:
    sender, receiver, time, message_id, content, group_id
    * if message is sent to a group, receiver should be empty or a universal id for all groups.
Device:
    Consider the user has multiple devices, we need to ensure all devices receive messages simultaneously.
    device_id, type, status (enum, online, offline, etc)
***Notification queue:
    To ensure every message is notified to the receivers, we need to store those messages that are waiting to be notified to receivers, in case anything happened with the servers.

3. Figure out your DB

Always start from relational DB. That's easier to understand the relations between different objects and to maintain. For this problem, the relational DB part can be easily figured out from above data types.

4. Think about your API

Now comes the fun part. How to design the whole thing so that our chat server will work.
Let's start from a new user registering to our chat server. So we need a User interface, in which it should have a method called createUser(some parameter). For an existing user, if he or she logs in, we need to grab his/her chat history/profile/etc, so we need another interface, called getUser().
Now if the user wants to send a message, there should be two methods called send(Sender sender, Receiver receiver, Content content) and send(Sender sender, Group group, Content content). These two methods can be put in another interface, called MessageSendingService (or else). The action of sending message will create a new Message object.
Now let's think about the process of sending a message. First the user send a POST request with a new message content. This request will be transformed to an API call to our MessageSendingService, which will call send method and create the message. A new message will then be created and stored in our DB. Now at this point, the message is successfully sent from the sender, so we can send response to sender that the message is successfully sent. The next thing is to notify the receiver. Now we can have another service called MessageNotificationService, which will have a method called createNotificationRequest(Receiver receiver), which will create list of notification requests for each "active" device the user has. "Active" status can be acquired by checking status of the device in device id. The interface can have another method called pushNotification(Message message) which will push push each message to the receiver.
Now there is one more interface we need, which can be called UserRelationManager, which can have two methods, createRelation(User requestUser, User responseUser), which one user will send a "friend" request to another user, and another one, createGroup(User requestUser, List<User> group), which will add all users to a Group object and save to DB.

These are possible interfaces and methods we may need for our API, but there should be more and better solutions.

5. Now think about scalability and reliability

* Think about using NoSQL, how would you denormalize?
* Separate front end, back end and DB. Front end servers only care about transforming client requests and call back end server. Backend servers make API calls, read and write to DB and send response to front end server. This makes things easier later we want to expand our app to mobile or other platforms.
* Check heartbeat
* Using load balancer, replication, caching, batch processing...

6. Think about the hardest problem

* How to guarantee exactly once?
   Retry if message delivery not successful.
   In client side using hash to identify already delivered message.


7. The reality

The actual Facebook chat architecture can be found in this presentation. I wrote this post before I saw this presentation, and I'm happy that the actual implementation doesn't deviate from what I propose.  :)

The challenge in reality is that the "status" field, which in reality is called "Presence", is hard to scale. In FB's implementation, they use an actual set of servers for presence. Presence aggregates online info in memory, and do periodic AJAX polling for list of online friends.

Conversations are stored in log format.

The notification queue is maintained in user bases, i.e., each user has a channel for all his/her devices, , and long-polling is used for delivering messages. Briefly, long-polling is that when client sends a request for a message, the connection between client and server keeps open until new message comes in, or until time out. When the client receives the response, the connection closes and the client files a new request.

Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one. 
The return value is the subtree's size, which is 3.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

Use a struct which contains current subtree number the and the maximum subtree so far. Recursively get the result from the two children. Now if curr is 0 for either tree, it means the node's children are not valid BST, so we only track the maximum subtree seen so far. Otherwise, if current node and its left and right children follows the BST rule, we update the maximum subtree number and current subtree number.

public int largestBSTSubtree(TreeNode root) {
        return getTree(root).max;
    }

    private BSTCounter getTree(TreeNode root) {
        if (root == null) {
            return new BSTCounter(0, 0);
        }
        if (root.left == null && root.right == null) {
            return new BSTCounter(1, 1);
        }
        BSTCounter left = getTree(root.left);
        BSTCounter right = getTree(root.right);
        BSTCounter curr = new BSTCounter(0, 0);
        if (left.curr == -1 || right.curr == -1
            || (root.left != null && root.left.val >= root.val)
            || (root.right != null && root.right.val <= root.val)) {
            curr.curr = -1;
            curr.max = Math.max(left.max, right.max);
        } else {
            curr.curr = left.curr + right.curr + 1;
            curr.max = curr.curr;
        }
        return curr;
    }

    private class BSTCounter {
        int curr;
        int max;
        public BSTCounter(int curr, int max){
            this.curr = curr;
            this.max = max;
        }
    }

Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Union find, easiest solution you can have.

public int countComponents(int n, int[][] edges) {
        UnionFind unionFind = new UnionFind(n);
        for (int[] e : edges) {
            unionFind.union(e[0], e[1]);
        }
        return unionFind.size;
    }

    private class UnionFind {
        int[] roots;
        int size;

        public UnionFind(int n) {
            this.roots = new int[n];
            Arrays.fill(roots, -1);
            size = n;
        }

        public int find(int x) {
            if (roots[x] < 0) {
                return x;
            }
            roots[x] = find(roots[x]);
            return roots[x];
        }

        //false if already in the same union
        //true if successfully union these two vertices
        public boolean union(int x, int y) {
            if (x == y) {
                return false;
            }
            int r1 = find(x);
            int r2 = find(y);
            if (r1 == r2) {
                return false;
            }
            if (roots[r1] > roots[r2]) {
                roots[r1] = r2;
            } else {
                if (roots[r1] == roots[r2]) {
                    roots[r1]--;
                }
                roots[r2] = r1;
            }
            size--;
            return true;
        }
    }

Range Sum Query 2D - Mutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

1. The matrix is only modifiable by the update function.
2. You may assume the number of calls to update and sumRegion function is distributed evenly.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Using Binary index tree, similar as the 1D one, see here for explanation.

public class RangeSumQuery2DMutable {

    int[][] binaryIndexTree;
    int[][] nums;

    public RangeSumQuery2DMutable(int[][] nums) {
        int m = nums.length, n = nums[0].length;
        binaryIndexTree = new int[m][n + 1];
        this.nums = nums;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                add(i, j + 1, nums[i][j]);
            }
        }
    }

    private void add(int row, int col, int val) {
        while (col < binaryIndexTree[row].length) {
            binaryIndexTree[row][col] += val;
            col += (col&-col);
        }
    }

    public void update(int row, int col, int val) {
        add(row, col + 1, val - nums[row][col]);
        nums[row][col] = val;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = 0;
        for (int i = row1; i <= row2; i++) {
            ans += sum(i, col2 + 1) - sum(i, col1);
        }
        return ans;
    }

    private int sum(int row, int col) {
        int ans = 0;
        while (col > 0) {
            ans += binaryIndexTree[row][col];
            col -= (col&-col);
        }
        return ans;
    }
}

Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000](inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

For each point, we use a map to track the distance and number of points seen for this distance. Total number of points with same distance should be x * (x - 1) where x is the number of points with a calculated distance from this point.

    public int numberOfBoomerangs(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        int sum = 0;
        int len = points.length;
        for (int i = 0; i < len; i++) {
            Map distances = new HashMap<>();
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    continue;
                }
                int distance = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                distances.put(distance, distances.getOrDefault(distance, 0) + 1);
            }
            sum += distances.values().stream().mapToInt(x -> x * (x - 1)).sum();
        }
        return sum;
    }

Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

The easiest solution for this problem utilizes union-find. Each time we add a land, first increment the size of the total number of islands, then for each of its neighbors, union them if the neighbor is also an island.

public class NumberOfIslands {
    private int[] rankArray;

    int size, cols, rows;

    public NumberOfIslands (int m, int n) {
        rankArray = new int[m * n];
        this.size = 0;
        this.cols = n;
        this.rows = m;
        Arrays.fill(rankArray, rows * cols + 1);
    }

    public int add(int x, int y) {
        int index = getIndex(x, y);
        rankArray[index] = -1;
        size++;
        int[] neighbors = getNeighbors(x, y);
        for (int n : neighbors) {
            if (n < 0 || rankArray[n] == rows * cols + 1) {
                continue;
            }
            union(index, n);
        }
        return size;
    }

    private int getIndex(int x, int y) {
        return x * cols + y;
    }

    //left, right, down, up
    private int[] getNeighbors(int x, int y) {
        int[] neighbors = new int[4];
        neighbors[0] = x - 1 >= 0 ? getIndex(x - 1, y) : -1;
        neighbors[1] = x + 1 < rows ? getIndex(x + 1, y) : -1;
        neighbors[2] = y - 1 >= 0 ? getIndex(x, y - 1) : -1;
        neighbors[3] = y + 1 < cols ? getIndex(x, y + 1) : -1;
        return neighbors;
    }

    private void union(int index1, int index2) {
        int root1 = find(index1);
        int root2 = find(index2);
        if (root1 == root2)  {
            size--;
            return;
        }
        if (rankArray[root2] < rankArray[root1]) {
            rankArray[root1] = root2;
            size--;
        } else {
            if (rankArray[root1] == rankArray[root2]) {
                rankArray[root1]--;
            }
            rankArray[root2] = root1;
            size--;
        }
    }

    private int find(int index) {
        if (rankArray[index] < 0) {
            return index;
        }
        int root = find(rankArray[index]);
        rankArray[index] = root;
        return root;
    }
}