Hardtopological-sort
Как работает топологическая сортировка?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Topological sort — linear ordering вершин DAG, где для каждого edge (u, v) u идёт раньше v. Применения: task scheduling, build systems, course prerequisites (LeetCode 207, 210).
# Kahn's algorithm (BFS): очередь с indegree 0
from collections import deque
def kahn(graph, indegree):
q = deque([v for v in graph if indegree[v] == 0])
result = []
while q:
u = q.popleft()
result.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
return result if len(result) == len(graph) else [] # [] = cycleАльтернатива — DFS post-order + reverse (с gray/black coloring для cycle detection). O(V+E) время. Cycle detection: если result короче V — есть cycle. Lexicographically smallest order — priority queue вместо queue.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.