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

65 practiced

Explain the core differences between Breadth-First Search (BFS) and Depth-First Search (DFS). For each algorithm, list three common practical use cases in machine learning engineering or systems (e.g., unweighted shortest path, topological order, feature propagation).

MediumTechnical

52 practiced

Implement a function k_hop_neighbors(graph, source, k) that returns all nodes at distance <= k from source in Python using BFS. Graph may be large but fits in memory; ensure you avoid revisiting nodes and that the function returns counts per hop as well as the flattened list.

Sample Answer

Approach: perform breadth-first search from source up to depth k, tracking visited nodes to avoid revisits. At each BFS level collect nodes discovered at that hop; produce counts per hop (including hop 0) and a flattened list of all nodes at distance <= k.

python

from collections import deque, defaultdict
from typing import Dict, Iterable, List, Tuple, Set

def k_hop_neighbors(graph: Dict[int, Iterable[int]], source: int, k: int) -> Tuple[List[int], List[int]]:
    """
    Returns (counts_per_hop, flattened_nodes)
    - graph: adjacency list mapping node -> iterable of neighbors
    - source: starting node
    - k: maximum hop distance (>=0)
    """
    if k < 0:
        raise ValueError("k must be non-negative")
    if source not in graph:
        # If source not present, treat as isolated node
        return [1] + [0]*k, [source]

    visited: Set[int] = set([source])
    q = deque([source])
    counts_per_hop: List[int] = []
    flattened: List[int] = [source]  # include hop 0

    # hop 0
    counts_per_hop.append(1)

    for hop in range(1, k+1):
        next_level = deque()
        while q:
            node = q.popleft()
            for nb in graph.get(node, ()):
                if nb not in visited:
                    visited.add(nb)
                    next_level.append(nb)
        counts_per_hop.append(len(next_level))
        flattened.extend(list(next_level))
        q = next_level
        if not q:
            # no more nodes to expand
            # fill remaining hops with zeros if any
            for _ in range(hop+1, k+1):
                counts_per_hop.append(0)
            break

    # ensure counts_per_hop length is k+1
    if len(counts_per_hop) < k+1:
        counts_per_hop.extend([0] * (k+1 - len(counts_per_hop)))

    return counts_per_hop, flattened

Key points:- Uses BFS level-order to get exact hop distances.- visited set prevents revisiting nodes and infinite loops on cycles.- Returns counts_per_hop of length k+1 (hop 0..k) and flattened list of nodes up to k hops.

Time complexity: O(V + E) (each edge/node processed once). Space: O(V) for visited and queue.

Edge cases:- k = 0 returns only source.- source not in graph handled as isolated node.- Disconnected graphs, cycles, and duplicated adjacency entries handled by visited set.

Alternatives:- If many queries with different sources, precompute multi-source BFS or compute k-step neighborhood via sparse matrix powers (SciPy) for batch feature engineering.

HardTechnical

54 practiced

Implement multi-source Dijkstra in Python: given multiple source nodes with initial distances (some may be zero or different), compute shortest distances to all nodes. Explain how to initialize the priority queue and why correctness still holds. Target complexity O(E log V).

Sample Answer

To compute shortest paths from multiple sources with possibly different initial distances, run Dijkstra seeded with all sources inserted into the priority queue with their given initial distances. The algorithm is identical to single-source Dijkstra because the PQ always extracts the currently smallest tentative distance globally.

python

import heapq
from collections import defaultdict

def multi_source_dijkstra(n, edges, sources):
    """
    n: number of nodes (0..n-1)
    edges: list of (u, v, w) for directed or undirected graphs (use both directions if undirected)
    sources: dict {node: initial_distance} - may include zeros or varying values
    Returns: list dist of length n with shortest distances (float('inf') if unreachable)
    """
    g = defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))
        # If undirected, uncomment: g[v].append((u, w))

    dist = [float('inf')] * n
    pq = []
    for s, d0 in sources.items():
        if d0 < dist[s]:
            dist[s] = d0
            heapq.heappush(pq, (d0, s))

    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Key points:- Initialize PQ with all (initial_distance, node). That ensures the smallest global tentative distance is processed first.- Correctness: Dijkstra's proof relies on processing nodes in nondecreasing tentative distance; seeding multiple sources preserves this invariant because all initial distances are present from start.- Complexity: Each edge relax once per decrease -> O(E log V) with binary heap. Space O(V+E).

Edge cases:- Negative weights: Dijkstra not applicable.- Duplicate sources: take min initial distance.- Disconnected nodes remain inf.

HardSystem Design

112 practiced

Design a compact on-disk format and API for storing a large static graph (hundreds of millions of edges) used for read-heavy nearest-neighbor and multi-hop queries in a low-latency online service. Consider compression, indexing, memory mapping, and how to serve adjacency slices to many concurrent workers efficiently.

Sample Answer

Requirements & constraints (clarify):- Read-only large static graph: ~100M+ edges, low-latency per-request (ms/sub-ms), heavy concurrent readers, queries: k-NN on node embeddings (returns candidate nodes) + multi-hop traversal (BFS/beam search).- Priorities: compact on-disk, random-access adjacency slices, low CPU per request, many concurrent workers.

High-level idea- Store graph as mmapped read-only files with per-node adjacency lists compressed into block-aligned segments. Maintain a compact offset index so any node’s adjacency slice can be zero-copy mapped + selectively decompressed. Shard primary files by node-id range (or hash) to reduce contention and support parallel IO.

