Scene 13 of Graph Traversals in Core Technical Interview Questions for Software Engineers
By Amin Ariana — November 2008
You have a directed connected graph. Write an algorithm that detects any cycle, if one exists, and returns a list of its nodes.
Problem Statement
You have a directed connected graph. Write an algorithm that detects any cycle, if one exists, and returns a list of its nodes.
Evaluation
- Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution, O (n), offered? (25%)
Solution
Hint: Hash tables and Dirty bits are both acceptable solutions as long as you qualify the ugliness of your answer and suggest that a better answer exists.
References
A senior developer at Amazon asked me this question during an interview