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
24 practiced

Discuss how common graph algorithms should handle input edge cases: self-loops, parallel/multi-edges, isolated nodes, and nodes with multiple labels. For BFS/DFS, Dijkstra, union-find and topological sort, describe concrete pitfalls you might encounter in production and how to sanitize or validate input to make implementations robust.

MediumTechnical
25 practiced

Implement an iterative DFS in Python to check whether there exists a path between two nodes in a directed graph. Use early exit to improve performance, handle missing nodes gracefully, and discuss stack size and worst-case complexity.

MediumTechnical
25 practiced

Implement clone (deep copy) of an undirected graph given a reference to a node. The graph may contain cycles. Provide both BFS and DFS approaches and explain how you ensure node identity mapping and avoid infinite loops.

EasyTechnical
31 practiced

Explain the formal differences between a tree and a general graph. Describe properties that define a tree (connected, acyclic, exactly n-1 edges for n nodes), implications such as unique simple path between nodes, and how those properties simplify algorithms (e.g., no need for visited set in some traversals). Give concrete examples of when you'd model a problem as a tree versus as a general graph.

HardTechnical
21 practiced

Write functions in C++ to convert between adjacency matrix and adjacency list representations for a graph with n nodes labeled 0..n-1. Consider both directed and undirected graphs and explain the time and space complexity of each representation and of the conversion. Provide guidance on when to prefer one representation over the other.

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.