Dernière activité 5 days ago

Interview prep notes

Révision 0bf7b5068a408ef8f73c2e16f976e6cc057aff67

topk.md Brut

Top-K Problems with Heaps: When and How to Use Them

"Find the k most frequent elements", "k closest points to the origin", "kth largest element in a stream": whenever a question says top k, consider a heap.

Rule of thumb

To keep the k largest items, use a min-heap of size k. The smallest of your current top k sits at the root, so each new item is compared with it in O(log k).

import heapq
from collections import Counter

def top_k_frequent(nums, k):          # LeetCode 347
    heap = []
    for val, cnt in Counter(nums).items():
        heapq.heappush(heap, (cnt, val))
        if len(heap) > k:
            heapq.heappop(heap)
    return [v for _, v in heap]

Total time is O(n log k), better than sorting (O(n log n)) when k is small.

Alternatives to mention

  • Bucket sort by frequency: O(n) for Top K Frequent because frequencies are bounded by n.
  • Quickselect: average O(n) for kth largest, but O(n²) worst case; say so.
  • heapq.nlargest(k, iterable) is fine in Python, but be ready to implement it yourself.

Streaming version (LeetCode 703)

Keep the size-k min-heap as state; each add pushes, pops if the size exceeds k, and returns heap[0].

Pitfalls

  • Python's heapq is a min-heap only; negate values for a max-heap.
  • Tuples compare element by element, so ties can fall through to comparing objects that don't support it. Add an index as a tie-breaker.

Disclosure: I help build an AI interview copilot at Linkjob. This guide is general study material.