On-disk layout (single shard)- Header (magic, version, shard range, node_count, edge_count, codec table)- Node index: fixed-size array of uint64 offsets (node i → byte offset in edge blob). For memory, use relative offsets (u32) when possible.- Edge blob: concatenation of compressed adjacency lists, stored as independent blocks. Each block: [block-header: node_id, compressed_size, uncompressed_size, encoding_type] + payload.- Footer: checksum, statistics.

Compression & encoding- If neighbor lists are sorted by node-id (recommended), use: - Delta encode IDs then Elias-Fano for very long lists (fast rank/select, memory compact). - Varint/Group varint or Frame-of-Reference (FOR) + SIMD-BP128 for medium lists. - For tiny lists, inline plain u32s (no decompression).- Store per-block codec tag to allow mixed encodings optimizing latency vs ratio.- Optionally store cached uncompressed blocks for hot nodes.

Indexing & random access- Node index gives direct block offset and length. Blocks are independent, so reading a node requires reading only its block.- For very large adjacency lists, split into multiple blocks (fixed-size uncompressed target e.g., 4KB-64KB) with local offsets in the node index (start block and count).- Maintain a small in-memory metadata (mmapped or loaded) with per-shard index and per-node degree to quickly decide algorithmic choices (e.g., skip empty nodes).

Memory-mapping & serving- Mmap the index and edge-blob file read-only. Since blobs are compressed, workers read the compressed slice (zero-copy), then decompress into thread-local buffers.- Use shared file-descriptors and OS page cache for automatic caching. Sharding reduces lock contention in OS VFS.- Provide an LRU per-process decompressed-block cache sized for memory budget to avoid repeated decompression of hot blocks.- Use asynchronous prefetching: when multi-hop traversal requests neighbors of many nodes, prefetch next blocks via posix_fadvise(FADV_WILLNEED) or aio_read to reduce tail latency.

API (C++/Python pseudo)- openShard(path, options) -> GraphShard handle- get_neighbors(node_id) -> NeighborSlice { pointer to compressed bytes, codec, uncompressed_len, degree } — zero-copy for codecs that support in-place decoding; otherwise provides a small buffer view- decode_neighbors(slice, out_buf) -> int[] (fast SIMD decode)- batch_get_neighbors(node_ids[]) -> vector<NeighborSlice> (parallelized)- multi_hop(start_nodes[], depth, visitor_callback) -> traverses using batch_get_neighbors + prefetch hints- metrics() -> hot lists, cache hit rates, bytes_read

Concurrency & performance- Read-only mmapped files: no locks needed for file access. Thread-local decompression avoids contention.- Limit shared mutable state to LRU cache protected by lock-free structures or sharded caches.- Use IO sharding: multiple files allow serving many concurrent workers without single-file bottleneck.- Exploit NUMA-awareness: mmap and access affinity to worker’s NUMA node, or replicate index in RAM if needed.

Trade-offs- Elias-Fano gives best random-access compression for sorted large lists (fast rank/select) but adds decoding complexity. Varint is simpler with lower CPU but worse size.- Block size: smaller blocks reduce wasted decompression and tail latency for small neighbor queries; larger blocks get better compression ratios and fewer syscalls.- Caching decompressed blocks increases memory use but reduces CPU overhead for hot nodes.

Edge cases & extras- Support node/edge attributes by adding parallel attribute blob with same index layout.- Provide versioned files and atomic swap for deployment.- Validate with benchmarks: measure decode time / cold/hot latency, tune block size and codec mix for target latency (aim sub-ms decode + <1ms fetch in warm cache).

Why this works for an ML engineer- Compact on-disk reduces memory pressure while mmapping + zero-copy leverages OS caching for many concurrent readers. Mixed-codec and block design balance compression vs decode latency—critical for low-latency ML online inference and multi-hop candidate expansion.

EasyTechnical

70 practiced

Write a Python function to detect a cycle in an undirected graph. Use either DFS with parent tracking or Union-Find. Explain why the parent check is necessary in DFS-based detection. Graph is given as adjacency list; V up to 2*10^5.

Sample Answer

To detect a cycle in an undirected graph (adjacency list), two common approaches are DFS with parent tracking or Union-Find. I'll give a concise DFS implementation (O(V+E) time, O(V) stack/visited), explain the parent check, and outline a Union-Find alternative.

python

def has_cycle_dfs(adj):
    """
    adj: dict or list-of-lists adjacency list for undirected graph
    returns: True if there's any cycle, False otherwise
    """
    n = len(adj)
    visited = [False] * n

    def dfs(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                # visited neighbor that's not the parent -> cycle
                return True
        return False

    for i in range(n):
        if not visited[i]:
            if dfs(i, -1):
                return True
    return False

Why the parent check is necessary:- In an undirected graph each edge appears twice (u->v and v->u). During DFS from u to v, v will see u as a visited neighbor — but that's the edge we came from, not a cycle. Checking v != parent distinguishes the trivial back-edge to parent from a genuine cross/back-edge that indicates a cycle.

Union-Find alternative:- Use union-by-rank + path compression; for each undirected edge (u,v) if find(u)==find(v) -> cycle; else union(u,v). Also O(α(n)) per operation, overall O(E α(V)).

Edge cases:- Disconnected graph: iterate all components (handled).- Self-loop: treated as cycle (edge u->u).- Large graphs: iterative DFS or increase recursion limit if recursion depth could reach ~2e5.

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.