Maximum CPU Load (Peak Overlap)

🎯

Maximum CPU Load (Peak Overlap)

mediumHEAPAmazonGoogle

Imagine a cloud server running multiple tasks simultaneously, each consuming some CPU load. To avoid overload, you want to find the peak CPU usage at any time.

💡 This problem is about finding the maximum overlap of intervals weighted by CPU load. Beginners often struggle because they try to check all pairs or intervals naively, missing efficient data structures like heaps or sweep line techniques.

📋

Problem Statement

Given a list of jobs where each job has a start time, an end time, and a CPU load, find the maximum CPU load at any time if all jobs are running on the same machine.

1 ≤ n ≤ 10^50 ≤ start time < end time ≤ 10^91 ≤ CPU load ≤ 10^4

💡

Example

Input"[[1,4,3], [2,5,4], [7,9,6]]"

Output7

Jobs 1 and 2 overlap between time 2 and 4, total load = 3 + 4 = 7. Job 3 does not overlap with others.

• All jobs non-overlapping → max load is max single job load
• All jobs fully overlapping → max load is sum of all loads
• Jobs with same start and end times → count all loads at that instant
• Single job only → max load is that job's load

⚠️

Common Mistakes

Not sorting jobs by start time before processing

Heap or sweep line logic fails, incorrect max load

✅ Always sort jobs or events by start/time before processing

Incorrectly checking overlap conditions in brute force

Missed overlaps or double counting, wrong max load

✅ Use correct condition: jobs[j][0] < jobs[i][1] and jobs[j][1] > jobs[i][0]

In sweep line, not handling events with same timestamp properly

Load calculation errors, off-by-one mistakes

✅ Process start events before end events if timestamps equal

Forgetting to subtract load of ended jobs from current load in heap approach

Current load accumulates incorrectly, max load too high

✅ Pop ended jobs from heap and subtract their loads before adding new job

Using data structures with poor performance for large n

Solution times out or runs slowly

✅ Use efficient sorting and heap or sweep line with O(n log n) complexity

🧠

Brute Force (Check All Overlaps)

💡 This approach exists to build intuition by directly checking overlaps between every pair of jobs, showing why naive methods are inefficient.

Intuition

For each job, check all other jobs to see if they overlap and sum their loads to find the max load at that job's time.

Algorithm

1. Initialize max_load to 0
2. For each job i, initialize current_load to job i's load
3. For each other job j, if job j overlaps with job i, add job j's load to current_load
4. Update max_load if current_load is greater

💡 The nested loops make it clear how overlaps contribute to load, but the double iteration is costly.

</>

Code

def find_max_cpu_load(jobs):
    max_load = 0
    n = len(jobs)
    for i in range(n):
        current_load = jobs[i][2]
        for j in range(n):
            if i != j and jobs[j][0] < jobs[i][1] and jobs[j][1] > jobs[i][0]:
                current_load += jobs[j][2]
        max_load = max(max_load, current_load)
    return max_load

# Driver code
if __name__ == '__main__':
    jobs = [[1,4,3], [2,5,4], [7,9,6]]
    print(find_max_cpu_load(jobs))  # Output: 7

Line Notes

max_load = 0Initialize max_load to track the highest CPU load found

for i in range(n):Outer loop picks each job as the reference interval

current_load = jobs[i][2]Start current load with the load of the current job

if i != j and jobs[j][0] < jobs[i][1] and jobs[j][1] > jobs[i][0]:Check if job j overlaps with job i

current_load += jobs[j][2]Add overlapping job's load to current load

max_load = max(max_load, current_load)Update max_load if current load is higher

import java.util.*;

public class MaxCPULoad {
    public static int findMaxCPULoad(int[][] jobs) {
        int maxLoad = 0;
        int n = jobs.length;
        for (int i = 0; i < n; i++) {
            int currentLoad = jobs[i][2];
            for (int j = 0; j < n; j++) {
                if (i != j && jobs[j][0] < jobs[i][1] && jobs[j][1] > jobs[i][0]) {
                    currentLoad += jobs[j][2];
                }
            }
            maxLoad = Math.max(maxLoad, currentLoad);
        }
        return maxLoad;
    }

