Heaps and top-K interview questions

The heap never holds more than k entries, one front per list, so each push or pop walks at most about log2 k levels, not log2 N. Each of the N values is pushed once and popped once, which gives O(N log k). Sorting the concatenation is O(N log N), and it needs every value in memory before it returns the first. The gap matters when k is much smaller than N, and above all when the lists are files or streams: merging 1,000 lists of a million values walks about 10 levels per value instead of 20, and holds 1,000 values at a time instead of a million.

Along row i the first term a[i] stays fixed while b[j] grows with j, because b is sorted, so the sums rise from left to right. Down column j, b[j] stays fixed while a[i] grows, so the sums rise from top to bottom. The smallest sum of all is therefore in the corner, a[0] + b[0]. More generally, a pair costs at least as much as the pair to its left and the pair above it, so it can be the next smallest only once those two have been taken. The candidates for the next smallest sum always form a thin edge around the pairs already taken, which is why a heap that holds only that edge is enough, instead of all n times m sums.

Counts alone do not decide the order, because two words can occur equally often, and the problem says which of them ranks higher: the one that comes first alphabetically. So the order compares counts first, the higher count ranking higher, and compares the words only when the counts are equal. With the count as the only key, the order of equal counts is left to the method: a heap returns them in no promised order, and a stable sort returns them in the order they reached it, which depends on the log. The answer would then change when the same searches arrive in another order. The second key has to be part of every comparison the method makes, not a sort applied at the end, because the method may already have dropped the word that should have won the tie.

A heap gives fast access to one value only, its top: the smallest of a min-heap or the largest of a max-heap. The median is neither; it sits in the middle, where the sorted values split into halves. So split them: the lower half in a max-heap, whose top is its largest value, and the upper half in a min-heap, whose top is its smallest. Those two tops are exactly the values next to the split, so the median is the lower top when the count is odd and the mean of both tops when it is even. A new value joins one half and at most one top moves across to keep the halves even, so each value costs O(log n). One heap would need n/2 pops to reach the middle every time.

The square root keeps order: for distances that are not negative, one is smaller than another exactly when its square is, so x² + y² ranks the points as their distances do. Skipping the root saves work, and with whole-number coordinates the squared distance is a whole number, compared exactly, while a square root is rounded and can make two different distances look equal. What remains to watch is size. Squares grow fast: with coordinates up to 10⁹, x² + y² reaches 2 × 10¹⁸, so it needs a 64-bit integer type, and in languages with fixed-size integers the coordinates must be widened before they are multiplied, not after.

A room becomes usable again when its current meeting ends, so the only fact that matters about a busy room is its end time. When a new meeting starts, the question is whether any room is free by then, and the room that frees first answers it: if even the earliest end time is later than the start, every room is busy. So a min-heap of end times keeps exactly the needed fact on top. If the earliest end is at most the start, for half-open meetings, that room is reused and its end time is replaced; otherwise a room opens. Meetings must be visited in start order for this to work, and each one costs O(log n).

Because a heap can find only its top. An old entry may sit anywhere in the array, so removing it means searching the whole heap, O(n), and then repairing the heap around the hole. Lazy deletion avoids the search: the update pushes a new entry and records which entry is current, and the old one stays where it is. It can only change an answer when it reaches the top, and at that moment it is easy to recognise and pop. Every entry is pushed once and popped at most once, so the work stays O(log n) per operation, amortised, even when one query happens to pop several out-of-date entries in a row.