Twitter University Recruit Coding Challenge 2020
Anonymous User
1075
Interview
  1. Give value k, find distinct pairs [a, b] that the gap between a and b is k, return how many pairs we can find in the giving list.
    Method: like "two sum", we can use PriorityQueue(minHeap) and HashSet.
public int findPair(List<Integer> list, int k){
		// by using heap to sort the list
        HashSet<Integer> set = new HashSet<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i : list){
            set.add(i);
            pq.add(i);
        }
        int count = 0;
        while(!pq.isEmpty()){
            int x = pq.remove();
            if(set.contains(x + k)){
                count++;
            }
        }
        return count;
    }

2.Paint house. we have 3 colors to choose, the color of adjacent house cannot be the same. Each house has different costs in painting different colors, we need to find the min cost to paint all houses.(Using dp to solve)

public static int minPrice(List<List<Integer>> cost){
        int n = cost.size();
        for(int i = 1; i < n; i++){
            int tmp1 = cost.get(i).get(0);
            int tmp2 = cost.get(i).get(1);
            int tmp3 = cost.get(i).get(2);

            cost.get(i).set(0, tmp1 + Math.min(cost.get(i-1).get(1), cost.get(i-1).get(2)));
            cost.get(i).set(1, tmp2 + Math.min(cost.get(i-1).get(0), cost.get(i-1).get(2)));
            cost.get(i).set(2, tmp3 + Math.min(cost.get(i-1).get(0), cost.get(i-1).get(1)));
        }
        return Math.min(cost.get(n-1).get(0), Math.min(cost.get(n-1).get(1), cost.get(n-1).get(2)));
    }
  1. Search whether (x1,y1) can reach to (x2,y2), (x1, y1) can only move to (x1+y1, y1) or (x1, y1+x1) each time.
    Method: It is a search problem, using dfs to search until x1>x2 || y1 > y2
public boolean searchPoint(int x1, int y1, int x2, int y2){
        return search(x1, y1, x2, y2);
    }

    public boolean search(int x1, int y1, int x2, int y2){
        if(x1 > x2 || y1 > y2){
            return false;
        }
        if(x1 == x2 && y1 == y2){
            return true;
        }

        int[][] dir = {{x1+y1, y1}, {x1, y1+x1}};

        for(int i = 0; i < dir.length; i++){
            int newX1 = dir[i][0];
            int newY1 = dir[i][1];
            if(search(newX1, newY1, x2, y2)){
                return true;
            }
        }
        return false;
    }
  1. Each task has a number, and each task has a weight, there is a tool can process same task twice at the same time (multi-threads). Try to find the max weight with the sum of task number <= p.
    Method：dp, compare if we choose the task or if we do not choose the task.
public static int maximumTotalWeight(List<Integer> weights, List<Integer> tasks, int p) {
        // dp, like a knapsack problem
        int[][] dp = new int[tasks.size() + 1][p + 1];

        // initialize the tasks
		// because the problem says the processor can handle "Double" (just like multi-threads)
        for(int i = 0; i < tasks.size(); i++){
            int tmp = tasks.get(i);
            tasks.set(i, tmp * 2);
        }

        // use j to traverse the p value
        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[0].length; j++){
                // if task is bigger than j, we can not add more task
                if(j < tasks.get(i-1)){
                    dp[i][j] = dp[i-1][j];
                }else{
                    // put weight(i-1) into the bag and compare
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - tasks.get(i-1)] + weights.get(i-1));
                }
            }
        }
        return dp[tasks.size()][p];
    }
Comments (2)