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.

MediumTechnical

53 practiced

Design a data model and Cypher-like query for friend-of-friend (FoF) suggestions in a social network using a graph database (e.g., Neo4j). Describe node and relationship types, indexes you would create, and an efficient query to return top-k suggestions for user U prioritized by number of mutual friends and recency of interaction. Discuss limitations at very large scale and caching strategies.

Sample Answer

Node & relationship model- Nodes: - User {userId: string, name, joinDate, ...}- Relationships: - (u)-[:FRIEND {since: datetime}]->(v) // undirected modeled as two directed or single undirected - (u)-[:INTERACTED {timestamp: datetime, type: 'message|like|comment', weight: 1.0}]->(v) - (optional) (u)-[:BLOCK]->(v)

Indexes & constraints- CREATE CONSTRAINT ON (u:User) ASSERT u.userId IS UNIQUE;- CREATE INDEX ON :User(userId);- Optional indexes on interaction timestamp if you model Interaction as node: INDEX ON :Interaction(timestamp). Usually INTERACTED is rel property so rely on relationship scans limited by traversal.

Efficient Cypher-like FoF query (prioritize mutual friends count and recency)Parameters: $userId, $k, $w_mutual=1.0, $w_recency=0.5

cypher

MATCH (me:User {userId:$userId})-[:FRIEND]->(friend)-[:FRIEND]->(cand:User)
WHERE NOT (me)-[:FRIEND]->(cand) AND cand.userId <> $userId
WITH cand, count(DISTINCT friend) AS mutualCount

// get most recent interaction between me and candidate (could be null)
OPTIONAL MATCH (me)-[r:INTERACTED]-(cand)
WITH cand, mutualCount, max(r.timestamp) AS lastInteraction

// normalize recency into score: newer => higher. Use epoch ms for numeric ops.
WITH cand, mutualCount,
     CASE WHEN lastInteraction IS NULL THEN 0
          ELSE duration.inSeconds(lastInteraction, datetime()).seconds END AS secondsSinceInteraction

WITH cand, mutualCount,
     // convert to recencyScore in [0,1]: recent->1, older->~0 (tunable decay)
     apoc.math.exp(-secondsSinceInteraction / (60*60*24*30.0)) AS recencyScore

WITH cand, mutualCount, recencyScore,
     (mutualCount * $w_mutual) + (recencyScore * $w_recency) AS score
RETURN cand.userId AS userId, cand.name AS name, mutualCount, recencyScore, score
ORDER BY score DESC, mutualCount DESC, lastInteraction DESC
LIMIT $k

Reasoning and key points- Mutual friends provide social proof; recency captures active ties and shared recent activity.- Use COUNT DISTINCT to avoid double-counting via multiple paths.- Recency normalized via exponential decay avoids dominance of one factor; weights tunable.- Use OPTIONAL MATCH so candidates without interactions still considered.

Performance & scaling considerations- FoF traversal is local but can explode for high-degree hubs (celebrity nodes). Strategies: - Cap traversal depth/degree: only sample top-N friends per user (ORDER BY recent interaction LIMIT m). - Precompute mutual counts periodically with batch jobs (offline materialized suggestions table). - Use Graph Data Science or dedicated algorithms (NodeSimilarity, node2vec) for embeddings and approximate top-k. - For very large user base, maintain candidate pipelines (friends-of-friends, people-you-may-know) in a denormalized store.

Caching strategies- Serve suggestions from a cache (Redis) with TTL (e.g., 5–60 minutes) and single-user invalidation on friend-add/remove.- Use incremental updates: when FRIEND or INTERACTED event occurs, update cached ranking for affected users (push model).- Hybrid: online small query to refine cached candidates (cache top 200 candidates; compute final top-k fresh).- Precompute weekly/real-time with streaming (Kafka) + workers to keep suggestion cache fresh and eventually consistent.

Limitations- Real-time strict freshness vs cost trade-off: perfect freshness is expensive.- High-degree nodes produce many candidates—need sampling or heuristics to avoid noisy recommendations.- Cypher-based live queries may be slow for hotspots; prefer precompute + caching or GDS algorithms for heavy traffic.

Edge cases- Avoid recommending blocked users, existing friends, or very new accounts (cold start). Adjust weights for privacy settings.

MediumTechnical

74 practiced

