← Interview Prep

Python Drills — Graphs & Routing

Live-coding drills a network engineer sees at the whiteboard: building graphs from LLDP, parsing config trees, longest-prefix match, config diffing, prefix aggregation, and Dijkstra. Each drill has the problem statement, an approach with complexity, and a reference solution.

1. Topology from LLDP + BFS shortest path

Problem. Target: 12 minutes. A live-coding classic.

build_topology(lines) -> dict[str, set[str]]

Each line is "leaf1 Ethernet1 spine1 Ethernet1" (local device, local port, neighbor, neighbor's port). The graph is undirected.
Lines that do not have exactly 4 fields are silently skipped.
Self-links (a device linked to itself) are skipped.

shortest_path(topo, src, dst) -> list[str] | None

BFS. If src == dst return [src]. Unknown node or no path returns None.
When several paths of equal length exist, pick the one where neighbors are visited in lexicographic order — this makes the output deterministic for tests.

Be ready for follow-ups: what if links carry a weight/cost (Dijkstra)? What if you need all equal-cost paths (ECMP)?

Approach

Build an adjacency map by inserting both directions for every valid line (setdefault keeps it terse). For the search, run a plain BFS from src, recording a prev back-pointer for each node the first time it is reached; because BFS explores by increasing hop count, the first time dst is dequeued/discovered gives a shortest path. Sorting each node's neighbors before iterating makes tie-breaking deterministic. Reconstruct the path by walking prev from dst back to src and reversing.

Complexity: building the graph is O(E). BFS is O(V + E) time, with the per-node sorted() adding an O(E log Δ) factor (Δ = max degree). O(V) space for the queue and back-pointers.

Solution (Python)

"""Drill 4 (solution): LLDP topology + BFS."""
from __future__ import annotations

from collections import deque


def build_topology(lines: list[str]) -> dict[str, set[str]]:
    topo: dict[str, set[str]] = {}
    for raw in lines:
        parts = raw.split()
        if len(parts) != 4:
            continue
        a, _, b, _ = parts
        if a == b:
            continue
        topo.setdefault(a, set()).add(b)
        topo.setdefault(b, set()).add(a)
    return topo


def shortest_path(topo: dict[str, set[str]], src: str, dst: str) -> list[str] | None:
    if src not in topo or dst not in topo:
        return None
    if src == dst:
        return [src]

    prev: dict[str, str] = {src: src}
    queue = deque([src])
    while queue:
        node = queue.popleft()
        for nb in sorted(topo.get(node, ())):
            if nb in prev:
                continue
            prev[nb] = node
            if nb == dst:
                path = [dst]
                while path[-1] != src:
                    path.append(prev[path[-1]])
                return list(reversed(path))
            queue.append(nb)
    return None

Pitfalls

Forgetting the undirected edge. Insert both a→b and b→a, or half the graph is unreachable.
Non-deterministic order. Sets have no stable iteration order; without sorted() the chosen shortest path varies run to run and tests flake.
Marking visited too late. Record prev (visited) when you enqueue a node, not when you dequeue it — otherwise the same node gets queued many times and can produce a non-shortest path.
Unknown-node check. Handle src/dst not in the graph before the src == dst shortcut so an isolated node still returns None (except the trivial same-node case).
Path direction. Reconstruction walks backward from dst; remember to reverse.

2. Indented config text ↔ tree

Problem. Target: 12 minutes.

parse_tree(config) -> a nested dict where a leaf is an empty dict.

  router bgp 65001
    router-id 10.0.0.1
    neighbor 10.0.0.2
      remote-as 65002

  -> {"router bgp 65001": {"router-id 10.0.0.1": {},
                           "neighbor 10.0.0.2": {"remote-as 65002": {}}}}

Key order is preserved (a regular dict already gives this).
Blank lines, "!", and lines starting with "#" are skipped.
Extra spaces inside a line are collapsed.

to_lines(tree, indent=2) -> list[str] — the inverse transform, such that parse_tree("\n".join(to_lines(t))) == t.

Algorithm hint: a stack of (indent_level, node). This is the exact trick asked in many variations over the years.

Approach

Maintain a stack seeded with a sentinel (-1, root). For each non-skipped line, compute its indentation as the count of leading spaces and normalize the text (" ".join(raw.split())). Pop the stack while the top's indent is >= the current indent — that leaves the correct parent on top. Attach a fresh empty dict under the parent and push (indent, node). The inverse to_lines is a pre-order DFS that emits indent * level spaces before each key.

Complexity: O(n) in the number of lines (each line is pushed and popped at most once); O(depth) stack space.

Solution (Python)

"""Drill 5 (solution): indented config <-> tree."""
from __future__ import annotations


def parse_tree(config: str) -> dict:
    root: dict = {}
    stack: list[tuple[int, dict]] = [(-1, root)]

    for raw in config.splitlines():
        if not raw.strip() or raw.strip() == "!" or raw.lstrip().startswith("#"):
            continue
        indent = len(raw) - len(raw.lstrip(" "))
        line = " ".join(raw.split())

        while stack and stack[-1][0] >= indent:
            stack.pop()
        parent = stack[-1][1]
        node: dict = {}
        parent[line] = node
        stack.append((indent, node))

    return root


def to_lines(tree: dict, indent: int = 2, _level: int = 0) -> list[str]:
    out: list[str] = []
    for key, child in tree.items():
        out.append(" " * (indent * _level) + key)
        out.extend(to_lines(child, indent, _level + 1))
    return out

Pitfalls

Measuring indent after stripping. Count leading spaces on the raw line; if you strip first you lose the depth signal.
Wrong pop condition. Use >=, not > — a sibling at the same indent must pop the previous sibling so the new node lands under the shared parent, not inside its sibling.
Sentinel level. Seed the stack with indent -1 so a top-level line (indent 0) never pops the root.
Round-trip fidelity. Because parse_tree collapses inner whitespace, to_lines must re-emit with a consistent indent step for the round-trip identity to hold.
Debug prints. Don't leave a print() inside parse_tree (as in the scratch version) — it corrupts output and slows the drill.

3. Longest Prefix Match (routing)

Problem. Target: 10 minutes. The ipaddress module is allowed.

lpm(table, ip) -> str | None

table is a list of (cidr, next_hop). Return the next_hop of the longest prefix that covers ip. No match returns None.
"0.0.0.0/0" is the default route (prefix length 0, the most general).

table = [("0.0.0.0/0", "gw0"),
         ("10.0.0.0/8", "gw1"),
         ("10.1.0.0/16", "gw2")]
lpm(table, "10.1.2.3") -> "gw2"   # /16 is longer than /8 and /0
lpm(table, "10.2.3.4") -> "gw1"   # only /8 matches (plus default)
lpm(table, "8.8.8.8")  -> "gw0"   # only the default matches

Follow-up: naively this is O(n) per query. How would you speed it up with millions of routes and high QPS? (A binary/Patricia trie keyed on prefix bits.) What if two identical prefixes have different next hops (ECMP)?

Approach

Parse the queried address once. Scan every table entry; for each CIDR, test membership (addr in net) and keep the match with the greatest prefixlen. ipaddress handles both membership and prefix length, so the whole thing is a linear scan with a running best.

Complexity: O(n) per lookup for n routes. A trie brings this to O(W) where W is the address width (32 for IPv4).

Solution (Python)

"""Drill 9 (solution): longest prefix match."""
from __future__ import annotations

import ipaddress


def lpm(table: list[tuple[str, str]], ip: str) -> str | None:
    addr = ipaddress.ip_address(ip)
    best_hop: str | None = None
    best_len = -1
    for cidr, next_hop in table:
        net = ipaddress.ip_network(cidr, strict=False)
        if addr in net and net.prefixlen > best_len:
            best_len = net.prefixlen
            best_hop = next_hop
    return best_hop

Pitfalls

Returning the first match, not the longest. You must compare prefixlen across all matches; order in the table is irrelevant.
Initializing best length to 0. Use -1 so a /0 default (prefixlen 0) can still win when it is the only match.
Host bits set in the CIDR. Pass strict=False so entries like "10.1.2.3/16" don't raise.
IPv4/IPv6 mixing. addr in net is False across families, which is correct — but be aware if a table mixes both.
Ties. Equal-length matches with different hops are ECMP; this version keeps the first seen. Name that explicitly in an interview.

4. Diff two configs

Problem. Target: 10 minutes. Standard library only.

diff_config(old, new) -> dict returning {"added": [...], "removed": [...]}:

added — lines present in new but not in old;
removed — lines present in old but not in new.
Order follows the source text (new for added, old for removed).

Normalization rules (same as drill 5):

Blank lines, "!", and lines starting with "#" are skipped;
Extra inner spaces are collapsed;
Leading/trailing whitespace is removed (indentation is not significant for the diff).

old = "hostname r1\n!\ninterface eth0\n  mtu 1500"
new = "hostname r1\ninterface eth0\n  mtu 9000"
-> {"added": ["mtu 9000"], "removed": ["mtu 1500"]}

Follow-up: how does this differ from a line-diff (git)? How would you account for section hierarchy so that "mtu 1500" under eth0 isn't confused with "mtu 1500" under eth1?

Approach

Normalize both configs into cleaned line lists with a shared helper (strip, drop comment/marker/blank lines, collapse inner spaces). Build a set of each for O(1) membership, then produce added and removed by filtering each list against the other's set — filtering the list (not the set) preserves source order.

Complexity: O(n + m) time and space for configs of n and m lines.

Solution (Python)

"""Drill 10 (solution): config diff."""
from __future__ import annotations


def _clean(config: str) -> list[str]:
    out: list[str] = []
    for line in config.split("\n"):
        stripped = line.strip()
        if not stripped or stripped == "!" or stripped.startswith("#"):
            continue
        out.append(" ".join(stripped.split()))
    return out


def diff_config(old: str, new: str) -> dict:
    old_lines = _clean(old)
    new_lines = _clean(new)
    old_set = set(old_lines)
    new_set = set(new_lines)
    added = [line for line in new_lines if line not in old_set]
    removed = [line for line in old_lines if line not in new_set]
    return {"added": added, "removed": removed}

Pitfalls

Losing order. Deriving results from set difference alone scrambles order; iterate the original list and test membership in the other set.
Skipping normalization. Without collapsing inner spaces and stripping indentation, cosmetically identical lines show up as spurious add/remove pairs.
Duplicate lines. A set-based diff treats repeats as one; if a config legitimately has duplicates and counts matter, you need a multiset (Counter).
Flat vs hierarchical. This is a flat set diff — it can't distinguish mtu 1500 under different parents. The hierarchical answer is to key each line by its section path (tie-in to drill 5).

5. Prefix aggregation (supernetting)

Problem. Target: 12 minutes. The ipaddress module is allowed, but you may not use collapse_addresses — the point is to implement the collapse by hand (sort + merge).

aggregate(prefixes) -> list[str] — collapse a list of CIDRs into the minimal equivalent set:

drop prefixes nested inside another prefix from the list;
merge two "halves" of a supernet into it (10.0.0.0/25 + 10.0.0.128/25 -> 10.0.0.0/24);
apply merging repeatedly until nothing changes.
The result is sorted by address, then by prefix length. Duplicates and overlaps on input are allowed.

aggregate(["10.0.0.0/25", "10.0.0.128/25"]) -> ["10.0.0.0/24"]
aggregate(["10.0.0.0/24", "10.0.0.0/25"])   -> ["10.0.0.0/24"]
aggregate(["10.0.0.0/24", "10.0.2.0/24"])   -> ["10.0.0.0/24", "10.0.2.0/24"]

Follow-up: in production this is ipaddress.collapse_addresses — name it. Why can't you merge 10.0.1.0/24 + 10.0.2.0/24 into a /23? (The boundary isn't on a power-of-two: the /23 supernet of .1.0 starts at .0.0, not .1.0.)

