What must be easy to discard?

Retain the best three scores. Current scores are [5,2,8]; next score is 6.

Decision: Which retained value must be exposed, and why does a maximum at the root not answer the replacement question?

1 / 10

Kth Largest Element in an Array — predict before coding

Keep the best k values seen so far and expose the weakest retained one. A min-heap makes that threshold available at the root; duplicates occupy separate ranks.

Decision: A stream summary keeps only the largest two occurrences. Prefixes [1,10,9] and [8,10,9] produce the same summary. If a later query asks for the third-largest value of that past prefix, can the stored state answer it?

Presenter notes

Model answer: No. Both summaries retain {9,10}, but the requested third values are 1 and 8. The discarded values became relevant when k changed. Fixed-k retention is sufficient for its original query, not for arbitrary later ranks; supporting those requires retaining additional information or a different data structure.

Correctness argument: After each input value, the heap contains the largest min(k,processed) values as a multiset. Inserting the next value temporarily adds one candidate. If the size exceeds k, removing the smallest discards a value no better than any retained one; it can never displace a retained value in the top-k multiset. This preserves the invariant by induction. At the end, the heap contains k largest entries, and its smallest is exactly the kth largest. Sorting the entire input is unnecessary, and equal values are retained according to multiplicity rather than deduplicated.

Debugging prompt: Check the heap direction: retaining the largest k requires removing the smallest candidate. Test k=1, k=n, duplicates, and negative values. The input is not sorted or mutated by the reference.

2 / 10

Top K Frequent Elements — predict before coding

First count occurrences, then rank distinct values by their counts. The heap entries are values with frequencies, not individual occurrences.

Decision: A streaming shortcut evicts low-frequency values before the input ends and then ignores their future occurrences. With k=1, it sees [2,1,1], keeps 2 after the first tie, and permanently discards 1. Why is final frequency counting different?

Presenter notes

Model answer: The last 1 raises its final frequency to two, above 2’s frequency one. Early eviction did not justify forgetting future updates. The reference first builds complete frequencies, then ranks fixed candidates. A live frequency-ranking structure would need to track increments and repair candidate priorities; it cannot reuse the fixed-count proof unchanged.

Correctness argument: Once the frequency map is complete, process each distinct value once. Maintain a min-heap of the k strongest frequency entries processed so far; inserting a new entry and removing the weakest when oversized preserves this property. At completion no excluded value has frequency greater than a retained minimum, so the result is a valid top-k selection. Equal frequencies at the cutoff can admit multiple correct subsets, and map iteration can vary their choice. Every returned value must be distinct; sorting output alone does not make a test robust to a cutoff tie.

Debugging prompt: Check length k, no duplicates, membership in the input, and that no excluded frequency exceeds any selected one. Do not assert deterministic ordering from Go map traversal.

3 / 10

Find K Pairs with Smallest Sums — predict before coding

Each first-array index defines a sorted row of pair sums as the second index increases. The heap merges these sorted rows by keeping only the next unreported pair from each active row.

Decision: A different pair-grid search expands both (i+1,j) and (i,j+1) after every pop. Starting at (0,0), show two ways to schedule (1,1). Why does the reference’s seeded-row successor rule need no visited set?

Presenter notes

Model answer: Paths (0,0)→(1,0)→(1,1) and (0,0)→(0,1)→(1,1) both schedule that same index pair. A two-direction search must deduplicate indices. The reference seeds each active row at column zero and advances only to its next column, so every pair has one unique predecessor within its row. Equal displayed value pairs from different indices remain distinct outputs.

Correctness argument: For each seeded row i, its current head is the least unreported pair in that row. Popping the smallest head is globally safe because all later entries in every active row are at least their heads. After outputting (i,j), insert (i,j+1) to restore that invariant. Seeding only min(k,len(nums1)) rows is sufficient: every omitted row’s first sum is at least the first sums of k earlier rows, so it cannot be strictly required before k outputs; ties allow alternative valid pairs. Index pairs, not value pairs, are the distinct candidates, so repeated input values legitimately produce duplicate value rows. Wide sum comparison prevents overflow from reversing heap order.