Implement the A* search algorithm in Python for pathfinding on a 4-direction grid. Input: 2D grid where 0=free, 1=obstacle, start (sx,sy) and goal (gx,gy). Use Manhattan distance as the heuristic. Return a list of coordinates representing the found path or an empty list if unreachable. Ensure proper g and f score maintenance and path reconstruction.

Sample Answer

Approach: Use A* with open set as a min-heap keyed by f = g + h (Manhattan). Track g-score (cost from start), came_from for path reconstruction, and a closed set. Neighbors are 4-directional, valid if inside grid and not obstacle.

python

import heapq

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    sx, sy = start; gx, gy = goal

    def h(x, y):
        return abs(x - gx) + abs(y - gy)

    def neighbors(x, y):
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx, ny = x+dx, y+dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
                yield nx, ny

    open_heap = []
    g = { (sx, sy): 0 }
    f = { (sx, sy): h(sx, sy) }
    heapq.heappush(open_heap, (f[(sx, sy)], sx, sy))
    came_from = {}
    closed = set()

    while open_heap:
        _, x, y = heapq.heappop(open_heap)
        if (x, y) == (gx, gy):
            # reconstruct path
            path = [(gx, gy)]
            while path[-1] != (sx, sy):
                path.append(came_from[path[-1]])
            return path[::-1]
        if (x, y) in closed:
            continue
        closed.add((x, y))

        for nx, ny in neighbors(x, y):
            tentative_g = g[(x, y)] + 1
            if (nx, ny) in closed and tentative_g >= g.get((nx, ny), float('inf')):
                continue
            if tentative_g < g.get((nx, ny), float('inf')):
                came_from[(nx, ny)] = (x, y)
                g[(nx, ny)] = tentative_g
                fscore = tentative_g + h(nx, ny)
                f[(nx, ny)] = fscore
                heapq.heappush(open_heap, (fscore, nx, ny))
    return []

Key points:- Manhattan heuristic is admissible for 4-direction movement.- g stores best-known costs; f stored for heap priority.- closed set prevents re-expansion; we still allow updating a node if a better g is found before it's closed.Time: O(rows*cols*log(rows*cols)) worst-case. Space: O(rows*cols).Edge cases: start==goal, start/goal on obstacle, empty grid. Alternative: use a priority queue with tie-breakers or a monotone open-set to reduce pushes.

EasyTechnical

69 practiced

Compare use-cases for BFS and DFS. For each algorithm, list typical problems where it is the preferred approach (e.g., unweighted shortest path, cycle detection), memory usage characteristics, and scenarios where one performs better than the other (e.g., very deep vs very wide graphs). Provide practical rules-of-thumb for choosing between BFS, DFS, and bidirectional search.

HardTechnical

55 practiced

Describe Yen's algorithm for computing the K shortest simple paths between a source s and target t in a weighted directed graph (no negative cycles). Outline how to use Dijkstra as a subroutine, how to generate spur paths by temporarily removing edges and nodes, how to manage the candidate heap, and analyze the time complexity and practical tradeoffs.

Sample Answer

To compute the K shortest simple (loopless) paths from s to t, Yen’s algorithm enumerates paths in nondecreasing length using Dijkstra as a subroutine and generating “spur” alternatives by temporarily removing edges/nodes to avoid previously found paths.

Approach summary:1. Use Dijkstra to find the shortest path P0 from s to t; push it into result list A.2. Maintain a min-heap B of candidate paths (keyed by total path cost).3. For the i-th path Pi in A, generate alternatives by iterating each node (called spur node) along Pi from the root: - Root path = nodes from s to spur node. - For each previous path Pj in A that shares the same root path, temporarily remove the next edge after the spur node from the graph (to avoid rediscovering Pj). - Also temporarily remove all nodes in root path except spur node (to prevent cycles back into root). - Run Dijkstra from spur node to t in the modified graph to get spur path; combine with root to form total candidate. - Restore removed edges/nodes. - Insert unique candidates into B.4. Pop the smallest-cost candidate from B, append to A as the next shortest path; repeat until K paths found or B empty.

Python-like outline (simplified):

python

