Problem 1: Kth Largest Element in a Stream

Problem Statement: Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Implement the KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Solution in Java:

 import java.util.PriorityQueue;

class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
} 

Analysis:

We use a min-heap of size k to store the k largest elements seen so far. For each new element, we add it to the heap. If the heap size exceeds k, we remove the smallest element (root of the min-heap). The root of the min-heap then represents the kth largest element.

• Time Complexity: O(log k) for each add operation due to heap insertion and deletion. Initialization takes O(N log k) where N is the size of the initial array.
• Space Complexity: O(k) for storing the elements in the heap.

Problem 2: Merge k Sorted Lists

Problem Statement: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Solution in Java:

 import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            tail.next = node;
            tail = tail.next;

            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
} 

Analysis:

We use a min-heap to store the head nodes of all the linked lists. We repeatedly extract the node with the smallest value from the heap, append it to the merged list, and then insert the next node from the same list back into the heap.

• Time Complexity: O(N log k), where N is the total number of nodes in all the linked lists and k is the number of linked lists. We perform N insertions/deletions into the heap, each taking O(log k) time.
• Space Complexity: O(k) for storing the head nodes of the k linked lists in the heap.

Problem 3: Task Scheduler

Problem Statement: You are given a char array tasks representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done without original order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter). Return the least number of units of times that the CPU will take to finish all the given tasks.

Solution in Java:

 import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] taskCounts = new int[26];
        for (char task : tasks) {
            taskCounts[task - 'A']++;
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int count : taskCounts) {
            if (count > 0) {
                maxHeap.add(count);
            }
        }

        int time = 0;
        while (!maxHeap.isEmpty()) {
            int k = n + 1;
            List<Integer> tempTasks = new ArrayList<>();

            while (k > 0 && !maxHeap.isEmpty()) {
                int taskCount = maxHeap.poll();
                taskCount--;
                if (taskCount > 0) {
                    tempTasks.add(taskCount);
                }
                time++;
                k--;
            }

            for (int count : tempTasks) {
                maxHeap.add(count);
            }

            if (maxHeap.isEmpty()) break;

            time += k;
        }

        return time;
    }
} 

Analysis:

The idea is to use a max-heap to track the counts of each task. We iterate and try to schedule n+1 slots. In each slot we schedule tasks with the most counts. If the heap is empty before we fulfill n+1 slots, that means CPU needs to be idle.

• Time Complexity: O(N log 26) = O(N) where N is the length of tasks. In the while loop, the heap operations (poll and add) have time complexity O(log 26) since there are at most 26 types of tasks.
• Space Complexity: O(1), as the size of the heap is bounded by 26 (the number of different task types).