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.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early August, 2026
Late March, 2026
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
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.