Find the Student that Will Replace the Chalk

Find the Student that Will Replace the Chalk

1. What is this problem about?

The Find the Student that Will Replace the Chalk interview question is a cyclic simulation problem. $N$ students sit in a circle, and each student $i$ needs chalk[i] pieces of chalk to solve a problem. You start with a total amount of k chalk. The teacher gives chalk to student 0, then 1, and so on, wrapping back to 0 after student $n-1$. You need to find the index of the student who will run out of chalk (i.e., when $k < ext{chalk required}$).

2. Why is this asked in interviews?

Companies like Google and Bloomberg ask the Find the Student that Will Replace the Chalk coding problem to test if a candidate can optimize a repeating process. While a simple simulation would take $O(k/n)$ passes, the correct approach uses Prefix Sums and Modulo to solve it in $O(N)$ or $O(N \log N)$. It evaluations your ability to handle large numeric inputs ($k$ up to $10^{15}$).

Algorithmic pattern used

This problem follows the Modulo and Binary Search pattern.

1. Total Consumption: Calculate the total amount of chalk needed for one full round: total = sum(chalk).
2. Reduction: Use the modulo operator to skip all completed rounds: k_remaining = k % total.
3. Find Student:
   • Option A: Iterate through the students, subtracting chalk[i] from k_remaining until it becomes negative.
   • Option B: Pre-calculate prefix sums of the chalk array and use Binary Search to find the first index where prefixSum[i] > k_remaining.

4. Example explanation

Chalk needed: [3, 4, 1, 2], total $k = 25$.

1. Total per round: $3 + 4 + 1 + 2 = 10$.
2. Full rounds: $25 / 10 = 2$.
3. Chalk remaining: $25 \% 10 = 5$.
4. Search for student:
   • Student 0: needs 3. $5 - 3 = 2$ left.
   • Student 1: needs 4. $2 < 4$. Student 1 runs out. Result: 1.

5. Common mistakes candidates make

• Integer Overflow: Forgetting that $k$ and the sum of chalk can exceed $2^{31}-1$. Always use 64-bit integers (long or BigInt).
• Linear Simulation: Trying to simulate every single subtraction, which is too slow for very large $k$.
• Off-by-one: Mistakes in checking whether the chalk runs out exactly at 0 or when it's strictly less than needed.

6. Interview preparation tip

Always look for "periodicity" in simulation problems. If an array is traversed repeatedly, the sum of the array is the "period," and the modulo operator is the "shortcut" to the final cycle. This is a vital Prefix Sum interview pattern.