    public static void main(String[] args) {
        int[][] jobs = {{1,4,3}, {2,5,4}, {7,9,6}};
        System.out.println(findMaxCPULoad(jobs)); // Output: 7
    }
}

Line Notes

int maxLoad = 0;Initialize maxLoad to keep track of maximum CPU load

for (int i = 0; i < n; i++) {Outer loop selects each job as reference

int currentLoad = jobs[i][2];Start current load with the load of job i

if (i != j && jobs[j][0] < jobs[i][1] && jobs[j][1] > jobs[i][0]) {Check if job j overlaps with job i

currentLoad += jobs[j][2];Add overlapping job's load to current load

maxLoad = Math.max(maxLoad, currentLoad);Update maxLoad if currentLoad is higher

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMaxCPULoad(vector<vector<int>>& jobs) {
    int maxLoad = 0;
    int n = jobs.size();
    for (int i = 0; i < n; i++) {
        int currentLoad = jobs[i][2];
        for (int j = 0; j < n; j++) {
            if (i != j && jobs[j][0] < jobs[i][1] && jobs[j][1] > jobs[i][0]) {
                currentLoad += jobs[j][2];
            }
        }
        maxLoad = max(maxLoad, currentLoad);
    }
    return maxLoad;
}

int main() {
    vector<vector<int>> jobs = {{1,4,3}, {2,5,4}, {7,9,6}};
    cout << findMaxCPULoad(jobs) << endl; // Output: 7
    return 0;
}

Line Notes

int maxLoad = 0;Initialize maxLoad to track maximum CPU load

for (int i = 0; i < n; i++) {Outer loop picks each job as reference

int currentLoad = jobs[i][2];Start current load with current job's load

if (i != j && jobs[j][0] < jobs[i][1] && jobs[j][1] > jobs[i][0]) {Check if job j overlaps with job i

currentLoad += jobs[j][2];Add overlapping job's load

maxLoad = max(maxLoad, currentLoad);Update maxLoad if currentLoad is greater

function findMaxCPULoad(jobs) {
    let maxLoad = 0;
    const n = jobs.length;
    for (let i = 0; i < n; i++) {
        let currentLoad = jobs[i][2];
        for (let j = 0; j < n; j++) {
            if (i !== j && jobs[j][0] < jobs[i][1] && jobs[j][1] > jobs[i][0]) {
                currentLoad += jobs[j][2];
            }
        }
        maxLoad = Math.max(maxLoad, currentLoad);
    }
    return maxLoad;
}

// Driver code
const jobs = [[1,4,3], [2,5,4], [7,9,6]];
console.log(findMaxCPULoad(jobs)); // Output: 7

Line Notes

let maxLoad = 0;Initialize maxLoad to track the highest CPU load found

for (let i = 0; i < n; i++) {Outer loop selects each job as reference

let currentLoad = jobs[i][2];Start current load with current job's load

if (i !== j && jobs[j][0] < jobs[i][1] && jobs[j][1] > jobs[i][0]) {Check if job j overlaps with job i

currentLoad += jobs[j][2];Add overlapping job's load

maxLoad = Math.max(maxLoad, currentLoad);Update maxLoad if currentLoad is greater

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each iterate over n jobs, resulting in O(n^2) time. No extra space besides variables.

💡 For n=1000, this means about 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE for large inputs; useful only to introduce problem

This approach is too slow for big inputs but helps understand the problem and overlaps.

🧠

Sorting + Min Heap to Track Overlaps

💡 This approach improves efficiency by sorting jobs and using a min heap to track currently running jobs, avoiding checking all pairs.

Intuition

Sort jobs by start time. Use a min heap to keep track of jobs that are currently running (by their end time). Remove jobs that ended before current job starts. Sum loads of jobs in heap to find max load.

Algorithm

1. Sort jobs by start time
2. Initialize a min heap to store jobs by end time
3. Initialize current_load and max_load to 0
4. For each job in sorted order:
5. Remove all jobs from heap that ended before current job starts, subtract their loads
6. Add current job to heap and add its load to current_load
7. Update max_load if current_load is greater

💡 The heap helps efficiently remove jobs that no longer overlap, so we only sum loads of overlapping jobs.

</>

Code

import heapq

def find_max_cpu_load(jobs):
    jobs.sort(key=lambda x: x[0])
    min_heap = []  # stores (end_time, load)
    current_load = 0
    max_load = 0

    for job in jobs:
        start, end, load = job
        while min_heap and min_heap[0][0] <= start:
            ended_job = heapq.heappop(min_heap)
            current_load -= ended_job[1]
        heapq.heappush(min_heap, (end, load))
        current_load += load
        max_load = max(max_load, current_load)

    return max_load

# Driver code
if __name__ == '__main__':
    jobs = [[1,4,3], [2,5,4], [7,9,6]]
    print(find_max_cpu_load(jobs))  # Output: 7

Line Notes

jobs.sort(key=lambda x: x[0])Sort jobs by start time to process in chronological order

min_heap = []Min heap to track jobs by their end time for efficient removal

while min_heap and min_heap[0][0] <= start:Remove all jobs that ended before current job starts

ended_job = heapq.heappop(min_heap)Pop the earliest ending job from heap

current_load -= ended_job[1]Subtract load of ended job from current load

heapq.heappush(min_heap, (end, load))Add current job to heap

current_load += loadAdd current job's load to current load

max_load = max(max_load, current_load)Update max load if current load is higher

import java.util.*;

public class MaxCPULoad {
    public static int findMaxCPULoad(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int currentLoad = 0, maxLoad = 0;

        for (int[] job : jobs) {
            int start = job[0], end = job[1], load = job[2];
            while (!minHeap.isEmpty() && minHeap.peek()[0] <= start) {
                currentLoad -= minHeap.poll()[1];
            }
            minHeap.offer(new int[]{end, load});
            currentLoad += load;
            maxLoad = Math.max(maxLoad, currentLoad);
        }
        return maxLoad;
    }

    public static void main(String[] args) {
        int[][] jobs = {{1,4,3}, {2,5,4}, {7,9,6}};
        System.out.println(findMaxCPULoad(jobs)); // Output: 7
    }
}

Line Notes

Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));Sort jobs by start time

PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));Min heap to track jobs by end time

while (!minHeap.isEmpty() && minHeap.peek()[0] <= start) {Remove jobs that ended before current job starts

currentLoad -= minHeap.poll()[1];Subtract load of ended job

minHeap.offer(new int[]{end, load});Add current job to heap

currentLoad += load;Add current job's load

maxLoad = Math.max(maxLoad, currentLoad);Update max load if current load is higher

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int findMaxCPULoad(vector<vector<int>>& jobs) {
    sort(jobs.begin(), jobs.end(), [](auto& a, auto& b) { return a[0] < b[0]; });
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap; // (end, load)
    int currentLoad = 0, maxLoad = 0;

    for (auto& job : jobs) {
        int start = job[0], end = job[1], load = job[2];
        while (!minHeap.empty() && minHeap.top().first <= start) {
            currentLoad -= minHeap.top().second;
            minHeap.pop();
        }
        minHeap.push({end, load});
        currentLoad += load;
        maxLoad = max(maxLoad, currentLoad);
    }
    return maxLoad;
}

int main() {
    vector<vector<int>> jobs = {{1,4,3}, {2,5,4}, {7,9,6}};
    cout << findMaxCPULoad(jobs) << endl; // Output: 7
    return 0;
}

Line Notes

sort(jobs.begin(), jobs.end(), [](auto& a, auto& b) { return a[0] < b[0]; });Sort jobs by start time

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;Min heap to track jobs by end time

while (!minHeap.empty() && minHeap.top().first <= start) {Remove jobs that ended before current job starts

currentLoad -= minHeap.top().second;Subtract load of ended job

minHeap.pop();Remove ended job from heap

minHeap.push({end, load});Add current job to heap

currentLoad += load;Add current job's load

maxLoad = max(maxLoad, currentLoad);Update max load if current load is higher

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0 && this.heap[this.parent(i)][0] > this.heap[i][0]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapify(0);
        return root;
    }
    heapify(i) {
        let smallest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
        if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
        if (smallest !== i) {
            this.swap(i, smallest);
            this.heapify(smallest);
        }
    }
    peek() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
}

function findMaxCPULoad(jobs) {
    jobs.sort((a, b) => a[0] - b[0]);
    const minHeap = new MinHeap();
    let currentLoad = 0, maxLoad = 0;

    for (const [start, end, load] of jobs) {
        while (minHeap.size() > 0 && minHeap.peek()[0] <= start) {
            currentLoad -= minHeap.pop()[1];
        }
        minHeap.push([end, load]);
        currentLoad += load;
        maxLoad = Math.max(maxLoad, currentLoad);
    }
    return maxLoad;
}

// Driver code
const jobs = [[1,4,3], [2,5,4], [7,9,6]];
console.log(findMaxCPULoad(jobs)); // Output: 7

Line Notes

jobs.sort((a, b) => a[0] - b[0]);Sort jobs by start time

const minHeap = new MinHeap();Initialize min heap to track jobs by end time

while (minHeap.size() > 0 && minHeap.peek()[0] <= start) {Remove jobs that ended before current job starts

currentLoad -= minHeap.pop()[1];Subtract load of ended job

minHeap.push([end, load]);Add current job to heap

currentLoad += load;Add current job's load

maxLoad = Math.max(maxLoad, currentLoad);Update max load if current load is higher

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n). Each job is pushed and popped at most once from the heap, each operation O(log n).

💡 For n=100000, this approach is efficient enough to run quickly.

Interview Verdict: Accepted and efficient for large inputs

This approach balances clarity and efficiency, suitable for interviews.

🧠

Sweep Line Algorithm with Events

💡 This approach uses a sweep line technique by converting intervals into start and end events, then processing them in order to track load changes efficiently.

Intuition

Create events for all job start and end times. Sort events by time. Sweep through events, adding load on start and subtracting on end, tracking max load.

Algorithm

1. Create a list of events: (time, load_change), where load_change is +load for start and -load for end
2. Sort events by time
3. Initialize current_load and max_load to 0
4. Iterate over events in order:
5. Add load_change to current_load
6. Update max_load if current_load is greater

💡 This approach reduces the problem to processing a sorted list of load changes, avoiding complex data structures.

</>

Code

def find_max_cpu_load(jobs):
    events = []
    for start, end, load in jobs:
        events.append((start, load))
        events.append((end, -load))
    events.sort(key=lambda x: x[0])

    current_load = 0
    max_load = 0
    for _, load_change in events:
        current_load += load_change
        max_load = max(max_load, current_load)
    return max_load

# Driver code
if __name__ == '__main__':
    jobs = [[1,4,3], [2,5,4], [7,9,6]]
    print(find_max_cpu_load(jobs))  # Output: 7

Line Notes

events = []Initialize list to hold start and end events

events.append((start, load))Add start event with positive load

events.append((end, -load))Add end event with negative load

events.sort(key=lambda x: x[0])Sort events by time to process chronologically

current_load += load_changeUpdate current load by adding or subtracting load

max_load = max(max_load, current_load)Track maximum load seen so far

import java.util.*;

public class MaxCPULoad {
    public static int findMaxCPULoad(int[][] jobs) {
        List<int[]> events = new ArrayList<>();
        for (int[] job : jobs) {
            events.add(new int[]{job[0], job[2]}); // start event
            events.add(new int[]{job[1], -job[2]}); // end event
        }
        events.sort(Comparator.comparingInt(a -> a[0]));

        int currentLoad = 0, maxLoad = 0;
        for (int[] event : events) {
            currentLoad += event[1];
            maxLoad = Math.max(maxLoad, currentLoad);
        }
        return maxLoad;
    }

    public static void main(String[] args) {
        int[][] jobs = {{1,4,3}, {2,5,4}, {7,9,6}};
        System.out.println(findMaxCPULoad(jobs)); // Output: 7
    }
}

Line Notes

List<int[]> events = new ArrayList<>();Create list to hold start and end events

events.add(new int[]{job[0], job[2]});Add start event with positive load

events.add(new int[]{job[1], -job[2]});Add end event with negative load

events.sort(Comparator.comparingInt(a -> a[0]));Sort events by time

currentLoad += event[1];Update current load by adding or subtracting load

maxLoad = Math.max(maxLoad, currentLoad);Track maximum load

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMaxCPULoad(vector<vector<int>>& jobs) {
    vector<pair<int,int>> events;
    for (auto& job : jobs) {
        events.push_back({job[0], job[2]}); // start event
        events.push_back({job[1], -job[2]}); // end event
    }
    sort(events.begin(), events.end());

    int currentLoad = 0, maxLoad = 0;
    for (auto& event : events) {
        currentLoad += event.second;
        maxLoad = max(maxLoad, currentLoad);
    }
    return maxLoad;
}

int main() {
    vector<vector<int>> jobs = {{1,4,3}, {2,5,4}, {7,9,6}};
    cout << findMaxCPULoad(jobs) << endl; // Output: 7
    return 0;
}

Line Notes

vector<pair<int,int>> events;Create vector to hold start and end events

events.push_back({job[0], job[2]});Add start event with positive load

events.push_back({job[1], -job[2]});Add end event with negative load

sort(events.begin(), events.end());Sort events by time

currentLoad += event.second;Update current load by adding or subtracting load

maxLoad = max(maxLoad, currentLoad);Track maximum load

function findMaxCPULoad(jobs) {
    const events = [];
    for (const [start, end, load] of jobs) {
        events.push([start, load]); // start event
        events.push([end, -load]); // end event
    }
    events.sort((a, b) => a[0] - b[0]);

    let currentLoad = 0, maxLoad = 0;
    for (const [, loadChange] of events) {
        currentLoad += loadChange;
        maxLoad = Math.max(maxLoad, currentLoad);
    }
    return maxLoad;
}

// Driver code
const jobs = [[1,4,3], [2,5,4], [7,9,6]];
console.log(findMaxCPULoad(jobs)); // Output: 7

Line Notes

const events = [];Initialize array to hold start and end events

events.push([start, load]);Add start event with positive load

events.push([end, -load]);Add end event with negative load

events.sort((a, b) => a[0] - b[0]);Sort events by time

currentLoad += loadChange;Update current load by adding or subtracting load

maxLoad = Math.max(maxLoad, currentLoad);Track maximum load

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Creating and sorting 2n events takes O(n log n). Iterating over events is O(n).

💡 This approach is efficient and often simpler to implement than heap-based solutions.

Interview Verdict: Accepted and efficient

Sweep line is a clean and optimal approach, great for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the sorting + min heap or sweep line approach for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Min Heap	O(n log n)	O(n)	No	N/A	Code this for efficient and clear solution
3. Sweep Line Algorithm	O(n log n)	O(n)	No	N/A	Also good to code; simpler data structure

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of overlaps.Step 3: Introduce sorting and min heap to optimize overlap tracking.Step 4: Present the sweep line approach as an elegant alternative.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to identify interval overlap patterns, use appropriate data structures (heap or sweep line), and optimize from naive to efficient solutions.

Common Follow-ups

• What if jobs can have zero length? → Handle events carefully, possibly process start before end events.
• How to find the time interval(s) when max load occurs? → Track intervals while sweeping.

💡 Follow-ups test your ability to adapt the solution to edge cases and extend functionality.

🔍

Pattern Recognition

When to Use

1) Problem involves intervals with start and end times, 2) Need to find max overlap or resource usage, 3) Jobs/tasks have weights or loads, 4) Asked for peak or max concurrent usage.