import heapq
def yen_k_shortest_paths(graph, s, t, K):
    A = []
    B = []
    P0 = dijkstra_path(graph, s, t)
    if not P0: return A
    A.append(P0)
    for k in range(1, K):
        for i in range(len(A[-1])):  # actually iterate nodes of A[k-1] when generating for kth
            root = A[k-1][:i+1]
            removed_edges, removed_nodes = [], set()
            # remove edges that would recreate previous paths with same root
            for p in A:
                if p[:i+1] == root and len(p) > i+1:
                    removed_edges.append((p[i], p[i+1]))
                    graph.remove_edge(*removed_edges[-1])
            # remove root nodes except spur node
            for node in root[:-1]:
                removed_nodes.add(node)
                graph.remove_node(node)
            spur = dijkstra_path(graph, root[-1], t)
            if spur:
                candidate = root[:-1] + spur
                cost = path_cost(candidate)
                heapq.heappush(B, (cost, candidate))
            # restore graph edges/nodes
            restore(removed_edges, removed_nodes)
        if not B: break
        _, next_path = heapq.heappop(B)
        if next_path not in A:
            A.append(next_path)
    return A

Key concepts:- Dijkstra provides shortest spur paths in O(E + V log V) with a binary heap.- Removing edges/nodes enforces uniqueness and loopless property.- Candidate heap B ensures global ordering among alternatives.

Complexity:- Worst-case time: O(K * N * (Dijkstra-cost)) where N is average path length (number of spur positions). More precisely O(K * V * (E + V log V)). In dense graphs this is heavy.- Space: O(K * path_length) for storing A and B.

Practical tradeoffs:- Running Dijkstra from many spur nodes is expensive; pruning identical roots reduces candidates.- Use faster priority queues (Fibonacci heap) to reduce Dijkstra to O(E + V log V) amortized; in practice binary heap is fine.- For very large K or graphs, consider Eppstein’s algorithm (better asymptotic) or k-shortest walks allowing cycles.- Cache shortest-path trees or reuse previous Dijkstra results where feasible.- Beware of memory blowup in B; deduplicate candidates with a hash set.

Edge cases:- No path exists (return empty).- Graph changes while algorithm runs (work on a copy).- Multiple equal-cost paths: tie-breaking by path lexicographic order if needed.

MediumTechnical

58 practiced

Explain Kosaraju's algorithm to compute strongly connected components (SCCs) in a directed graph. Provide an outline for implementation: first pass to compute finishing times, transpose graph, second pass to collect SCCs. Discuss time/space complexity, memory layout considerations (storing reverse adjacency), and how to handle very large graphs in memory-constrained environments.

Sample Answer

Kosaraju finds all strongly connected components (SCCs) in two DFS passes: first to record finishing order, second on the transposed graph to collect components.

Approach:1. First pass: run DFS on each unvisited node, push nodes onto a stack (or list) when finished — this records decreasing finishing times.2. Transpose graph: reverse every edge (build reverse adjacency).3. Second pass: pop nodes from stack; for each unvisited node, run DFS on transposed graph and collect all reachable nodes as one SCC.

Implementation outline (Python-like):

python

def kosaraju(adj):
    n = len(adj)
    visited = [False]*n
    order = []

    def dfs1(u):
        visited[u]=True
        for v in adj[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)   # finishing time

    for u in range(n):
        if not visited[u]:
            dfs1(u)

    # build transpose
    rev = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            rev[v].append(u)

    visited = [False]*n
    sccs = []
    def dfs2(u, comp):
        visited[u]=True
        comp.append(u)
        for v in rev[u]:
            if not visited[v]:
                dfs2(v, comp)

    while order:
        u = order.pop()
        if not visited[u]:
            comp=[]
            dfs2(u, comp)
            sccs.append(comp)
    return sccs

Key points:- Time: O(V+E) — each edge/node visited constant times.- Space: O(V+E) for adjacency + recursion stack (depth up to V). Using iterative DFS avoids recursion limits.- Memory/layout: store adjacency as contiguous arrays (CSR/edge lists) for cache efficiency; reverse adjacency can be expensive — consider building CSR for reverse using counts to allocate arrays in one pass.- Large-graph strategies: stream edges from disk, use external-memory algorithms, or avoid storing both adj and rev by: - Using an on-disk transpose or regenerating edges on the fly (if input is edge list, scan to produce reverse neighbors when needed), - Partitioning graph and processing SCCs via algorithms like Tarjan (single pass, lower memory but still needs adjacency) or external-memory SCC algorithms (e.g., Kosaraju variants with edge streaming or distributed frameworks like GraphX).- Practical tips: prefer iterative DFS, reserve buffers, and compress node IDs if sparse.

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.