How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Voleon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Voleon during technical interviews.

Count White Balls After K Steps | Voleon Coding Question

Count White Balls After K Steps

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a ring of `N` positions indexed from `0` to `N-1`. - At each position `i`, there is initially one ball whose color is either white or black. - Each position may also contain a flip gate, represented by `gate[i]` where `1` means a gate is present and `0` means no gate. - In one synchronous step, every ball moves one position clockwise. - Whenever a ball crosses a position containing a flip gate, its color toggles. For each query, you are given an integer `K` and must determine how many balls are white after exactly `K` steps. Additional details: - A ball starting at index `i` will be located at `(i + K) mod N` after `K` steps. - Its final color depends only on whether it crosses an even or odd number of gates during those `K` moves. - `K` may be much larger than `N`, so simulating step by step is too slow. Design an algorithm that preprocesses the ring and answers each query efficiently, ideally in `O(1)` time per query after preprocessing.

Quick Answer: This question evaluates understanding of modular arithmetic, parity tracking, periodic behavior on circular data structures, and the design of efficient preprocessing for repeated queries.

You are given a ring of `N` positions indexed from `0` to `N-1`. Each position `i` starts with one ball whose color is white (`'W'`) or black (`'B'`), given by the string `colors`. Each position may contain a flip gate, given by the list `gates` where `gates[i] = 1` means a gate is present and `0` means no gate. In one synchronous step, every ball moves one position clockwise (a ball at index `p` moves to `(p + 1) mod N`). Whenever a ball moves onto a position that contains a flip gate, its color toggles (white becomes black and vice versa). You are also given a list `queries` of non-negative integers. For each value `K` in `queries`, determine how many balls are white after **exactly** `K` synchronous steps, starting fresh from the original configuration each time. Return a list of the answers, one per query, in order. A ball starting at index `i` ends at `(i + K) mod N` and crosses the positions `i+1, i+2, ..., i+K` (mod N) along the way; its final color depends only on the parity of how many of those crossings land on a gate. `K` may be far larger than `N`, so per-step simulation is too slow — preprocess the ring so each query is answered in `O(1)` time.

Constraints

0 <= N (ring size = len(colors) = len(gates))
colors[i] is 'W' or 'B'
gates[i] is 0 or 1
0 <= K, and K may be much larger than N
0 <= number of queries

Examples

Input: ("WBWB", [0, 1, 0, 0], [0, 1, 4])

Expected Output: [2, 1, 2]

Explanation: K=0: original WBWB has 2 whites. K=1: each ball steps once; gate sits at index 1 so only the ball that lands there toggles -> 1 white. K=4 is exactly one full lap (N=4): every ball crosses the single gate once and toggles, WBWB -> BWBW, still 2 whites.

Input: ("W", [1], [0, 1, 2, 3])

Expected Output: [1, 0, 1, 0]

Explanation: Single white ball on a 1-position ring whose only cell has a gate. Each step the ball re-enters the gated cell and toggles, so the white count alternates 1,0,1,0 with the parity of K.

Input: ("WWBB", [1, 0, 1, 0], [0, 2, 5, 8])

Expected Output: [2, 2, 2, 2]

Explanation: total_gates=2 (even), so every completed lap toggles each ball an even number of times -> net no change per lap. The remainder crossings rearrange colors but the white count stays 2 for all these K.

Input: ("W", [0], [0, 5])

Expected Output: [1, 1]

Explanation: No gates anywhere, so colors never change. The lone white ball stays white for any K.

Input: ("", [], [0, 3])

Expected Output: [0, 0]

Explanation: Empty ring (N=0): there are no balls, so the answer is 0 for every query regardless of K.

Input: ("WBWBW", [1, 1, 0, 1, 0], [7, 13, 100])

Expected Output: [2, 4, 3]

Explanation: N=5, total_gates=3 (odd). K=7 -> full=1,rem=2; K=13 -> full=2,rem=3; K=100 -> full=20,rem=0. Counting white = original-white XOR (full*3 + rem-window gates) odd, per ball, yields 2, 4, and 3 whites respectively (matches a step-by-step simulation).

Hints

A ball at index i ends at (i + K) mod N, but its final color depends only on the PARITY of how many gates it crosses, not on where it lands.
Split K into full laps and a remainder: K = full*N + rem. Every full lap crosses every gate exactly once, contributing full * (total gates) crossings to every ball.
For the remaining 'rem' steps a ball from index i crosses gates at positions i+1 .. i+rem. Use a prefix-sum array over the gates duplicated once to evaluate this wrap-around window in O(1).
Final color is white XOR (total crossings is odd). Sum that over all i to get the white count for each query.

Quick Overview

This question evaluates understanding of modular arithmetic, parity tracking, periodic behavior on circular data structures, and the design of efficient preprocessing for repeated queries.