Design A Typeahead

Reference:

Facebook Typeahead

Screen Shot 2015-09-30 at 10.30.58 PM

1. Preload 1st Degree Data into Browser Cache

Screen Shot 2015-09-30 at 10.41.43 PM

Once Alice clicks the search box, it sends off a request(basically calling first-degree.php in this case) to retrieve all of the user’s direct friends, pages, groups, applications, and upcoming events. Then save it in the browser cache. So that it can immediately show the results without sending another request. 

2. AJAX request and Load Balancer

Screen Shot 2015-09-30 at 10.46.25 PM

Now Alice types ‘B’, it should first show Bob since it is in the browser cache. Then it fires an ajax request (typeahead.php in this case), the load balancer is responsible for routing the request to different servers. Typically each server only handles one specific category of results(friend-of-friend, object-of-friend, events, etc). 

Those blue rectangles are services which could be applied on multiple machines. The global service is for something which are independent to querying user. Like the most popular game or event, since ther we can save latency by storing recent results in a memcached-based query cache.

3. Aggregator

Aggregator delegates queries to multiple lower-level services in parallel and integrating their results.

4. Fetching Data and Validating Results

The results returned by the aggregator are simply a list of ids. The web tier needs to fetch all the data from memcache/MySQL to render the results and display information like the name, profile picture, link, shared networks, mutual friends, etc. The web tier also needs to do privacy checking here to make sure that the searcher is allowed to see each result.

5. Displaying the Results

The results with all the relevant data are sent back to the browser to be displayed in the typeahead. These results are also added to the browser cache along with the bootstrapped connections so that similar subsequent queries don’t need to hit the backend again.

Typeahead Algorithm

 

 

FacebookTwitterGoogle+Share

Paint House I & II

Paint House I

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

//dp[i][j]:minimum cost to paint first i houses with house i to be j color
//dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][j]
//given the color of house i
//find the min total cost to paint first i-1 houses
//0:red, 1:green, 2:blue
//time: O(nk) k: # of colors, n: # of houses
public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    int row = costs.length;
    int col = costs[0].length;
    int[][] dp = new int[row][col];
    //for house 0, dp[0][j] = costs[0][j]
    for (int j = 0; j < col; j++) {
        dp[0][j] = costs[0][j];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 0; j < col; j++) {
            int min = Integer.MAX_VALUE;
            //given the color of house i
            //find the min total cost to paint first i-1 houses
            for (int k = 0; k < col; k++) {
                if (k == j) {
                    continue;
                }
                min = Math.min(min, dp[i - 1][k]);
            }
            dp[i][j] = min + costs[i][j];
        }
    }
    int minCost = Integer.MAX_VALUE;
    //return min in last row
    for (int j = 0; j < col; j++) {
        minCost = Math.min(minCost, dp[row - 1][j]);
    }
    return minCost;
}

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    if (costs[0].length == 1) {
        return costs[0][0];
    }
    int n = costs.length;
    int k = costs[0].length;
    //dp 2d array.
    //minCost[i][j]: minimum cost to paint ith house with color j.
    int[][] minCost = new int[n][k];
    //minColor==i: for the current house, use ith color has smallest total value from house 0 ~ i
    int minColor = -1;

    //init first row(1st house)
    int minValue = Integer.MAX_VALUE;
    int secondMinValue = Integer.MAX_VALUE;
    for (int j = 0; j < k; j++) {
        minCost[0][j] = costs[0][j];
        if (minCost[0][j] < minValue) {
            //Important here!
            //if there is a new min, then we need to compare the old min with the secondMinValue
            secondMinValue = Math.min(secondMinValue, minValue);
            minValue = minCost[0][j];
            minColor = j;
        } else if (minCost[0][j] < secondMinValue) {
            secondMinValue = minCost[0][j];
        }
    }
    int preMinValue, preSecondMinValue, preMinColor;
    for (int i = 1; i < n; i++) {
        preMinColor = minColor;
        preMinValue = minValue;
        preSecondMinValue = secondMinValue;
        minColor = -1;
        minValue = Integer.MAX_VALUE;
        secondMinValue = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            //if minCost[i-1][j] is not the smallest
            if (j != preMinColor) {
                minCost[i][j] = preMinValue + costs[i][j];
            }
            //if minCost[i-1][j] is the smallest
            //then we can only use the second smallest one
            else {
                minCost[i][j] = preSecondMinValue + costs[i][j];
            }
            if (minCost[i][j] < minValue) {
                //Important here!
                //if there is a new min, then we need to compare the old min with the secondMinValue
                secondMinValue = Math.min(secondMinValue, minValue);
                minValue = minCost[i][j];
                minColor = j;
            } else if (minCost[i][j] < secondMinValue) {
                secondMinValue = minCost[i][j];
            }
        }
    }
    return minValue;
}

