Katkat
Back

Implement Kac ring with O(1) color and kstep

VoleonSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of algorithmic state representation, modular arithmetic, and efficient update/query design by requiring a Kac ring implementation that supports constant-time k-step advancement and O(1) aggregate color reporting.

You are implementing a Kac ring dynamical system.

Model

  • There are N positions arranged in a circle, indexed clockwise: 0, 1, ..., N-1.
  • Each position holds exactly one ball, whose color is either white or black.
  • A subset of positions is marked.
  • Initially (time t = 0), all balls are white.

One time step

At each step:

  1. Every ball moves one position clockwise: a ball at position i moves to position (i + 1) mod N.
  2. If a ball leaves a marked position (i.e., it was at a marked index before moving), it flips color (white ↔ black) as it moves.

Task

Implement a class/data structure with the following interface:

Initialization

KacRing(N, marked)

  • N: number of positions.
  • marked: a sorted list of distinct marked indices 0 <= y1 < ... < ym < N.

Methods

  1. step()
  • Advances the system by exactly 1 time step.
  1. kstep(k)
  • Advances the system by k time steps.
  • Must run in O(1) time per call (i.e., it must not loop for k steps).
  1. color()
  • Returns the value:

[ \frac{W - B}{N} ]

where W is the current number of white balls and B is the current number of black balls.

  • Must run in O(1) time.

Notes / Constraints

  • Assume 1 <= N.
  • 0 <= len(marked) <= N.
  • k can be very large (e.g., up to 10^18), so kstep cannot simulate step-by-step.
  • You do not need to expose individual ball colors; only the required methods above.