Graph Cycle Detection

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