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

Implement topological sort for a DAG using Kahn's algorithm in Python. Function signature: def topological_sort(graph: Dict[int, List[int]]) -> Optional[List[int]]. Return a list representing one valid topological order or None if a cycle exists. Include a small example graph and explain how the algorithm detects cycles.

Sample Answer

To implement topological sort with Kahn's algorithm we:1) compute in-degrees for all nodes, 2) enqueue nodes with in-degree 0, 3) repeatedly pop, append to order, decrement neighbors' in-degrees and enqueue new zeros. If we output fewer nodes than exist, a cycle exists and we return None.

python

from collections import deque, defaultdict
from typing import Dict, List, Optional

def topological_sort(graph: Dict[int, List[int]]) -> Optional[List[int]]:
    """
    Kahn's algorithm for topological sorting.
    graph: adjacency list mapping node -> list of neighbors (edges node -> neighbor)
    Returns a list with one valid topological order, or None if a cycle exists.
    """
    indeg = defaultdict(int)
    nodes = set(graph.keys())
    for u, nbrs in graph.items():
        for v in nbrs:
            indeg[v] += 1
            nodes.add(v)

    q = deque([n for n in nodes if indeg[n] == 0])
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    # If we didn't include all nodes, there's a cycle
    return order if len(order) == len(nodes) else None

Example:graph = {1: [2,3], 2: [4], 3: [4], 4: []}topological_sort(graph) -> one valid output: [1,2,3,4] or [1,3,2,4]

Cycle detection explanation:Kahn's algorithm succeeds only if at least one node has in-degree 0 at every step. If a cycle exists, nodes in the cycle will never reach in-degree 0, so the queue empties before visiting all nodes — indicated by returned None.

Complexity:Time O(V+E), Space O(V+E). Edge cases: empty graph -> [], isolated nodes handled via nodes set, invalid input types should raise normally.

MediumTechnical

73 practiced

Explain how to implement parallel BFS on GPU using a frontier-based approach. Discuss work distribution across threads/warps, handling duplicates and race conditions when multiple threads attempt to mark visited nodes, memory access patterns and coalescing, and optimizations such as using bitmaps or push/pull (top-down vs bottom-up) strategies.

Sample Answer

Overview: Implementing frontier-based parallel BFS on GPU processes one level (frontier) at a time. Each thread/warp explores edges from frontier vertices to discover next-level vertices; synchronization happens between levels.

Work distribution:- Assign one thread per frontier vertex for high-degree variability causes imbalance; better: assign a warp or CTA per high-degree vertex and threads-per-edge for fine-grained work-stealing.- Use prefix-sums to allocate output slots for newly discovered neighbors (compact next-frontier).

Handling duplicates and races:- Use an atomic compare-and-swap (atomicCAS) or atomicExch on a visited array to atomically mark a node when first discovered; only the thread that wins adds it to next frontier.- To reduce atomics, use per-block hash tables or bloom/bitmaps and later compact unique entries.

Memory access & coalescing:- Store adjacency in CSR (offsets + neighbor list). Ensure threads in a warp access consecutive neighbor indices to enable coalesced reads; mapping vertices to warps by contiguous IDs helps.- Read-only arrays (offsets, neighbors) should be in GPU global memory with caching; use __ldg() or place in read-only cache where supported.

Optimizations:- Bitmap visited (bitset) reduces memory and atomic contention; use atomic bit-set or warp-aggregated writes.- Push (top-down): frontier pushes neighbors — good when frontier is small.- Pull (bottom-up): unexplored vertices check if any neighbor is in frontier — good when most vertices are unexplored (large frontier); avoids scanning many edges repeatedly.- Hybrid push/pull: switch based on frontier size or edges-to-explore heuristic (e.g., direction-optimizing BFS).- Use warp-level primitives (ballot, shuffles) to aggregate checks and reduce atomics; use shared memory for local deduplication and load balancing.- Use work queues, load balancing via dynamic parallelism or persistent threads to amortize kernel launch overhead.

Trade-offs:- Atomics are simple but costly at high contention; bitmaps + pull reduce atomics but increase per-vertex work.- Balance per-thread work vs memory bandwidth; prefer grouping neighbors to maximize coalescing and minimize global atomics.

This combination yields a scalable GPU BFS: frontiers processed level-by-level, with load-balanced assignment, atomic-safe marking (or bitmap dedup), cache/coalesced memory access, and push/pull switching for performance.

HardTechnical

74 practiced

Prove the correctness of the Bellman-Ford algorithm for single-source shortest paths. Then describe a concrete algorithm to detect a negative cycle reachable from the source and to extract the nodes forming that cycle. Provide the key proof steps and complexity analysis.

