Graphs and Graph Algorithms Questions

Graph representations (adjacency list and adjacency matrix) and the traversal algorithms applied to general, non-tree structures: BFS, DFS, topological sort (Kahn's algorithm and DFS-based), shortest paths (Dijkstra, Bellman-Ford, A*), minimum spanning trees, cycle detection, connected components, and union-find. Covers modeling a problem as a graph even when the underlying data is not obviously graph-shaped, such as state-space search, an implicit graph over strings or grid cells (for example Word Ladder), or a task-dependency graph, and implementing these traversals with a hash map or hash set as the storage vehicle (adjacency map, visited set, memoization table), not the subject being tested. The graded skill is traversal, ordering, connectivity, or shortest-path reasoning over nodes and edges. This topic does not own: traversal, reconstruction, or serialization of a single-rooted binary tree (preorder, inorder, postorder, or level-order implementation, rebuilding a tree from traversal arrays, lowest common ancestor, binary search tree validation), which belongs to binary trees and binary search trees even though a tree is technically a graph; hash table internals such as hash function design, collision resolution, and load factor and resizing, which belong to hashing and hash tables; and deriving or comparing algorithmic complexity across graph algorithms without implementing them, such as comparing the time complexity of BFS, DFS, Dijkstra, and A*, which belongs to time and space complexity analysis. One of the highest-signal areas in senior coding interviews.

EasyTechnical
23 practiced

Explain the Bellman-Ford algorithm and how it detects negative-weight cycles. Discuss the algorithm's complexity and scenarios where Bellman-Ford is preferred over Dijkstra in ML systems or feature computations.

EasyTechnical
23 practiced

Explain cycle detection in directed graphs using DFS with node color states (white/gray/black). Describe how back edges are identified and why this method reliably detects cycles even in complex pipeline dependency graphs. Also explain how you would return the actual nodes involved in the detected cycle.

EasyTechnical
26 practiced

Implement breadth-first search (BFS) in Python to find the shortest path between two nodes in an unweighted graph. Function signature: def shortest_path(adj: Dict[int, List[int]], start: int, target: int) -> List[int]. Return the list of nodes forming the shortest path from start to target inclusive, or an empty list if no path exists. The adjacency input is an adjacency list mapping node ids to neighbor lists. Aim for O(V+E) time and O(V) memory.

MediumTechnical
39 practiced

Implement BFS on an implicit graph (state space) where each state's neighbors are generated by a function produce_neighbors(state). Write find_shortest_sequence(start, goal, produce_neighbors) in Python to return the shortest move sequence. Discuss pruning strategies, heuristics, and how to guarantee shortest path (when allowed to prune). Suggest bidirectional search when applicable.

HardTechnical
23 practiced

Write Python code to find all articulation points (cut vertices) and bridges (cut edges) in an undirected network graph represented as adjacency list Dict[int, List[int]]. Use a DFS lowlink algorithm and explain how articulation points and bridges indicate single points of failure in a network topology.

Unlock Full Question Bank

Get access to all Graphs and Graph Algorithms interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.