Graph Cycle Detection

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

Recommended reading

Author
Amin Ariana
Published
November 2008