Signature Phrases

maximum CPU loadoverlapping jobspeak concurrent load

NOT This Pattern When

Problems that only ask for sorting or merging intervals without weighted sums are different.

Similar Problems

Meeting Rooms II - find minimum rooms needed for overlapping meetingsCar Pooling - track passenger load over time intervalsEmployee Free Time - find gaps between overlapping intervals

Practice

1. You are given a list of points on a 2D plane and need to find the k points closest to the origin (0,0). Which algorithmic approach best balances average time complexity and space usage for this problem?

easy

A. Use a Quickselect algorithm to partition points around a pivot distance until the k closest are identified.

B. Use a greedy algorithm that iteratively picks the closest point until k points are selected.

C. Use a dynamic programming approach to build up solutions for subsets of points.

D. Sort all points by their distance to the origin and return the first k points.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the k closest points efficiently, ideally better than sorting all points which is O(n log n).

2. Step 2: Identify algorithm characteristics

   Quickselect partitions points around a pivot and reduces the problem size each iteration, achieving average O(n) time and O(1) extra space, making it optimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Quickselect is known for average linear time selection problems [OK]

Hint: Quickselect offers average O(n) vs sorting's O(n log n) [OK]

Common Mistakes:

• Confusing sorting with selection algorithms
• Assuming greedy always works for closest points

