Depth-first search (DFS) Interview Questions and Practice Problems

Coding Freak
Sep 1, 2018 · 2 min read

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. Determine if a given graph is Bipartite Graph using DFS
  3. Topological Sorting in a DAG
  4. Transitive Closure of a Graph
  5. Check if an undirected graph contains cycle or not
  6. Determine if an undirected graph is a Tree (Acyclic Connected Graph)
  7. 2-Edge Connectivity in the graph
  8. Check if given digraph is a DAG (Directed Acyclic Graph) or not
  9. Check if given Graph is Strongly Connected or not
  10. Lexicographic sorting of given set of keys
  11. Find maximum occurring word in given set of strings
  12. Find first k maximum occurring words in given set of strings
  13. Find path from source to destination in a matrix that satisfies given constraints
  14. Find all occurrences of given string in a character matrix
  15. Flood Fill Algorithm
  16. Check if given Graph is Strongly Connected or not using one DFS Traversal
  17. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
  18. Check if Graph is Strongly Connected or not using one DFS Traversal
  19. Determine if a graph is Bipartite Graph using DFS
  20. Find Cost of Shortest Path in DAG using one pass of Bellman-Ford
  21. Traverse the given directory using BFS and DFS in Java

Thank you all being with us.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade