DEPLOYED — AI Engineer & Forward Deployed Engineer Interview Prep

Two graph techniques come up constantly: topological sort for ordering dependencies, and union-find for grouping connected elements.

Topological sort

On a directed acyclic graph (DAG), a topological order lists nodes so every edge points forward — every prerequisite comes before what depends on it. Kahn's algorithm repeatedly removes nodes with in-degree 0. If you cannot remove all nodes, the graph has a cycle (an impossible dependency).

from collections import deque

def topo_order(n, edges):          # edges: prereq -> course
    indeg = [0] * n
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in adj[node]:
            indeg[nb] -= 1
            if indeg[nb] == 0:
                q.append(nb)
    return order if len(order) == n else []   # empty -> cycle

Union-find (disjoint set)

Union-find tracks a collection of disjoint groups with two near-constant operations: find (which group is x in?) and union (merge two groups). With path compression and union by rank each op is effectively O(1) (inverse-Ackermann). It answers connectivity and cycle-in-undirected-graph questions and drives Kruskal's MST.

parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path compression
        x = parent[x]
    return x
def union(a, b):
    parent[find(a)] = find(b)
# (union by size/rank omitted for brevity — needed for the
#  inverse-Ackermann bound alongside path compression)

Recognize themTopological sort is the tell for course schedule / build order / task dependencies. Union-find is the tell for number of connected components, redundant connection, accounts merge, and Kruskal's MST.

Topological sort & union-find

Topological sort

Union-find (disjoint set)

◆ Lock it in