# Full Circle > Follow the chain long enough and it might loop back. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L3 ## Problem A forwarding table is stored as a flat array `next_indices`, where each slot holds the index it forwards to next, or -1 to mark the end of a chain. Starting from slot 0 and following the pointers, return the index of the first slot the walk reaches twice, or -1 if it ends first. A pointer of -1, or one that falls outside the array, ends the walk rather than closing a loop. ## Worked solution and explanation ### What this really is Strip the forwarding-table costume and this is cycle detection on a functional graph: every slot has exactly one outgoing edge, so following pointers is a single deterministic walk with no branching. The tempting shortcut is a step counter: walk, and if you outlast n steps you must be in a loop. That answers 'is there a loop', but this problem asks WHERE the loop closes, and a counter can never name the slot. You have to remember every slot you have stepped on, so the instant the walk lands on one twice you can hand back that index. Reach for the counter and you can prove a cycle exists but you cannot say which slot it enters. > **Trick to solving** > > The visited set pulls double duty. It both detects the revisit and tells you its exact index, and it bounds the walk to at most n steps. A scalar bound cannot do the first job at all, so the set is not an optimization here, it is what lets you answer the question that was actually asked. --- ### Walking the chain #### Step 1: Start at slot 0 The walk has one fixed entry point. You are not hunting for any cycle in the graph, only the loop reachable from slot 0. A loop sitting off to the side that 0 never reaches does not count, which is why you never iterate over starting points. #### Step 2: Validate before you dereference Three things end the walk: a -1, a pointer that lands outside 0 to n-1, and a slot already in your visited set. The first two mean the chain ran out, so the answer is -1. Only the third is a loop. Check the range in the loop guard before you dereference, or a -1 terminator becomes next_indices[-1] and you read the last element instead of halting. #### Step 3: Return the slot, not a boolean If you stopped because the current slot was already visited, that slot IS the entry to the loop, so return its index. If you stopped because the pointer terminated or went out of range, return -1. Tie the answer to the reason you stopped, not merely to the fact that you stopped. --- ### The solution **Visited-set traversal** ```python def find_loop_entry(next_indices): visited = set() idx = 0 n = len(next_indices) while idx != -1 and 0 <= idx < n: if idx in visited: return idx visited.add(idx) idx = next_indices[idx] return -1 ``` *Validate the index in the loop guard, so a -1 or out-of-range pointer ends the walk before it is ever used to index the array. The first slot found in the set is the loop entry.* > **Time and space** > > Time: O(n). Each reachable slot enters the set once, and the walk halts the instant it would repeat. Space: O(n) for the set in the worst case, a single long non-cyclic chain. At 100,000 slots this is one linear pass with no risk of the infinite loop a missing visited check would cause. **Visited set** O(n) time, O(n) space. One walk plus a hash set of seen slots. The moment the walk hits a slot in the set, that index is the loop entry, so you get the answer for free. Simplest to write and to reason about. **Floyd's two pointers** O(n) time, O(1) space. Floyd's tortoise and hare finds a meeting point inside the loop, then a second phase resets one pointer to slot 0 and advances both by one until they meet at the entry. Costs no memory, but it is a second algorithm on top, and you still replicate the -1 and out-of-range checks on the fast pointer at every hop. > **Interviewers watch for** > > Whether you notice that a step counter answers a different question. A candidate who reaches for 'count to n and declare a cycle' has solved existence, not location, and the tell of seniority is catching that the ask is the entry slot and that only remembered state, or Floyd's two phases, can produce it. > **Common pitfall** > > Dereferencing before validating. If you write idx = next_indices[idx] without first confirming idx is in range, the -1 terminator becomes next_indices[-1], which in Python silently reads the last element instead of ending the chain. Your entry index is then quietly wrong on exactly the inputs that should return -1. --- ## Common follow-up questions - Can you find the entry slot in O(1) extra space? _(Tests Floyd's two-phase cycle detection: find a meeting point, then walk one pointer from the start to locate the entry.)_ - How would you also report how many slots are on the loop? _(Tests continuing the walk from the entry to measure the loop length, or counting slots between two encounters of the entry.)_ - What if the chain can start from any slot, not just 0? _(Tests running detection from every unvisited starting slot, similar to connected components in a graph.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/full_circle) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.