~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Weighted graphs

Dijkstra (weighted shortest paths)

Heap of (dist, node), skip stale entries; non-negative weights only.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: you want the shortest path with non-negative weights: network delay, cheapest route, minimum effort.

dist = {src: 0}; pq = [(0, src)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist.get(u, inf): continue     # stale entry
    for v, w in adj[u]:
        nd = d + w
        if nd < dist.get(v, inf):
            dist[v] = nd; prev[v] = u
            heapq.heappush(pq, (nd, v))

O((V + E) log V). Rebuild the path by following prev back from the target.

Gotchas: skip stale heap entries. It's wrong with negative edges (use Bellman-Ford). With 0/1 weights, a deque-based BFS is faster. "At most k stops" breaks plain Dijkstra, so use the state (node, stops) or Bellman-Ford rounds.

8 problems

Interview roadmap

Weighted graphs Dijkstra, union-find, spanning trees.

Dijkstra (weighted shortest paths) guide

esc