Full Circle

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3
Asked in
Sigmoid

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.

Follow the chain long enough and it might loop back.

Example 1

Input:

next_indices = [1,2,0]

Output:

0

Example 2

Input:

next_indices = [3,2,1,1]

Output:

1

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.

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

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.

Common follow-up questions