Graph Algorithms and Traversal Questions

Covers fundamental representations, traversal techniques, and classical algorithms for graph structured data. Candidates should understand graph representations such as adjacency list and adjacency matrix and the tradeoffs in time and space for each. Core traversal skills include implementing and reasoning about breadth first search and depth first search for reachability, traversal order, and unweighted shortest path discovery, as well as tree traversal variants and their relationship to graph traversals. Algorithmic topics include cycle detection, topological sorting for directed acyclic graphs, connected components and strongly connected components, and shortest path and pathfinding algorithms for weighted graphs including Dijkstra algorithm and Bellman Ford algorithm with discussion of negative weights and appropriate use cases. Candidates should be able to analyze time and space complexity, choose appropriate auxiliary data structures such as queues, stacks, priority queues, and union find, handle directed versus undirected and weighted versus unweighted graphs, discuss implementation details and trade offs, and explain practical applications such as dependency resolution, scheduling, pathfinding, connectivity queries, and roles of graph algorithms in system design and data processing.

EasyTechnical

76 practiced

Explain the union-find (disjoint set) data structure: the operations find and union, how path compression and union by rank/size improve performance, and why the amortized cost is nearly constant. Describe two SRE use cases where union-find is useful, such as offline connectivity queries or grouping servers by failure domain.

MediumTechnical

60 practiced

Design and describe an incremental/online approach using union-find to answer a sequence of connectivity queries on a graph that only receives edge additions (no deletions). Explain how you would implement it to support a mix of union operations and connectivity queries, and analyze amortized complexity. Mention batching strategies for performance.

Sample Answer

Approach (high-level):Use a classic Union-Find (Disjoint Set Union, DSU) to maintain connected components as edges are incrementally added. Support two operations: Union(edge u,v) to add an edge, and Connected(u,v) to answer connectivity queries. Because there are no deletions, DSU is ideal: merges only increase connectivity.

Implementation details:- Data structures: parent[], rank[] (or size[]). Path compression on find and union by rank/size.- API: - find(x): compress path returning root. - union(u,v): ru=find(u); rv=find(v); if ru!=rv attach smaller under larger and decrement component count. - connected(u,v): return find(u)==find(v).- Concurrency: shard the node id space if extremely large; each shard runs its own DSU and a coordinator handles cross-shard unions via a lightweight mapping (or use distributed consensus for global merges). Use thread-safe unions or serialize union ops per shard.

Amortized complexity:- With union by rank/size + path compression, any m operations (unions + finds) on n elements cost O(m α(n)) amortized, where α is inverse Ackermann (practically constant).

Batching strategies for performance:- Batch edge-adds: accumulate a batch of edges and apply unions in-memory to reduce locking/synchronization overhead. Use union-by-size to process high-degree nodes first to shorten paths.- Bulk-find optimization: if many connectivity queries arrive, run batch find with path compression on all queried nodes to amortize costs.- Snapshotting & persistence: periodically snapshot parent/size arrays to durable storage to speed recovery; replay recent batched edges on restart.- Offline / large-scale merges: if tens of millions of edges arrive, run hierarchical batching: apply batches locally, compact components into supernodes, then merge supernodes to reduce work.

Edge cases & operational notes:- New nodes: lazily initialize on first reference.- Memory limits: use compressed integer IDs, eviction or external sharding.- Monitoring: track ops/sec, batch latency, component count; alert if α(n) grows unexpectedly (which indicates misuse).

HardTechnical

66 practiced

Routing loops in a microservice network cause outages and amplification. Design algorithms to detect routing loops using traces and graph analysis, and propose automated remediation steps (rate-limiting, circuit-breaking, rollback). Discuss how to handle false positives caused by sampled traces and techniques to minimize noisy detections.

Sample Answer

Requirements & goals:- Detect routing loops quickly from distributed traces and service graph; prioritize high-confidence, low-latency alerts to prevent amplification.- Provide automated mitigation (rate-limit, circuit-break, rollback) with safe guardrails.- Minimize false positives from sampled traces.

Detection approach (overview):1. Build a time-windowed directed service-call graph from traces (edges = observed RPC from A→B with timestamps, latency, sampling weight).2. Run incremental loop-detection on the dynamic graph: detect cycles using depth-first search (DFS) / Tarjan on the directed multigraph, but weighted by recent traffic volume to prioritize impactful loops.3. Use trace-path analysis: for each trace, look for repeated service IDs or same trace-id re-entering a service (strong signal of loop). Aggregate counts per window and compute loop amplification factor = total requests attributable to loop / baseline traffic.