Approach

Deduplicate into ip_network objects and sort by (network_address, prefixlen). Then iterate a fixed-point loop with two passes: (1) drop any net that is a subnet_of the last kept net (containment removal); (2) walk adjacent pairs and, when two neighbors share a prefix length and together fill their common supernet (the first is the supernet's base and the second is a subnet of it), replace the pair with supernet(). Re-sort and repeat until a full pass makes no change — this lets a freshly merged /24 pair up into a /23, and so on.

Complexity: each pass is O(n log n) from the sort; the outer loop runs at most O(depth) times as prefixes shorten, so O(n log n · W) worst case.

Solution (Python)

"""Drill 11 (solution): prefix aggregation by hand (no collapse_addresses)."""
from __future__ import annotations

import ipaddress


def _key(net):
    return (int(net.network_address), net.prefixlen)


def aggregate(prefixes: list[str]) -> list[str]:
    nets = sorted(
        {ipaddress.ip_network(p, strict=False) for p in prefixes}, key=_key
    )
    changed = True
    while changed:
        changed = False

        # 1) drop nets contained in an earlier (bigger) one
        kept = []
        for net in nets:
            if kept and net.subnet_of(kept[-1]):
                changed = True
                continue
            kept.append(net)

        # 2) merge adjacent sibling halves into their supernet
        merged = []
        i = 0
        while i < len(kept):
            cur = kept[i]
            if i + 1 < len(kept) and cur.prefixlen == kept[i + 1].prefixlen and cur.prefixlen > 0:
                sup = cur.supernet()
                if sup.network_address == cur.network_address and kept[i + 1].subnet_of(sup):
                    merged.append(sup)
                    i += 2
                    changed = True
                    continue
            merged.append(cur)
            i += 1

        nets = sorted(set(merged), key=_key)

    return [str(n) for n in nets]

Pitfalls

Merging non-aligned neighbors. Two adjacent /24s only merge if the lower one is the supernet's base (sup.network_address == cur.network_address). 10.0.1.0/24 + 10.0.2.0/24 fails this — don't blindly pair by adjacency.
Single-pass merging. A merge can create a new pairing opportunity one level up; you must loop to a fixed point, not merge once.
Guarding prefixlen > 0. Don't try to supernet a /0.
Skipping containment. A /25 inside a /24 must be dropped before/alongside merging, or you get overlapping output.
Not deduping. Sort a set of networks; duplicate inputs otherwise break the pairwise merge logic.
Using collapse_addresses. It's banned here — but name it as the production tool.

6. Shortest path by latency (Dijkstra)

Problem. Target: 15 minutes. Standard library only (heapq helps).

shortest_path(links, src, dst) -> tuple[list[str], float] | None

links is a list of (a, b, latency) — undirected edges, latency > 0.
Return (path, total_latency) with minimal latency; path is the node list from src to dst inclusive.
No path (or node not in the graph) returns None. src == dst returns ([src], 0.0).

links = [("A","B",1.0), ("B","C",1.0), ("A","C",5.0)]
shortest_path(links, "A", "C") -> (["A","B","C"], 2.0)

On equal latency the choice is deterministic (tie-break by node name).

Follow-up: why Dijkstra instead of BFS (as in drill 4)? What breaks with negative weights? How would you get the k shortest paths for backup routes (ECMP / fast-reroute)?

Approach

Build a weighted adjacency map (both directions). Run Dijkstra from src with a binary heap of (distance, node): including the node in the tuple gives a deterministic tie-break by name when distances are equal. Pop the smallest, skip if already finalized, and relax each neighbor, recording a prev pointer on improvement. Stop when dst is finalized. Reconstruct by walking prev back from dst.

Complexity: O((V + E) log V) with a binary heap; O(V + E) space.

Solution (Python)

"""Drill 12 (solution): weighted shortest path (Dijkstra)."""
from __future__ import annotations

import heapq


def shortest_path(links: list[tuple[str, str, float]], src: str, dst: str):
    graph: dict[str, list[tuple[str, float]]] = {}
    for a, b, w in links:
        graph.setdefault(a, []).append((b, w))
        graph.setdefault(b, []).append((a, w))

    if src not in graph or dst not in graph:
        return ([src], 0.0) if src == dst else None

    dist: dict[str, float] = {src: 0.0}
    prev: dict[str, str] = {}
    visited: set[str] = set()
    # (distance, node) -- node in the key gives a deterministic tie-break
    pq: list[tuple[float, str]] = [(0.0, src)]

    while pq:
        d, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        if node == dst:
            break
        for nb, w in graph[node]:
            nd = d + w
            if nb not in dist or nd < dist[nb]:
                dist[nb] = nd
                prev[nb] = node
                heapq.heappush(pq, (nd, nb))

    if dst not in dist:
        return None

    path = [dst]
    while path[-1] != src:
        path.append(prev[path[-1]])
    path.reverse()
    return (path, dist[dst])

Pitfalls

Using BFS on weighted edges. BFS minimizes hops, not latency — it returns A→C (5.0) instead of A→B→C (2.0). You need Dijkstra.
No visited/finalized set. Without skipping already-finalized nodes you re-expand stale heap entries; the "lazy deletion" pattern (push duplicates, skip on pop) is what keeps it correct and simple.
Non-deterministic ties. Put the node name in the heap tuple so equal-distance pops break consistently.
src == dst and missing nodes. Handle both before the main loop; return ([src], 0.0) for the trivial case and None when a node isn't in the graph.
Negative weights. Dijkstra assumes non-negative edges; a negative latency breaks the finalized-once invariant (use Bellman-Ford instead). Latencies are positive here, so it's fine.

Related: Interview Prep index.