Question 1

Kth largest of n values, k much smaller than n. With heapq, which is O(n log k)?

Accepted Answer

Keep a min heap of size k, pop when size exceeds k, answer is heap[0] A size k min heap keeps the k largest and its root is the kth largest. Pushing all n values one by one is O(n log n) before any pop. A size k max heap evicts the wrong items. Sorting is O(n log n).

Question 2

You already hold n task priorities in a list and need a heap before processing. What does heapq.heapify(tasks) cost, compared with pushing them one by one?

Accepted Answer

O(n) Bottom up heapify is linear because most nodes are near the leaves and sift down a short distance. O(n log n) is pushing n items one by one. O(log n) is one push. O(n^2) is insertion into a sorted list.

Question 3

heapq.heappush(h, (dist, node)) where node is a custom object without ordering. When does it raise TypeError?

Accepted Answer

When two entries have equal dist, Python compares the node objects Tuples compare element by element, so equal priorities fall through to the payload. Add a counter as a tie breaker: (dist, count, node). Tuples are pushable. heapq has no key argument and compares whole items. Float or int makes no difference.

Question 4

On Python 3.13, heapq offers only min heap functions publicly. How do you get max heap behaviour for integers?

Accepted Answer

Push -x and negate when popping Negation turns the min heap into a max heap. Private helpers are not a supported API and re-heapifying each push is O(n). Python 3.14 added public max heap functions, which is why the version is stated. h[-1] is not the max of a heap. Sorting once breaks on later pushes.

Question 5

heapq.nlargest(k, iterable) on n items. What is the complexity a candidate should quote?

Accepted Answer

O(n log k) nlargest keeps a heap of size k, so each of n items costs O(log k). O(n log n) is sorting. O(k log n) is heapify then k pops, which also needs O(n) to build. O(n k) is a linear scan per pick.

Question 6

K Closest Points to Origin, n up to 10^4. Which is correct and avoids sqrt?

Accepted Answer

Compare x*x + y*y, keeping a size k max heap via negated distances Squared distance preserves order, and a size k max heap evicts the farthest. A size k min heap evicts the closest, which is backwards, and sqrt is unnecessary. Manhattan distance ranks differently from Euclidean. Sorting by coordinates is unrelated to distance.

Question 7

Merge k sorted lists with N total nodes using a heap of list heads. Time?

Accepted Answer

O(N log k) The heap holds at most k items and each of N nodes is pushed and popped once. O(N log N) is collecting then sorting. O(N k) is scanning all heads each step. O(k log N) undercounts.

Question 8

Find Median from Data Stream with two heaps. Invariant?

Accepted Answer

Max heap of the lower half, min heap of the upper half, sizes differ by at most 1 The tops of the two halves give the median in O(1) and inserts are O(log n). Two min heaps cannot expose the lower half's max. A max heap of the upper half exposes the wrong end. insort is O(n) per insert due to shifting.

Question 9

Task Scheduler: each interval runs one task or idles, and the same task needs n intervals between runs. Tasks A x3, B x3, n = 2. Minimum intervals?

Accepted Answer

8 (max_count - 1) * (n + 1) + count_of_max = 2 * 3 + 2 = 8: A B idle A B idle A B. 6 ignores cooldown. 7 counts only one task at the end. 9 adds an extra idle.

Question 10

IPO: you start with capital w. Project i needs capital[i] to start and adds profits[i]. Pick at most k projects to maximize final capital. Which structure combination?

Accepted Answer

Projects sorted by capital needed, plus a max heap of profits for affordable ones Unlock affordable projects as capital grows and always take the best profit. A profit only heap includes unaffordable projects. Sorting by profit once ignores that capital grows. DP over capital up to 10^9 is infeasible.

Heap and top k coding interview questions

More coding topics

Practise these on your commute