Последняя активность 5 days ago

Interview prep notes

linkjobai ревизий этого фрагмента 5 days ago. К ревизии

1 file changed, 40 insertions

topk.md(файл создан)

@@ -0,0 +1,40 @@
1 + # Top-K Problems with Heaps: When and How to Use Them
2 +
3 + "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.
4 +
5 + ## Rule of thumb
6 +
7 + 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).
8 +
9 + ```python
10 + import heapq
11 + from collections import Counter
12 +
13 + def top_k_frequent(nums, k): # LeetCode 347
14 + heap = []
15 + for val, cnt in Counter(nums).items():
16 + heapq.heappush(heap, (cnt, val))
17 + if len(heap) > k:
18 + heapq.heappop(heap)
19 + return [v for _, v in heap]
20 + ```
21 +
22 + Total time is O(n log k), better than sorting (O(n log n)) when k is small.
23 +
24 + ## Alternatives to mention
25 +
26 + - **Bucket sort by frequency:** O(n) for Top K Frequent because frequencies are bounded by n.
27 + - **Quickselect:** average O(n) for kth largest, but O(n²) worst case; say so.
28 + - `heapq.nlargest(k, iterable)` is fine in Python, but be ready to implement it yourself.
29 +
30 + ## Streaming version (LeetCode 703)
31 +
32 + Keep the size-k min-heap as state; each `add` pushes, pops if the size exceeds k, and returns `heap[0]`.
33 +
34 + ## Pitfalls
35 +
36 + - Python's `heapq` is a min-heap only; negate values for a max-heap.
37 + - 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.
38 +
39 + ---
40 + *Disclosure: I help build [an AI interview copilot at Linkjob](https://www.linkjob.ai/). This guide is general study material.*
Новее Позже