Coding questions · Amazon
Detect cycles in lists and graphs
This question evaluates understanding of cycle detection in linked lists and directed graphs, assessing competencies in pointer manipulation, graph traversal strategies, and reasoning about algorithmic time and space complexity within the Coding & Algorithms domain.
Given a singly linked list, determine whether it contains a cycle. Implement an O(1)-space algorithm and explain the intuition and correctness. Follow-up: Generalize to a directed graph where each node may have multiple children. Given a starting node, determine whether a cycle exists reachable from it. Discuss how you'd handle disconnected graphs, very large graphs that may not fit in memory, and the time/space complexity trade-offs. Provide pseudocode or code for both parts.
Detect Cycle In A Linked List
The linked list is represented by next_indices, where -1 means null. Return whether the list reachable from head contains a cycle.
Examples
Example 1
Input: ([1,2,3,1], 0)
Output: True
Explanation: The list cycles back to index 1.
Example 2
Input: ([1,2,-1], 0)
Output: False
Explanation: The list terminates.
Hints
- Use Floyd slow and fast pointers.
- Treat -1 as the end of the list.
Detect Reachable Cycle In A Directed Graph
Return whether any directed cycle is reachable from the start node.
Examples
Example 1
Input: {0:[1],1:[2],2:[0]}, 0
Output: True
Explanation: A directed cycle is reachable from start.
Example 2
Input: ({"a":["b","c"],"b":[],"c":[]}, "a")
Output: False
Explanation: A DAG has no cycle.
Hints
- Use DFS colors: visiting means on the recursion stack.
- Only nodes reachable from start need to be explored.