Depth-First Search (DFS): Interview Questions and Practice Problems

A Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Above graph shows order in which the nodes are discovered in DFS. Here’re the list of commonly asked interview questions that can be solved using DFS –

1. Depth First Search (DFS) | Iterative & Recursive Implementation
2. Generate list of possible words from a character matrix
3. Find length of longest path in the matrix with consecutive characters
4. Replace all occurrences of 0 that are completely surrounded by 1 in a binary matrix
5. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
6. Find all occurrences of given string in a character matrix
7. Find path from source to destination in a matrix that satisfies given constraints
8. Flood Fill Algorithm
9. Traverse given directory using BFS and DFS in Java
10. Types of edges involved in DFS and relation between them
11. Arrival and Departure Time of Vertices in DFS
12. Find longest path in a Directed Acyclic Graph (DAG)
13. Find the path between given vertices in a directed graph
14. Determine if a graph is Bipartite Graph using DFS
15. Check if Graph is Strongly Connected or not using one DFS Traversal
16. Find Cost of Shortest Path in DAG using one pass of Bellman-Ford
17. Check if given Graph is Strongly Connected or not
18. Check if given digraph is a DAG (Directed Acyclic Graph) or not
19. 2-Vertex Connectivity in the graph
20. 2-Edge Connectivity in a Graph
21. Determine if an undirected graph is a Tree (Acyclic Connected Graph)
22. Check if an undirected graph contains cycle or not
23. Transitive Closure of a Graph
24. Topological Sort Algorithm for DAG using DFS
25. Find correct order of alphabets in a given dictionary of ancient origin
26. Find first k maximum occurring words in given set of strings
27. Find maximum occurring word in given set of strings
28. Lexicographic sorting of given set of keys
29. Construct a directed graph from undirected graph that satisfies given constraints
30. Inorder Tree Traversal | Iterative & Recursive
31. Preorder Tree Traversal | Iterative & Recursive
32. Postorder Tree Traversal | Iterative & Recursive

Thank you.