A Kac ring is a dynamical system defined as follows:
- there are N points x0,…,xN−1x_0, …, x_{N-1}x0,…,xN−1 arranged in a circle, numbered clockwise.
- each point is occupied by either a white ball or a black ball.
- in addition, M of these points are “marked.”
- at each step, balls are moved one step clockwise, i.e. x0→x1,x1→x2,…,xN−1→x0x_0 \to x_1, x_1 \to x_2, …, x_{N-1} \to x_0x0→x1,x1→x2,…,xN−1→x0.
- if a ball leaves a marked point, it changes color. For example, if at time ttt the ball at point xix_ixi is white and xix_ixi is marked, then at time t+1t+1t+1 the ball at xi+1x_{i+1}xi+1 is now black. If point xjx_jxj is not marked, then at t+1t+1t+1 the ball at xj+1x_{j+1}xj+1 keeps its color.
Part 1: Implement a Kac ring with the following interface:
- The initializer accepts N (number of points) and a sorted list of marked points 0≤y1<…<ym<N0 \le y_1 < … < y_m < N0≤y1<…<ym<N. All points start white.
step()advances the model one step.color()returns the ratio (W−B)/N(W – B) / N(W−B)/N, where W is the number of white balls and B is the number of black balls. This method should be O(1).
Brief summary: Simulate a circular system where balls move one step each tick and flip color only when leaving a marked slot. Build an object with step() and an O(1) color() that returns (white−black)/N(white – black)/N(white−black)/N. Focus on modular indexing and maintaining counts/deltas to keep queries constant time.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Voleon, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