2. Given the following Python code implementing the optimal approach for Kth Largest in a Stream, what is the output of the last print statement?

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]

kthLargest = KthLargest(3, [4, 5, 8, 2])
print(kthLargest.add(3))
print(kthLargest.add(5))
print(kthLargest.add(10))
print(kthLargest.add(9))
print(kthLargest.add(4))

easy

A. 8

B. 5

C. 4

D. 9

Solution

1. Step 1: Trace heap initialization

   Initial nums = [4,5,8,2], heapified and trimmed to size k=3: heap becomes [4,5,8] after popping 2.

2. Step 2: Trace add calls and heap updates

   add(3): 3 < 4 (heap[0]), no replace, return 4 add(5): 5 > 4, replace 4 with 5, heap now [5,5,8], return 5 add(10): 10 > 5, replace 5 with 10, heap now [5,10,8], return 5 add(9): 9 > 5, replace 5 with 9, heap now [8,10,9], return 8 add(4): 4 < 8, no replace, return 8

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last add returns 8 as kth largest element [OK]

Hint: Heap root always holds kth largest element [OK]

Common Mistakes:

• Off-by-one errors in heap size
• Replacing when val <= heap[0]
• Misunderstanding heap root meaning

3. Consider the following Python code implementing the optimal approach for top K frequent words. Given the input words = ["apple", "banana", "apple", "orange", "banana", "banana"] and k = 2, what is the returned list?

