Utoljára aktív 5 days ago

Interview prep notes

linkjobai gist felülvizsgálása 5 days ago. Revízióhoz ugrás

1 file changed, 53 insertions

topological-sort.md(fájl létrehozva)

@@ -0,0 +1,53 @@
1 + # Topological Sort in Coding Interviews: Kahn's Algorithm Explained
2 +
3 + Problems like **Course Schedule (LeetCode 207/210)**, **Alien Dictionary** and build-order questions are all the same idea: you have tasks with "must happen before" rules, and you need a valid order (or proof that none exists).
4 +
5 + ## The idea in one sentence
6 +
7 + Repeatedly take a node with **no remaining prerequisites** (in-degree 0), output it, and remove its outgoing edges.
8 +
9 + ## Python template (Kahn's algorithm)
10 +
11 + ```python
12 + from collections import deque, defaultdict
13 +
14 + def topo_order(n, edges): # edges: (before, after)
15 + graph = defaultdict(list)
16 + indeg = [0] * n
17 + for a, b in edges:
18 + graph[a].append(b)
19 + indeg[b] += 1
20 + q = deque(i for i in range(n) if indeg[i] == 0)
21 + order = []
22 + while q:
23 + node = q.popleft()
24 + order.append(node)
25 + for nxt in graph[node]:
26 + indeg[nxt] -= 1
27 + if indeg[nxt] == 0:
28 + q.append(nxt)
29 + return order if len(order) == n else [] # [] means a cycle
30 + ```
31 +
32 + Time O(V + E), space O(V + E).
33 +
34 + ## What to say out loud
35 +
36 + - "I'll model this as a directed graph where an edge means *must come before*."
37 + - "If I can't output every node, some nodes are stuck waiting on each other, so there is a cycle."
38 + - Mention the alternative: DFS with three colours (unvisited / visiting / done) detects cycles too, and the reverse post-order is a valid topological order.
39 +
40 + ## Common follow-ups
41 +
42 + 1. **Lexicographically smallest order?** Swap the deque for a min-heap.
43 + 2. **Minimum number of semesters?** Process the queue level by level and count levels (LeetCode 1136).
44 + 3. **Alien Dictionary**: build edges by comparing the first differing character of adjacent words, and watch for the invalid case where a longer word comes before its own prefix.
45 +
46 + ## Mistakes interviewers notice
47 +
48 + - Building the edge in the wrong direction (prerequisite → course, not the reverse).
49 + - Forgetting isolated nodes that have no edges at all.
50 + - Returning a partial order instead of reporting the cycle.
51 +
52 + ---
53 + *Disclosure: I'm part of the team behind [Linkjob AI](https://www.linkjob.ai/), an AI interview assistant. These notes are free to use for practice.*
Újabb Régebbi