Phone Screen @AppDynamics

Position: Software Engineer (Data Platform)

  1. Questions about resume
  2. Technical Questions
    Similar to Wildcard Matching but difference is follows:
    Implement wildcard pattern matching with support for '.' and '*'.

    • '.' Matches any single character.
    • '*' Matches zero or more of the preceding character.

    The matching should cover the entire input string (not partial).

     Example
    isMatch("aa","a") → false
    isMatch("aa","aa") → true
    isMatch("a","*") → false //since there is no preceding char of *isMatch("aa","**") → false //* can not be preceding char of another *
    isMatch("aa",".*") → true
    isMatch("aaa","aa") → false
    isMatch("aa", "a*") → true
    isMatch("a", ".*") → true
    isMatch("aab", "c*a*b") → true

Solution:

 

Phone Screen @Box

Position: Software Engineer, Full Stack/Developer Experience

  1. Introduce what they are working on
  2. Technical Questions
    1. Merge two sorted array: just describe the algorithm and time complexity
    2. Merge K sorted array: write the code.
    3. Two Sum: an sorted array, find if there is at least a pair of two elements which the sum equals 0. Just describe the algorithm and time complexity.
      I gave him two approaches: using HashMap and two pointers.
      Then he asked me to write the code with two pointers.
    4. Three Sum: just describe the algorithm and time complexity.

Elevator Design

How would I design the elevators for a new 40 story office

building that had an average of 100 people per floor to most efficiently fill and empty the building given a standard 9-5 workday and traffic conditions in my city? The answer needed to be completely detailed, including expected passengers per car, time per stop, average floors stops per trip at various hours, etc.

1. Ask

  1. How many elevators are there?
  2. What is the capacity of each elevator?
  3. Is the efficiency goal focused only at the start & end of day & not in between (i.e. lunch time, breaks)?

2. General optimal critiera

  • provide even service to each floor
  • minimize how long passengers wait for an elevator to arrive
  • minimize how long passengers spend to get to their destination floor
  • serve as many passengers as possible

The first advice that I’ve read is to ask some questions before you start answering. It will show that you are strategic & don’t jump to random assumptions. So I will probably ask questions like: Is the efficiency goal focused only at the start & end of day & not in between (i.e. lunch time, breaks)? How many elevators are there? What is the capacity of each elevator?

2) Assuming that everything is average, i.e. 6 elevators, 15 people per elevator, and focus only on start and end date, then the sample data should follow a normal distribution.

730-8 – 2%

8-830 – 14%

830-9 – 34%

9-930 – 34%

930-10 – 14%

10-1030 – 2%

3) I will break this down & solve the worst case scenario first. This means, 34 people x 40 floors = 1360 people to be transported by 6 elevator x 15 = total 90 capacity during 830-9 or 9-930 am.

4) Focusing on this more manageable problem, 1360 / 90 means each elevator will make 15 full cycles (lobby to highest floor and back) 5) Since we want to minimize the cycle time for each elevator, we assign one elevator per subset of 40/6 consecutive floors. This should address the issue on minimizing time per stop. 6) That means, the final design should be a load balancing of the elevators by minimizing the travel time — Elevator A – 1st to 7th floor, B – 8th to 14th floor, and so forth. Do you guys see anything wrong with this line of thinking?

先说说我对单个电梯设计的想法(欢迎批评指正)

1 Elevator Object, 应该包含physical components: Door, Indicator Lights,
Control Panel. 一些性质(Non physical properties): Speed, Num of floors,
capacity, max weight. 所能从事的操作methods: moveto, stop, ringbell。然后电
梯应该能够handle user request, 所以还应有一个requestQueue, 电梯应该根据自己
的state 和 requestQueue做出moveto, stop的决定,所以有一component:
requestHandler(Strategy pattern),可以set不同的requestHanlder.

2 Door, properties: State, method: open, close, getState.

3 Indicator light(指示所到楼层),properties: state; method: on, off,
getState

4 Control Panel, 包含physical component: Floor Buttons, Other buttons(也可直
接把Buttons 当作 elevator的components,还没考虑哪一个方法好)

5 Button, properties: floorNum, Parent Elevator, methods: OnPress(Observer
Pattern).

