Find the Child Who Has the Ball After K Seconds

Find the Child Who Has the Ball After K Seconds

What is this problem about?

The Find the Child Who Has the Ball After K Seconds interview question is a cyclic simulation problem. $N$ children (indexed 0 to $n-1$) stand in a line. A ball starts at child 0 and moves to the right. When it reaches the end of the line (child $n-1$), it reverses direction and moves left. This continue until $k$ seconds have passed. You need to identify which child holds the ball at exactly $k$ seconds.

Why is this asked in interviews?

Meta and Google ask the Find the Child Who Has the Ball After K Seconds coding problem to test a candidate's ability to avoid brute-force simulation. While you could simulate $k$ steps, for very large $k$, this is inefficient. It evaluates your knowledge of Math interview patterns, specifically modulo arithmetic and periodic sequences.

Algorithmic pattern used

This problem uses Modulo Arithmetic based on the "Round Trip" period.

1. Period Calculation: The ball moves from $0 \dots n-1$ (taking $n-1$ steps) and then back from $n-1 \dots 0$ (another $n-1$ steps). The total length of one full cycle is $2 imes (n - 1)$.
2. Effective Time: Calculate k_eff = k % (2 * (n - 1)).
3. Position Logic:

• If k_eff < n, the ball is moving to the right. The position is k_eff.
• If k_eff >= n, the ball has reversed. The position is (2 * (n - 1)) - k_eff.

Example explanation

$n = 3, k = 5$.

1. Period: $2 imes (3 - 1) = 4$.
2. Effective time: $5 \% 4 = 1$.
3. Since $1 < 3$, child 1 has the ball. Let's check:

• 0 sec: child 0.
• 1 sec: child 1.
• 2 sec: child 2 (End of line, reverse).
• 3 sec: child 1.
• 4 sec: child 0 (End of line, reverse).
• 5 sec: child 1. Correct!

Common mistakes candidates make

• Brute Force Simulation: Simulating all $k$ steps, which works for small $k$ but is $O(K)$ instead of $O(1)$.
• Incorrect Period: Using $2n$ or $n$ as the cycle length instead of $2(n-1)$.
• Off-by-one: Mistakenly identifying the child when the ball is at the boundary.

Interview preparation tip

Always look for a "mathematical shortcut" in simulation problems involving repeated movements. If the movement is periodic, use the modulo operator to find the final state instantly. This is a core part of the Math interview pattern.