High Five Scores

Given a list of Result objects which include the id and score of students. Each student will have at least five scores. Calculate the average score of the highest five scores of each student.

/*
Use hashmap to store each student's id and average score. Use priorityqueue to ensure the highest five scores of each student. 

time:O(n), space:O(n)
*/

import java.util.*;

class Result{
    int id;
    int value;
    public Result(int id, int value){
        this.id = id;
        this.value = value;
    }
}
public class Solution {
    public static Map<Integer, Double> getHighFive(Result[] results){
        if (results == null || results.length == 0) {
            return null;
        }
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for (Result result : results) {
            int id = result.id;
            int value = result.value;
            if (!map.containsKey(id)) {
                PriorityQueue<Integer> minheap = new PriorityQueue<>(6);
                minheap.add(value);
                map.put(id, minheap);
            } else {
                map.get(id).add(value);
                if (map.get(id).size() > 5) {
                    map.get(id).poll();
                }
            }
        }
        Map<Integer, Double> resultMap = new HashMap<>();
        for (Map.Entry<Integer, PriorityQueue<Integer>> entry : map.entrySet()) {
            PriorityQueue<Integer> pq = entry.getValue();
            double mark = 0;
            while (!pq.isEmpty()) {
                mark += pq.poll();
            }
            mark = mark / 5.0;
            resultMap.put(entry.getKey(), mark);
        }
        return resultMap;
    }

    public static void main(String[] args) {
        Result r1 = new Result(1, 1);
        Result r2 = new Result(1, 7);
        Result r3 = new Result(1, 7);
        Result r4 = new Result(1, 6);
        Result r5 = new Result(1, 6);
        Result r6 = new Result(1, 6);

        Result r7 = new Result(2, 6);
        Result r8 = new Result(2, 6);
        Result r9 = new Result(2, 7);
        Result r10 = new Result(2, 6);
        Result r11 = new Result(2, 6);
        Result[] arr = {r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11};
        Map<Integer, Double> res = getHighFive(arr);

        System.out.println(res.get(1) + " " +res.get(2));
    }
}

Find K Nearest Points

Given an array containing n points and an origin point, find k nearest points to the origin point in 2D plane.

/*
Maintain a max-heap storing Points. Need to override the Comparator.

time:O(nlogk), space:O(k)
*/

public class kNearestPoints {
    class Point {
        double x;
        double y;
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    public Point[] Solution(Point[] array, Point origin, int k) {
        if (array == null || array.length == 0 || k <= 0) {
            return new Point[0];
        }
        PriorityQueue<Point> pq = new PriorityQueue<>(k + 1, 
                                         new Comparator<Point>(){
            public int compare(Point a, Point b) {
                if (getDistance(b, origin) > 
                    getDistance(a, origin)) {
                    return 1;
                } else if (getDistance(b, origin) < 
                           getDistance(a, origin)) {
                    return -1;
                }
                return 0;
            }  
        });
        for (int i = 0; i < array.length; i++) {
            pq.offer(array[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        Point[] ans = new Point[k];
        int index = k - 1;
        while (!pq.isEmpty()) {
            ans[index--] = pq.poll();
        }
    }
    public double getDistance(Point a, Point b) {
        return (a.x - b.x) * (a.x - b.x) + 
               (a.y - b.y) * (a.y - b.y);
    }
}

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

return -1->2->4->null.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

/*
First put all the ListNode in the input array into the min-heap. Every time,  pop out the ListNode with the smallest value. If this ListNode's next node is not null, then push the next ListNode into the min-heap. 

PriorityQueue. time: O(NlogK), space: O(K), N: the number of all the ListNode，K: the length of the input lists array.
*/

public class Solution {
    private Comparator<ListNode> ListNodeComparator = new                                                Comparator<ListNode>() {
        public int compare(ListNode a, ListNode b) {
            return a.val - b.val;    //b.val-a.val, descending sort.
        }
    };
    public ListNode mergeKLists(ListNode[] lists) {  
        if (lists == null || lists.length == 0) {
            return null;
        }
        Queue<ListNode> heap = new PriorityQueue<>(lists.length,                                                   ListNodeComparator); 
        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node); 
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode head = heap.poll();
            tail.next = head;
            tail = head;
            if (head.next != null) {
                heap.offer(head.next);
            }
        }
        return dummy.next;
    }
}


//divide & conquer, recursion, time: O(NlogK), space: O(1)
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeHelper(lists, 0, lists.length - 1);
    }
    public ListNode mergeHelper(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode left = mergeHelper(lists, start, mid);
        ListNode right = mergeHelper(lists, mid + 1, end);
        
        return mergeTwoLists(left, right);
    }
    private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                temp.next = head1;
                head1 = head1.next;
            } else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        if (head1 != null) {
            temp.next = head1;
        } else {
            temp.next = head2;
        }
        return dummy.next;
    }
}


//merge two by two, iteration, time: O(NlogK), space: O(K)
public class Solution {
    private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                temp.next = head1;
                head1 = head1.next;
            } else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        if (head1 != null) {
            temp.next = head1;
        } else {
            temp.next = head2;
        }
        return dummy.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int index = 0;
        while (lists.length > 1) {
            int l = lists.length;
            ListNode[] newList = new ListNode[(l + 1) / 2];
            for (int i = 0; i + 1 < l; i += 2) {
                ListNode temp = mergeTwoLists(lists[i], 
                                              lists[i + 1]);
                newList[index++] = temp;
            }
            if (l % 2 == 1) {
                newList[index] = lists[l - 1];
            }
            lists = newList;
            index = 0;
        }
        return lists[0];
    }
}


//merge two by two, iteration, time: O(NlogK), space: O(1)
public class Solution {
    private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                temp.next = head1;
                head1 = head1.next;
            } else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        if (head1 != null) {
            temp.next = head1;
        } else {
            temp.next = head2;
        }
        return dummy.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int size = lists.length;
        while (size > 1) {
            for (int i = 0, j = size - 1; i < j; i++, j--) {
                lists[i] = mergeTwoLists(lists[i], lists[j]);
            }
            size = (size + 1) / 2;
        }
        return lists[0];
    }
}