6 ElevatorRequestHandler: handleRequest(Elevator ele, requestList rlist), 可
以define 一个interface, 然后又各种不同实现

7 Request: 可以define 一个abstract class, 然后有子类movingRequest,
helpRequest doorRequest etc.

A Single Elevator

Use Case:

  1. User
    1. press a button to summon the lift
    2. press a button to get to a specific floor
  2. Button
    1. floor button and level button
    2. illuminates when pressed
    3. place an ‘elevator request’ when pressed
  3. Elevator
    1. moves up/down
    2. open/close the door

ElevatorRequests Class

Each button press results in an elevator request which has to be served. Each of these requests is tracked at a global place. ElevatorRequests, the class which stores elevator requests can use different strategies to schedule the elevator requests.

ElevatorController

The elevator is controlled by a controller class which we call ElevatorController. The elevator controller instructs the elevator what to do and also can shutdown/start up the elevator of the building. The elevator controller reads the next elevator request to be processed and serves it.

Button (Abstract) Class

Button is abstract class defining common behavior like illuminate, doNotIlluminate. FloorButton, ElevatorButton extend Button type and define placeRequest() which is invoked when the button is pressed.

In conclusion, ElevatorController runs the show by reading the ElevatorRequests to process and instructing the Elevator what to do. User send request by pressing Buttons.

Extend the answer to multiple elevators

  1. Each elevator have 1 controller.
  2. Floor based requests can be served by any elevator, thus these requests are added to a common area accessible by all controllers.
  3. Each elevator controller runs as a separate thread and checks if it can process a floor request. Mind synchronization issues.

http://www.columbia.edu/~cs2035/courses/ieor4405.S13/p14.pdf

https://github.com/joeblau/sample-elevator-control-system

http://blog.jobbole.com/74672/

http://blog.gssxgss.me/elevator-simulator-java/

Count Univalue Subtrees

Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Solution:

public int countUnivalSubtrees(TreeNode root) {
    int[] count = new int[1];
    isUnivalSubtrees(root, count);
    return count[0];
}