Debugging prompt: Check nondecreasing mathematical sums, available pair multiplicities, and the cutoff sum. Do not require one ordering among equal-sum pairs. The corrected reference compares full signed sums even when a+b cannot fit in int.

4 / 10

Pair sums: a frontier trace

A=[1,4,7,10], B=[2,3], k=3.

Pop	Reveal	Next heap sums
(0,0), sum 3	(0,1), sum 4	4,6,9
(0,1), sum 4	row 0 exhausted	6,9
(1,0), sum 6	(1,1), sum 7	7,9

Each index pair has one predecessor in its row.

5 / 10

Pair sums: why omit rows after k?

For i>=k, every A[i]+B[j] is at least A[k-1]+B[0].

The k seeded pairs (0,0) through (k-1,0) are no larger.

Decision: A=[1,1,1,1], B=[2], k=3. Must row 3 be visited because it ties the cutoff?

6 / 10

Find Median from Data Stream — predict before coding

Split the multiset into a lower half and an upper half. A max-heap exposes the lower half’s largest value; a min-heap exposes the upper half’s smallest value.

Decision: Two heaps have low values {1,100} and high values {2,3}. Each heap individually obeys its own ordering and the sizes match. What wrong median do their roots imply, and which independent invariant is missing?

Presenter notes

Model answer: The roots give (100+2)/2=51, but sorting all four values gives [1,2,3,100] and median 2.5. Size balance is insufficient: every low value must be no larger than every high value. Moving a boundary element while preserving that partition is essential; two valid heap structures do not automatically form a valid rank split.

Correctness argument: Maintain every low value <= every high value, with low having either the same number of entries as high or exactly one more. Insert relative to low’s root, then move one boundary root if sizes violate this rule. Because the moved root is the extreme at the boundary, transferring it preserves ordering while restoring sizes. With odd total size, low’s root is the middle-ranked value. With even size, low’s maximum and high’s minimum are the two middle values, whose exact arithmetic mean is returned as float64. Independent instances own independent heaps, and querying the median does not consume either root.

Debugging prompt: Test the median after every insertion, not just at the end. Include duplicates, decreasing streams, two independent instances, and signed extrema. FindMedian requires at least one inserted value; querying an empty structure is not a supported operation.

7 / 10

IPO — predict before coding

Feasibility depends on current capital, while desirability depends on profit. Sort once by capital requirement, then use a max-heap to choose the best profit among projects that are currently affordable.

Decision: Change the economic model: starting capital is 4, each project pays its requirement as a fee and then receives a gross reward. For one allowed project, choices (fee 4,reward 5) and (fee 1,reward 4) are affordable. Does choosing the larger reward remain optimal?

Presenter notes

Model answer: No. The first leaves 4-4+5=5, while the second leaves 4-1+4=7. Under that changed model, gross reward is not net profit and fees affect resources. The pack’s IPO contract uses requirements only as thresholds and adds the declared profit; its greedy proof cannot be transferred by merely renaming the inputs.

Correctness argument: Before each selection, the heap contains all unchosen projects whose capital requirement is at most current capital. Selecting the largest positive profit maximizes capital after that round. Exchange it with the first choice of an optimal sequence: the replacement is affordable now and leaves at least as much capital, so it cannot make later affordable projects unavailable; if it appeared later, move the displaced project or omit a redundant choice under the at-most-k limit. Repeating this exchange proves greedy optimality. Because selected profits are positive, capital never decreases and the sorted eligibility pointer advances only forward. If no positive affordable profit remains, stopping is optimal: zero changes nothing and negative profit cannot unlock a higher requirement.

Debugging prompt: Do not subtract required capital; it is an eligibility threshold, not a cost consumed by the model. Stop when the best available profit is nonpositive. Verify equal-length profit/capital arrays and representable accumulated capital.

8 / 10

Design a counterexample, not a larger example

A top-frequency solver counts correctly but orders its bounded heap by numeric value.

It returns a valid set for [4,4,9,9,9,2,2], k=2. Does that validate its priority? Construct a failing input.

9 / 10

Reconstruct and transfer

For each heap, specify admission, priority, eviction, size bound, and tie policy.

Check numerical comparisons without overflowing sums.

10 / 10