|
|
|
|
|
|
by varjag
2920 days ago
|
|
|
When people say they expect someone to implement cycle detection, they usually mean Floyd's algorithm. https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tort... If you come up with something else (like tagging nodes), you get a strike for inefficiency. It looks simple enough to feel smug about once you know it, at the same time there's near zero chance the interviewers could come up with this algorithm independently without prior knowledge. |
|
|
Not necessarily. Sometimes the dataset only has on the order of 10k nodes, and you just want to warn users if they create a cycle, or keep particular routines from going into an infinite loop.
If you come up with something else (like tagging nodes), you get a strike for inefficiency.
A few days ago, I implemented cycle detection in an event notification system where the graph size is relatively small in just 4 lines of code, which should be immediately understandable by any competent programmer. That you should mandate Floyd's algorithm in all cases gives you a strike for pedantic design without regard to cost/benefit.