Implement Kac Ring Simulation with O(1) Step Query
Implement a Kac Ring data structure consisting of a circular ring of N positions, each with a color (0 or 1, or equivalently White/Black) and optional markers. When the simulation advances one step, each ball/position moves clockwise, and any position leaving a marked spot flips its color. Implement two methods: step() to advance the simulation by one step, and kstep(k) to advance by k steps, each returning the color ratio (number of 1s / N, or equivalently (W - B) / N) after the operation. Optimize from a brute-force O(N) per step approach to an O(1) per query solution using prefix sums or similar techniques.
Asked at:
Voleon
The Voleon Group
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late March, 2026
The Voleon Group
Senior
Problem: • Npositions on a circular ring (O.N-1), each with a color (0 or 1) and a marker (some positions have markers). • Rule: When the cursor steps clockwise by 1, every position with a marker flips its color. • Part 1: After a single step, compute the ratio of 1s in the ring. (Brute force O(N) accepted.) • Part 2: After stepping k positions, compute the ratio in O(1) per query using prefix sums.
Mid February, 2026
Voleon
Staff
A Kac ring is a fictional (as far as i can tell) data structure modeled like a circular queue. There are N points, each occupied by a white or black ball, and M of these points are marked. Each "step", balls move one position clockwise, and if a ball leaves a marked point, it changes color. Provide two functionalities: 1) step() method to advance the model by one step and return the ratio (W - B) / N, where W is the number of white balls and B is the number of black balls, with a complexity of O(1) 2) kstep(k) method to advance the model by k steps, with a complexity of O(1). The initializer should accept N and a sorted list of marked points, with all points starting as white.
Hello Interview Premium
Your account is free and you can post anonymously if you choose.