Sample Answer

Proof sketch (correctness):- Bellman-Ford relaxes all edges up to |V|-1 times. Claim: after k iterations, all shortest-path distances using ≤k edges are found. Proof by induction: base k=0 trivial (d[s]=0, others = ∞). Inductive step: any shortest s→v path of ≤k edges can be written s→u (≤k−1 edges) then edge (u,v); after k−1 iterations d[u] is shortest for ≤k−1 edges, so relaxing (u,v) sets d[v] correctly. Since any simple shortest path has ≤|V|−1 edges, after |V|−1 iterations distances equal true shortest-path distances if no negative cycle reachable.

Negative-cycle detection and extraction:- After |V|−1 relaxations, run one more full relaxation over all edges. If any edge (u,v) satisfies d[u]+w(u,v)<d[v], then v is reachable from a negative cycle (or in it).- To extract an explicit cycle: when a node v is relaxed in the |V|th pass, follow predecessors pred[] for |V| steps from v to ensure you reach a node guaranteed inside the cycle (walking |V| steps removes tails). Let x be the node reached; then traverse pred[] starting from x until you return to x, recording nodes — that sequence is a negative cycle.

Algorithm (concise):1. Initialize d[s]=0, others ∞; pred[]=null.2. Repeat |V|−1 times: for each edge (u,v): if d[u]+w<d[v]: d[v]=d[u]+w; pred[v]=u.3. For each edge (u,v): if d[u]+w<d[v]: // negative cycle reachable - y = v; for i in 1..|V|: y = pred[y]; - start = y; cycle = []; do { cycle.append(y); y = pred[y]; } while y != start; - return cycle (weights along cycle sum negative).4. If no such edge, return distances.

Proof of extraction: After |V|−1 relaxations, any further decrease implies a path with ≥|V| edges, hence a repeated vertex → negative cycle. Walking |V| steps on pred[] from a node influenced by the cycle ensures entry into the cycle.

Complexity:- Time: O(VE) for relaxations; extra detection/extraction O(V + E) (dominated by O(VE)).- Space: O(V) for distances and predecessors.

Key guarantees:- If no negative cycles reachable, Bellman-Ford yields correct shortest paths.- If a negative cycle is reachable, the detection step finds a vertex affected and extraction yields the cycle.

HardSystem Design

56 practiced

Design an I/O-efficient algorithm to perform BFS on a graph that does not fit in memory (external-memory/out-of-core). Describe data layout on disk, streaming patterns to process frontier levels in batches, how to minimize random disk seeks, and how to measure complexity in terms of I/O operations. Mention existing frameworks or systems (GraphChi, X-Stream) that implement such approaches.

Sample Answer

Requirements & constraints:- Graph G=(V,E) too large for RAM; assume internal memory M (bytes), disk block size B, and edges stored on disk.- Goal: breadth-first search from source s, minimizing random disk I/Os (block transfers).

High-level idea:- Organize data to stream large sequential scans instead of random seeks. Process BFS level-by-level but in batches: represent the current frontier compactly (bitmap or list of vertex IDs) and stream through edge data to relax neighbors in a few sequential passes.

Data layout on disk:- Vertex partitioning: divide vertices into P contiguous ID ranges (shards) sized so per-shard metadata fits in memory. Each shard stores: - Out-edge lists for vertices in that shard concatenated and sorted by source (CSR-like on disk). - Per-shard index: vertex -> (offset,length).- Store a global vertex-status array (visited flag + distance) as a compact on-disk bitmap or per-shard bitmaps.- Optionally store reverse edges or both directions if needed.

Processing pattern (streaming frontier batches):1. Frontier representation: keep current frontier as an in-memory list if small, otherwise as a compressed on-disk list or bitmap per shard.2. For each shard (in disk order), stream its CSR block(s): - Load a block of consecutive adjacency entries (sequential read). - For each edge u->v where u is in current frontier (check via per-shard frontier bitmap or prefix in-memory buffer), attempt to mark v visited (check per-shard visited bitmap). - Emit newly discovered vertices into an output buffer for their destination shard (append-only), using batched writes.3. After scanning all shards, we have per-shard next-frontier buffers; swap them into the frontier for next level and repeat.

Minimizing random seeks:- Keep adjacency lists stored contiguously and process shards in disk order to turn random accesses into sequential scans.- Use per-shard frontier/visited bitmaps so checks are mostly in-memory bit tests; only when a vertex’s adjacency spans many blocks will you still read sequentially.- Buffer writes to per-destination-shard files to avoid tiny random writes; flush large blocks.- Use asynchronous prefetching, readahead, and large I/O sizes (~MB) to maximize throughput.- Merge small per-level frontier outputs via external sort or de-duplication using streaming hash/gather to avoid repeated visits.

