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

69 practiced

Implement Depth-First Search (DFS) iteratively and recursively in Python. Provide two functions: dfs_recursive(graph, start, visited=set()) and dfs_iterative(graph, start). Each should return a list of nodes in the order they are first visited. Discuss time and space complexity and stack-depth considerations for large graphs (V up to 10^5).

MediumTechnical

58 practiced

Implement Union-Find (Disjoint Set Union) with path compression and union by rank in Python. Provide methods: find(x), union(x,y), connected(x,y). Use it to answer k connectivity queries on an undirected graph given as a list of edges and queries. Aim for near-constant amortized time per operation.

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.

HardTechnical

62 practiced

Propose efficient memory layout and traversal strategies for training GNNs on GPUs where neighbor sampling and message passing are the bottlenecks. Discuss edge lists vs CSR vs tiled/blocked layouts, prefetching, and how to batch multiple subgraphs to maximize GPU occupancy.

MediumTechnical

98 practiced

Compare common graph sampling strategies used during GNN training: uniform neighbor sampling, importance sampling, random walks (DeepWalk/Node2Vec), and layer-wise sampling (GraphSAGE). For each, describe when it is appropriate, memory/compute trade-offs, and impact on downstream model generalization.

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.