public boolean isUnivalSubtrees(TreeNode root, int[] count) {
    if (root == null) {
        return false;
    }
    boolean left = isUnivalSubtrees(root.left, count);
    boolean right = isUnivalSubtrees(root.right, count);
    if (!left && !right) {
        if (root.left == null && root.right == null) {
            count[0]++;
            return true;
        }
    } else if (left && right) {
        if (root.left.val == root.val && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (left && !right) {
        if (root.right == null && root.left.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (!left && right) {
        if (root.left == null && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    }
    return false;
}

Ugly Number I & II

Ugly Number I

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        if (num == 1) {
            return true;
        }
        int[] factors = {2, 3, 5};
        for (int i = 0; i < factors.length; i++) {
            while (num % factors[i] == 0) {
                num = num / factors[i];
            }
        }
        return num == 1;
    }

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

https://leetcode.com/discuss/52716/o-n-java-solution

Solution:

O(n) time, one pass solution. O(n) space.

The idea of this solution is from this page:http://www.geeksforgeeks.org/ugly-numbers/

The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5.

Then we use similar merge method as merge sort, to get every ugly number from the three subsequence.

Every step we choose the smallest one, and move one step after,including nums with same value.

    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for (int i = 1; i < n; i++) {
            int min = Math.min(Math.min(factor2, factor3), factor5);
            ugly[i] = min;
            if (factor2 == min) {
                index2++;
                factor2 = 2 * ugly[index2];
            }
            if (factor3 == min) {
                index3++;
                factor3 = 3 * ugly[index3];
            }
            if (factor5 == min) {
                index5++;
                factor5 = 5 * ugly[index5];
            }
        }
        return ugly[n - 1];
    }

Union-Find 并查集

Union-Find is an algorithm which is widely used to solve finding disjoint components.

void init(int[] nums) {
    int[] fathers = new int[nums.length];
    //initially, father is itself
    for (int i = 0; i < nums; i++) {
        fathers[i] = i;
    }
}

//find the father for both nodes
//if they are in different groups, union them by setting fathers[xFather] = yFather;
void union(int x, int y, int[] fathers) {
    int xFather = findAndSet(x, fathers);
    int yFather = findAndSet(y, fathers);
    fathers[xFather] = yFather;
}

//recursively find its parent until reach the top which its parent is itself
//to improve the performance, we compress the path by setting the top father
//so that next time we call find, it is O(1) time complexity
int findAndSet(int x, int[] fathers) {
    int parent = fathers[x];
    while (parent != fathers[parent]) {
        parent = fathers[parent];
    }
    return parent;
}

Related Questions:

1. Graph Valid Tree Medium

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 check whether these edges make up a valid tree.

For example:

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

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

    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 algorithm
    //findSet is a faster version of find method which finds the top father of a node
    //and then set the father to
    //which basically compress the path.
    //another improvement could be: only
    public boolean validTree(int n, int[][] edges) {
        int[] fathers = new int[n];
        for (int i = 0; i < n; i++) {
            fathers[i] = i;
        }
        for (int i = 0; i < edges.length; i++) {
            //union
            int xfather = findSet(edges[i][0], fathers);
            int yfather = findSet(edges[i][1], fathers);
            //since there is no duplicate edge(important! otherwise this algorithm is wrong)
            //so if xfather == yfather means they are in
            if (xfather == yfather) {
                return false;
            }
            fathers[xfather] = yfather;
        }
        //there should only be one node(root) pointing to itself
        int count = 0;
        for (int i = 0; i < fathers.length; i++) {
            if (fathers[i] == i) {
                count++;
            }
        }
        return count == 1;
    }
    
    public int findSet(int x, int[] fathers) {
        int parent = fathers[x];
        while (parent != fathers[parent]) {
            parent = fathers[parent];
        }
        fathers[x] = parent;
        return parent;
    }

    2. Find the Connected Component in the Undirected Graph

    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        //init unions
        Map<Integer, Integer> fathers = new HashMap<>();
        for (UndirectedGraphNode node : nodes) {
            int label = node.label;
            if (!fathers.containsKey(label)) {
                fathers.put(label, label);
            }
            for (UndirectedGraphNode neighbor : node.neighbors) {
                union(label, neighbor.label, fathers);
            }
        }
        //put it into a new map which key is the father of the component
        //value is a list of node within the component
        Map<Integer, List<Integer>> components = new HashMap<>();
        for (Integer label : fathers.keySet()) {
            int father = findAndSet(label, fathers);
            if (components.containsKey(father)) {
                components.get(father).add(label);
            } else {
                List<Integer> component = new ArrayList<>();
                component.add(label);
                components.put(father, component);
            }
        }
        //sort the result
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> component : components.values()) {
            Collections.sort(component);
            res.add(component);
        }
        return res;
    }
    
    public void union(int x, int y, Map<Integer, Integer> fathers) {
        int xFather = findAndSet(x, fathers);
        int yFather = findAndSet(y, fathers);
        if (xFather != yFather) {
            fathers.put(xFather, yFather);
        }
    }
    
    public int findAndSet(int label, Map<Integer, Integer> fathers) {
        if (!fathers.containsKey(label)) {
            fathers.put(label, label);
            return label;
        }
        int parent = fathers.get(label);
        while (parent != fathers.get(parent)) {
            parent = fathers.get(parent);
        }
        fathers.put(label, parent);
        return parent;
    }

    3. Find the Weak Connected Component in the Directed Graph

    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        //init unions
        Map<Integer, Integer> fathers = new HashMap<>();
        for (DirectedGraphNode node : nodes) {
            int label = node.label;
            if (!fathers.containsKey(label)) {
                fathers.put(label, label);
            }
            for (DirectedGraphNode neighbor : node.neighbors) {
                union(label, neighbor.label, fathers);
            }
        }
        //put it into a new map which key is the father of the component
        //value is a list of node within the component
        Map<Integer, List<Integer>> components = new HashMap<>();
        for (Integer label : fathers.keySet()) {
            int father = findAndSet(label, fathers);
            if (components.containsKey(father)) {
                components.get(father).add(label);
            } else {
                List<Integer> component = new ArrayList<>();
                component.add(label);
                components.put(father, component);
            }
        }
        //sort the result
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> component : components.values()) {
            Collections.sort(component);
            res.add(component);
        }
    
        return res;
    }
    
    public void union(int x, int y, Map<Integer, Integer> fathers) {
        int xFather = findAndSet(x, fathers);
        int yFather = findAndSet(y, fathers);
        if (xFather != yFather) {
            fathers.put(xFather, yFather);
        }
    }
    
    public int findAndSet(int label, Map<Integer, Integer> fathers) {
        if (!fathers.containsKey(label)) {
            fathers.put(label, label);
            return label;
        }
        int parent = fathers.get(label);
        while (parent != fathers.get(parent)) {
            parent = fathers.get(parent);
        }
        fathers.put(label, parent);
        return parent;
    }