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 pseudocode 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

Circular Linked List Detection
A linked list is given. Write an algorithm that detects whether it's a singly linked list or a circularly linked list.

Calculate your Social Graph Klout Score
Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.

Find the middle node of a Linked List
Given a Singly Linked List, write an algorithm to find the middle node. You may not use more than one loop of any kind.

Tree InOrder Traversal to Next Node
Given a node in a binary tree, implement the algorithm for finding its next inorder node in the containing tree.
 Author
 Amin Ariana
 Published
 November 2008