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 Onsite rounds at Voleon.

What role is this question designed for?

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

Implement Kac ring with O(1) color and kstep

Q: Implement Kac ring with O(1) color and kstep

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.

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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. 2. `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). 3. `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.

Quick Answer: 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 simulating a Kac ring dynamical system. There are N positions in a circle, indexed 0 to N-1 clockwise. Each position holds one ball. A sorted list of distinct positions is marked. Initially, all balls are white. In one time step, every ball moves one position clockwise, and any ball that leaves a marked position flips color (white <-> black). In the original interview version, you would implement a class with methods step(), kstep(k), and color(). For judge compatibility, implement a function solution(N, marked, operations) that processes these method calls: - ('step',) means call step() - ('kstep', k) means call kstep(k) - ('color',) means call color() and record its result For each color query, return the exact value of (W - B) / N as a reduced string: - use '0' for zero - use an integer like '1' or '-1' if the denominator is 1 - otherwise use 'a/b' in lowest terms Because k can be extremely large, kstep(k) must not simulate k individual steps. Under the constraints below, an O(N^2) preprocessing step is acceptable, but each processed operation should be O(1).

Constraints

1 <= N <= 2000
0 <= len(marked) <= N
0 <= marked[i] < N
marked is sorted in strictly increasing order
1 <= len(operations) <= 200000
0 <= k <= 10^18
An O(N^2) preprocessing step is allowed; each operation afterward should be O(1)

Examples

Input: (5, [1, 3], [('color',), ('step',), ('color',), ('kstep', 3), ('color',), ('step',), ('color',)])

Expected Output: ['1', '1/5', '1/5', '1']

Explanation: For this ring, the color sequence over one period is [1, 1/5, -3/5, -3/5, 1/5]. The queried times are 0, 1, 4, and 0 again.

Input: (4, [], [('step',), ('kstep', 1000000000000000000), ('color',), ('step',), ('color',)])

Expected Output: ['1', '1']

Explanation: With no marked positions, no ball ever flips, so all balls remain white forever.

Input: (4, [0, 1, 2, 3], [('color',), ('step',), ('color',), ('kstep', 2), ('color',)])

Expected Output: ['1', '-1', '-1']

Explanation: If every position is marked, every ball flips at every step, so the entire system alternates between all white and all black.

Input: (4, [1], [('color',), ('kstep', 5), ('color',), ('step',), ('color',), ('kstep', 2), ('color',)])

Expected Output: ['1', '-1/2', '0', '1']

Explanation: With one marked position, the system has period 2N = 8. The queried times are 0, 5, 6, and 8, whose color values are 1, -1/2, 0, and 1.

Input: (1, [0], [('color',), ('step',), ('color',), ('kstep', 100), ('color',)])

Expected Output: ['1', '-1', '-1']

Explanation: There is only one ball and the only position is marked, so the ball flips every step. The colors alternate white, black, white, black, ...

Solution

def solution(N, marked, operations):
    from math import gcd

    is_marked = [0] * N
    for idx in marked:
        is_marked[idx] = 1

    # q[i] = (-1)^(number of marked positions among 0..i-1 in the doubled ring)
    q = [1] * (2 * N + 1)
    for i in range(2 * N):
        q[i + 1] = -q[i] if is_marked[i % N] else q[i]

    # magnetization[t] = W - B after t steps, for 0 <= t < N
    # A ball starting at i has sign q[i] * q[i+t]. Summing over all i gives W-B.
    magnetization = [0] * N
    for t in range(N):
        total = 0
        for i in range(N):
            total += q[i] * q[i + t]
        magnetization[t] = total

    def format_value(num):
        if num == 0:
            return '0'
        g = gcd(abs(num), N)
        num //= g
        den = N // g
        if den == 1:
            return str(num)
        return f'{num}/{den}'

    if len(marked) % 2 == 0:
        period = N
        values = [format_value(magnetization[t]) for t in range(N)]
    else:
        period = 2 * N
        values = [None] * period
        for t in range(N):
            values[t] = format_value(magnetization[t])
            values[t + N] = format_value(-magnetization[t])

    time = 0
    answer = []
    for op in operations:
        kind = op[0]
        if kind == 'step':
            time = (time + 1) % period
        elif kind == 'kstep':
            time = (time + op[1]) % period
        elif kind == 'color':
            answer.append(values[time])
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return answer

Time complexity: O(N^2 + Q), where Q is the number of operations. Space complexity: O(N).

Hints

After N steps, every ball has gone all the way around the ring once. What does that imply about the state, depending on whether the number of marked positions is even or odd?
For a fixed time t, a ball starting at position i flips once for each marked position in the cyclic window of length t starting at i. The total color value depends only on whether each such window contains an even or odd number of marked positions.

Quick Overview

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.