I/O complexity (in external-memory terms):- Measure in block transfers. Let Scan(X) = Theta(X/B).- Semi-external BFS (vertices in memory, edges on disk): each BFS level requires scanning adjacency lists of frontier vertices. Worst-case naive bound: O(|E|/B) per level (bad). With the streaming/shard approach you can ensure each disk edge is scanned only when its source’s shard is processed—so total I/O across entire BFS is O(Scan(E) + Scan(V)) plus extra for writing/reading frontier buffers: O((E+V)/B · polylog_{M/B}), typically O((E+V)/B).- More precise: With P shards sized so per-shard metadata fits in memory, each level does P sequential scans of the shard edge blocks touched by the frontier. With frontier batching and deduplication, empirical cost approaches O(Scan(E)) overall plus O(#levels · small overhead). If vertices are in memory, you get O(Scan(E)) total I/Os.

Variants & trade-offs:- Fully external: both V and E on disk — need external-memory priority structures; more I/O.- Semi-external: vertex arrays fit in memory — simpler and faster.- Larger P reduces per-shard metadata but can increase passes; choose shard size ~M/constant.- Deduplication cost: trade write/read overhead vs extra scans; using bitmaps prevents enqueue duplicates cheaply.

Existing frameworks:- GraphChi: shard-based “Parallel Sliding Windows” — converts random accesses into sequential passes over shards and keeps per-shard windows in memory; designed for out-of-core vertex-programs including BFS-like traversals.- X-Stream: edge-centric streaming; processes edges in sequential streams and writes updates via scatter/gather; minimizes random writes by streaming edges and performing out-of-core shuffle.- FlashGraph / PowerGraph variants: exploit SSDs and vertex-cut partitioning for high performance; useful if storage is fast.

Practical tips:- Use compressed adjacency storage (variable-byte, delta) to reduce I/O volume.- Keep visited bitmaps in memory or memory-mapped for cheap checks.- Batch IO, use asynchronous I/O, use SSDs for lower seek cost.- Instrument: measure total bytes read/written, number of block transfers, and time per sequential read vs random seeks to validate efficiency.

This design converts BFS into a sequence of sequential disk scans and batched writes, yielding near-optimal I/O (O((E+V)/B) under typical assumptions) and is the basis for GraphChi/X-Stream-style out-of-core graph processing.

EasyTechnical

61 practiced

Given a directed graph in adjacency list form, implement a function in Python to detect whether the graph contains a directed cycle. Use DFS with 3-color marking (unvisited, visiting, visited) or an explicit recursion stack. Function signature: def has_cycle_directed(graph: Dict[int, List[int]]) -> bool. Provide the time and space complexity and example inputs demonstrating detection.

Sample Answer

To detect a directed cycle we can run DFS and mark nodes with 3 colors: 0=unvisited, 1=visiting (in current recursion stack), 2=visited. If DFS reaches a node marked visiting, we found a back edge -> cycle.

python

from typing import Dict, List

def has_cycle_directed(graph: Dict[int, List[int]]) -> bool:
    """
    Detects a directed cycle using DFS with 3-color marking.
    graph: adjacency list mapping node -> list of neighbors
    Returns True if a directed cycle exists, else False.
    """
    UNVISITED, VISITING, VISITED = 0, 1, 2
    color = {node: UNVISITED for node in graph}

    def dfs(u: int) -> bool:
        color[u] = VISITING
        for v in graph.get(u, []):
            if color.get(v, UNVISITED) == UNVISITED:
                if dfs(v):
                    return True
            elif color[v] == VISITING:
                # found a back edge -> cycle
                return True
        color[u] = VISITED
        return False

    # If graph may have nodes referenced but not keys, include them
    for u in list(graph.keys()):
        if color[u] == UNVISITED:
            if dfs(u):
                return True
    return False

Key points:- We mark nodes as VISITING when entering and VISITED when exiting DFS; encountering VISITING means a cycle.- Handles disconnected graphs; uses graph.get to tolerate missing keys.

Time complexity: O(V + E) — each node and edge visited once.Space complexity: O(V) for color map and recursion stack (O(V) worst-case).

Examples:- graph = {1: [2], 2: [3], 3: []} -> False (no cycle)- graph = {1: [2], 2: [3], 3: [1]} -> True (1->2->3->1 cycle)- graph = {1: [2], 3: [4], 4: [3]} -> True (cycle between 3 and 4)

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.