Algorithm details:- Streaming ingestion: maintain adjacency lists with edge counters and EWMA of RPS per edge.- Cycle detection: perform bounded DFS from nodes with high out-degree, limit depth to N (e.g., 10) to avoid noisy long paths. Use Tarjan SCC periodically for comprehensive detection.- Trace-confirmation: for candidate cycle C, require at least K distinct traces that traverse the cycle end-to-end OR trace evidence of repeated hops within single trace to confirm.

Automated remediation playbook:1. Throttling: apply progressive rate-limits at ingress services in the cycle (start with 10–20% reduction) to reduce amplification while preserving availability.2. Circuit-break: when amplification factor exceeds threshold AND confirmed by X traces, open circuit breakers on the highest-amplitude edge(s) with exponential backoff and bulkhead isolation.3. Rollback / Deploy Freeze: if circuit-break triggers fail to stabilize or if a deploy timestamp correlates with loop onset, automatically flag and optionally rollback recent deploys using canary metadata; require human approval for full rollback unless SLO breach severe.4. Orchestration: implement remediation as runbooks in an automation engine (e.g., Argo Workflows/Runbooks, Terraform + service mesh API) with reversible actions and audit logs. Always notify on-call and require safety checks (rate-limit simulation, dry-run) when possible.

Handling false positives (sampled traces):- Weight edges by sample-inverse probability: when traces are sampled (1/N), scale counts by N but also track variance; require statistical confidence (e.g., Wilson score) before alerting.- Use multi-signal confirmation: combine tracing with metrics (increasing retry counts, queue lengths, CPU, error rates) and network telemetry (connection counts).- Use time-correlation: a true loop will produce rapid growth in RPS/errors; require monotonic growth pattern over T minutes.

Noise reduction techniques:- Adaptive thresholds: compute baseline per-service patterns and use anomaly detection (z-score / EWMA) instead of fixed thresholds.- Depth and path-length heuristics: ignore cycles that involve ephemeral sidecars or health-check ports; only consider application-level RPC IDs.- Trace sampling amplification: trigger high-fidelity sampling (trace tail or full-sample) for services involved in a suspected loop to confirm.- Rate-limit alerts: aggregate per-candidate and suppress repeats until state changes.

Operational considerations and trade-offs:- Aggressive automation reduces mean time to remediate but risks false shutdowns; use staged actions and escalation rules.- Maintain simulation & runbook tests in staging to validate automated remediations.- Logging, observability: store detected cycles, evidence traces, action history for post-incident analysis and to tune thresholds.

Example quick pseudocode (conceptual):- Ingest trace → update edge counters and sample weights → if edge EWMA spike and DFS finds cycle with aggregated weighted RPS > threshold → increase trace sampling on implicated services → if confirmed by K traces or metric corroboration → execute staged mitigation (rate-limit → circuit-break → rollback if unresolved).

This design balances fast detection using graph analysis + trace confirmation with conservative, reversible automation and statistical guards to minimize noisy detections.

HardSystem Design

64 practiced

Design a multi-region routing system for cross-datacenter traffic that minimizes latency and monetary cost subject to per-link capacity constraints and SLOs. Show how to model this as a graph or flow optimization (e.g., min-cost flow or LP), discuss exact vs approximate solvers and runtime tradeoffs, and explain strategies for real-time rerouting under failures.

Sample Answer

Requirements & constraints:- Functional: route cross-datacenter flows between region pairs minimizing latency and monetary cost.- Non-functional: respect per-link capacity, meet per-flow SLOs (e.g., 99.9% latency bound), support fast reroute under failures, operate in real time.

Model as graph & flow optimization- Graph: directed graph G=(V,E). Nodes V = datacenters + routers; edges e∈E have capacity Ce, latency le, and cost per unit traffic ce ($/Gb).- Multi-commodity flow: each demand d (source s_d, sink t_d, demand volume D_d, latency SLO L_d) is a commodity.- Variables: f_{d,e} ≥ 0 = flow of commodity d on edge e.- Constraints: 1) Flow conservation: ∑_{in} f_{d,in} = ∑_{out} f_{d,out} except at s_d(+D_d)/t_d(-D_d). 2) Capacity: ∑_d f_{d,e} ≤ C_e ∀ e. 3) Latency: path latency for commodity d = ∑_e (f_{d,e}>0 ? l_e : 0) ≤ L_d. (Enforce by disallowing paths whose sum l_e > L_d, i.e., restrict feasible edges per commodity by precomputing allowed paths.)- Objective: minimize ∑_{d,e} f_{d,e} * c_e + λ * (measured latency penalty). Alternatively formulate as linear program (LP) by precomputing K candidate paths per demand, variables x_{d,p} for flow on path p, enforce path latency ≤ L_d, capacity constraints sum over paths using edge e.

