Amazon

High Five

There are two properties in the node student id and scores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.

/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    public Map<Integer, Double> highFive(Record[] results) {
        Map<Integer, Double> ans = new HashMap<>();
        Map<Integer, PriorityQueue<Integer>> minHeapMap = new HashMap<>();

        for(Record r: results){
            if(!minHeapMap.containsKey(r.id)){
                minHeapMap.put(r.id, new PriorityQueue<>(5));
            }
            minHeapMap.get(r.id).add(r.score);
            if(minHeapMap.get(r.id).size() > 5){
                minHeapMap.get(r.id).poll();
            }
        }

        for(Map.Entry<Integer, PriorityQueue<Integer>> entry: minHeapMap.entrySet()){
            double sum = 0.0;
            while(!entry.getValue().isEmpty()){
                sum+=entry.getValue().poll();
            }
            ans.put(entry.getKey(), sum/5);
        }

        return ans;
    }
}

Maximum Minimum Path in Matrix

给一个矩阵,

先找所有从左上到右下的path. 找出每个path的最小值. 找出这些最小值中的最大值.

For Example: [[8,4,3,5] [6,5,9,8]]

所有的path:

8->4->3->5->8 min:3

8->4->3->9->8 min:3

8->4->5->9->8 min:5

8->6->5->9->8 min:5

Result = Math.max(3,3,5,5,) = 5

public static int maxMinPath(int[][] matrix){
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return -1;
    int m = matrix.length, n = matrix[0].length;
    int[][] f = new int[m][n];

    f[0][0] = matrix[0][0];
    for(int i=1; i<m; i++) f[i][0] = Math.min(f[i-1][0], matrix[i][0]);
    for(int j=1; j<n; j++) f[0][j] = Math.min(f[0][j-1], matrix[0][j]);

    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            f[i][j] = Math.min(Math.max(f[i-1][j], f[i][j-1]), matrix[i][j]);
        }
    }
    return f[m-1][n-1];
}