easy

A. ["banana", "apple"]

B. ["banana", "orange"]

C. ["apple", "banana"]

D. ["apple", "orange"]

Solution

1. Step 1: Count frequencies

   apple: 2, banana: 3, orange: 1; max_freq = 3

2. Step 2: Fill buckets and sort within buckets

   buckets[3] = ["banana"], buckets[2] = ["apple"], buckets[1] = ["orange"]; iterate from freq=3 down

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Top 2 frequent words are banana (3), apple (2) [OK]

Hint: Trace frequency buckets from highest to lowest [OK]

Common Mistakes:

• Confusing lex order with frequency order
• Off-by-one in bucket indices
• Returning words in ascending frequency order

4. The following code attempts to find the k-th smallest pair distance using a heap-based approach. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 8: Loop runs k-1 times instead of k times.

B. Line 5: Incorrect heap initialization with pairs from adjacent elements.

C. Line 2: Missing sorting of the input array before processing pairs.

D. Line 10: Incorrect condition for pushing next pair into the heap.

Solution

1. Step 1: Check for sorting

   The input array is not sorted before pushing pairs, so pair distances are incorrect or unordered.

2. Step 2: Verify heap initialization and loop

   Heap initialization and loop logic are correct assuming sorted input; condition and loop count are proper.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting is essential for correct pair distance ordering [OK]

Hint: Always sort before generating pairs for distance calculations [OK]

Common Mistakes:

• Forgetting to sort input array
• Off-by-one in loop count
• Wrong heap push condition

5. Suppose the problem is modified so that you can hire any number of workers (not exactly K), but you want to minimize the cost to hire at least K workers under the same fairness constraints. Which modification to the optimal algorithm is correct?

hard

A. Run the original algorithm and return the minimum cost found when the qualities list size is exactly K only.

B. Sort by quality instead of ratio and pick the first K workers to minimize cost.

C. Run the original algorithm but update the minimum cost whenever the qualities list size is at least K, not just equal to K.

D. Use a brute force approach checking all subsets of size at least K to find the minimum cost.

Solution

1. Step 1: Understand the relaxed constraint

   We want to hire at least K workers, so any group with size ≥ K is valid.

2. Step 2: Modify cost update condition

   Instead of updating min_cost only when qualities size == K, update it whenever size ≥ K to consider larger groups.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Allows considering all valid groups with size ≥ K, ensuring minimal cost [OK]

Hint: Update min cost for all sizes ≥ K, not just == K [OK]

Common Mistakes:

• Ignoring groups larger than K
• Using brute force unnecessarily
• Sorting by quality instead of ratio