How should I practice Find the Entry of a Linked List Cycle?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Qualys onsite interview problems in FastPrep.

Is Find the Entry of a Linked List Cycle associated with Qualys?

FastPrep tags this as a Qualys onsite interview coding practice problem when the problem catalog has that company and stage context.

Find the Entry of a Linked List Cycle

Qualys● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Find the entry node of the cycle reachable from a singly linked list's head. The entry is the first node that would be visited twice while following successor links from the head. Return -1 if no cycle is reachable.

For this exercise, links are encoded by an array next. Node IDs are its zero-based indices; next[i] is node i's successor ID, or -1 for no successor. The head is node 0 when the array is nonempty, and an empty array is an empty list. Ignore any nodes unreachable from the head.

Return the entry node's ID, rather than its position in the traversal. Aim for O(n) time and O(1) auxiliary space.

Function

findCycleEntry(next: int[]) → int

Examples

Example 1

next = [1,2,3,1]return = 1

The traversal 0 → 1 → 2 → 3 → 1 first repeats node 1, so that node is the cycle entry.

Example 2

next = [1,-1]return = -1

The traversal terminates after nodes 0 and 1, so there is no reachable cycle.

Constraints

For this exercise, assume 0 <= next.length <= 10^5.
Each entry is -1 or a valid ID smaller than next.length.