Bloomberg LP Interview Question
Financial Software DevelopersUse a linked list for the graph. Check for the next value for each node of the list. if it points to existing value, then there is a loop.
Or, do hare and tortoise rule:
use two pointers, one moves one node at a time,
other moves two nodes at a time, if they happen to show the same value, and next pointer, then there is a cycle..
Source: hxxp://en.wikipedia.org/wiki/Cycle_detection#Time-space_tradeoffs
If you apply dfs on graph if you visited a veter 'v' which is alreday visited already...there is a cycle
- Anonymous October 24, 2010