Exact vs approximate solvers & runtime tradeoffs- Exact solvers: LP/MIP solvers (Gurobi, CPLEX) or min-cost multi-commodity flow via network simplex. Pros: optimality, clear SLO guarantees. Cons: high runtime for large topologies / many commodities (NP-hard for integral multi-commodity), poor for sub-second decisioning.- Scalable exact-ish: linear relaxation + randomized rounding; solve LP periodically (every minutes) to get baseline allocation.- Approximate/heuristic approaches (real-time): - Kernel: K-shortest paths per demand; solve min-cost flow on path-space (reduces variables). - Greedy or primal-dual online algorithms: route demands one-by-one using shortest-cost-per-latency path while respecting residual capacities. - Lagrangian relaxation / dual decomposition: decompose by commodity, update link prices iteratively (good for distributed control planes). - Flow-splitting: use weighted ECMP or segment-routing to split traffic across top-K low-latency, low-cost paths.Tradeoffs: heuristics are fast (ms–s) but can be suboptimal; LPs yield better cost but require batching and slower cycles (secs–mins). Combine: run global optimizer (LP) periodically; use fast local heuristics for per-flow admission and transient events.

Real-time rerouting & failure strategies- Fast local failover: precompute 1:1 and 1:many backup paths per primary path (diverse edges) and program hardware (fast failover groups) to switch immediately on link failure (sub-50ms).- SDN controller + data-plane split: - Data-plane: ECMP/segment routing for normal load; hardware-level protection for immediate failover. - Control-plane: SDN controller detects failure via telemetry, recomputes flows using incremental constrained optimization (only affected demands/edges), and pushes updated forwarding entries. Use incremental repairs to minimize churn.- Graceful traffic shift: use congestion-aware weighted multipath with ramping (traffic shifting in small steps) to avoid packet reordering & transient overload. Apply rate-limiters and congestion-shedding policies when capacity tight.- Consistency & safety: implement transactional or versioned policy updates (two-phase install), avoid loops during convergence (use ordered updates or per-flow labels).- Admission control & SLO-aware throttling: when capacity can't meet SLOs, prioritize critical flows (per SLO weight), preempt lower-priority traffic, and signal upstream clients.- Telemetry & automation: real-time metrics (per-link utilization, latency histograms, packet loss). Use anomaly detectors to trigger recompute or rollbacks. Maintain a “hot” cache of precomputed alternate allocations for common failure scenarios.

Operational notes & best practices- Path precomputation: for each region-pair keep top-K disjoint latency-cost-optimal paths; use them in real time.- Hierarchical control: global optimizer for periodic rebalancing (minutes), regional controllers for sub-second failover.- Pricing signal: treat per-link cost as dynamic to reflect egress charges or spot pricing; use Lagrange multipliers as shadow prices to respect capacity.- Testing: simulate failures and load bursts; run chaos testing and measure failover time and SLO impact.- Metrics: track SLO compliance, cost delta vs baseline, failover MTTR, and flow churn.

This design gives mathematically-founded global optimization with practical, low-latency heuristics and robust fast-fail mechanisms suitable for an SRE operating multi-region traffic with strict SLOs.

EasyTechnical

59 practiced

Write a Python function that detects whether an undirected graph (adjacency list Dict[int, List[int]]) contains any cycle. The function should return True if a cycle exists and False otherwise. Explain why you must track the parent node during DFS to avoid false-positive detection from immediate back-edges. Ensure O(|V|+|E|) time.

Sample Answer

To detect a cycle in an undirected graph, run DFS from each unvisited node and track the parent of the current node. For undirected graphs, an edge back to the immediate parent is expected and must not be treated as a cycle — tracking parent avoids this false positive. This DFS visits each vertex and edge once: O(|V|+|E|).

python

from typing import Dict, List

def has_cycle(graph: Dict[int, List[int]]) -> bool:
    visited = set()

    def dfs(u: int, parent: int) -> bool:
        visited.add(u)
        for v in graph.get(u, []):
            if v == parent:
                # ignore the edge back to the node we came from
                continue
            if v in visited:
                # found a back-edge to an already visited node -> cycle
                return True
            if dfs(v, u):
                return True
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

Key points:- Parent parameter prevents treating the undirected edge to the caller as a cycle.- Time: O(|V|+|E|), Space: O(|V|) recursion/visited.Edge cases: disconnected graph (loop over nodes), isolated nodes, self-loop (detect by checking v==u).

Unlock Full Question Bank

Get access to hundreds of Graph Algorithms and Traversal interview questions and detailed answers.

Join thousands of developers preparing for their dream job.