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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Voleon Group.

What role is this question designed for?

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

Design circular sliding-window ratio tracker | Voleon Group Coding Question

Design circular sliding-window ratio tracker

Company: Voleon Group

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a circular binary array A of length n (A[i] ∈ {0,1}) and a fixed window size w (1 ≤ w ≤ n). Define r (i) as the fraction of 1s within the length-w window starting at index i (wrapping around the ring as needed). Design algorithms to report r after a sequence of cursor moves: (A) Step-by-1 moves: the cursor advances by exactly one index each time; output r after every move with O( 1) time per step. (B) Step-by-k moves: each query provides an integer k ≥ 0; the cursor jumps forward by k positions; output r after each jump in O( 1) time per query following any preprocessing you choose. Describe your data structures, how you handle circularity, the preprocessing (if any), and prove time/space complexities.

Quick Answer: This question evaluates proficiency with sliding-window techniques, handling of circular arrays and modular indexing, design of constant-time update mechanisms, and rigorous algorithmic time/space complexity analysis.

Circular sliding-window ratio tracker — Part A (step-by-1, O(1) per step)

You are given a circular binary array `A` of length `n` (each `A[i]` is 0 or 1) and a fixed window size `w` (1 ≤ w ≤ n). For a cursor at index `i`, define `r(i)` as the fraction of 1s within the length-`w` window starting at index `i`, wrapping around the ring as needed. The cursor starts at index 0. You are given `num_steps` single-step moves; on each move the cursor advances by exactly one index (wrapping around). After each move, report `r` for the window starting at the new cursor position. Each step must run in O(1) time. Return a list of length `num_steps` whose j-th entry is the ratio after the (j+1)-th move. Approach: maintain a running count of 1s in the current window. Advancing the cursor by one removes the element that leaves the window (`A[cursor]`) and adds the element that enters it (`A[(cursor + w) % n]`), so each update is O(1). The ratio is `count / w`.

Constraints

1 <= w <= n
A[i] is in {0, 1}
0 <= num_steps
The array is circular: index arithmetic wraps modulo n.

Examples

Input: ([1,0,1,1,0], 3, 5)

Expected Output: [0.6666666666666666, 0.6666666666666666, 0.6666666666666666, 0.3333333333333333, 0.6666666666666666]

Explanation: Initial window [A0,A1,A2]=[1,0,1] count=2. Each step removes A[cursor] and adds A[(cursor+w)%5]; after 5 single steps the cursor wraps once around the 5-element ring.

Input: ([1,1,1,1], 2, 4)

Expected Output: [1.0, 1.0, 1.0, 1.0]

Explanation: All ones, so every length-2 window is fully ones; ratio is always 1.0.

Input: ([0,0,0,0,0], 3, 2)

Expected Output: [0.0, 0.0]

Explanation: No ones anywhere; every window ratio is 0.0.

Input: ([1,0], 1, 3)

Expected Output: [0.0, 1.0, 0.0]

Explanation: Window size 1 on a 2-element ring: cursor visits index 1 (A=0), index 0 (A=1), index 1 (A=0).

Input: ([1,0,1,1,0,1], 4, 0)

Expected Output: []

Explanation: Zero moves means no ratios are reported.

Input: ([1], 1, 2)

Expected Output: [1.0, 1.0]

Explanation: Single-element ring: the cursor always points at the only element (a 1), so the ratio is 1.0 each step.

Hints

You only need a running count of 1s in the current window — not a re-sum each step.
When the cursor advances by one, exactly one element leaves the window (A[cursor]) and exactly one enters (A[(cursor + w) % n]).
Initialize the count for the window starting at index 0 before processing any moves; the first reported ratio is after the first move.

Circular sliding-window ratio tracker — Part B (jump-by-k, O(1) per query)

Same setup as Part A: a circular binary array `A` of length `n` and a fixed window size `w` (1 ≤ w ≤ n). For a cursor at index `i`, `r(i)` is the fraction of 1s in the length-`w` window starting at index `i`, wrapping around the ring. The cursor starts at index 0. You are given a list of non-negative integers `jumps`. For each `k` in `jumps`, the cursor jumps forward by `k` positions (modulo `n`), and you must report `r` for the window starting at the new cursor position. Each query must run in O(1) time after any preprocessing you choose. Return a list, one ratio per jump. Approach: build prefix sums over the array logically doubled to `A + A`, so that the length-`w` window starting at any index `i` in `[0, n-1]` is the contiguous range `[i, i + w - 1]`, and `i + w - 1 < 2n`. Then the count of 1s is `P[i + w] - P[i]`, where `P` is the prefix-sum array of the doubled sequence. Preprocessing is O(n); each query is O(1). The cursor position after a jump is `(cursor + k) % n`.

Constraints

1 <= w <= n
A[i] is in {0, 1}
k >= 0 for every jump (k may exceed n; reduce modulo n)
The array is circular: window and cursor arithmetic wrap modulo n.

Examples

Input: ([1,0,1,1,0], 3, [1,2,0,4])

Expected Output: [0.6666666666666666, 0.6666666666666666, 0.6666666666666666, 0.6666666666666666]

Explanation: Cursor path: 0->1->3->3->2 (each (cursor+k)%5). Windows [1,2,3], [3,4,0], [3,4,0], [2,3,4] each contain exactly two 1s, so 2/3 each.

Input: ([1,1,1,1], 2, [0,1,2,3])

Expected Output: [1.0, 1.0, 1.0, 1.0]

Explanation: All ones; every length-2 window ratio is 1.0 regardless of cursor.

Input: ([0,0,0,0,0], 4, [3,7])

Expected Output: [0.0, 0.0]

Explanation: No ones; every window ratio is 0.0. k=7 wraps to 7%5=2.

Input: ([1,0], 1, [0,1,1,1])

Expected Output: [1.0, 0.0, 1.0, 0.0]

Explanation: Window size 1 on a 2-ring: cursor 0(A=1), 1(A=0), 0(A=1), 1(A=0).

Input: ([1,0,1,1,0,1], 6, [10])

Expected Output: [0.6666666666666666]

Explanation: Window equals the whole ring (w=n=6); the window covers all 6 elements with four 1s -> 4/6 = 2/3. k=10 wraps to 10%6=4 but the full-ring window is identical from any start.

Input: ([1,0,1,1,0], 3, [])

Expected Output: []

Explanation: No jumps means no ratios are reported.

Input: ([1], 1, [5,0,100])

Expected Output: [1.0, 1.0, 1.0]

Explanation: Single-element ring: any jump lands on the only element (a 1); ratio is 1.0 each query.

Hints

Conceptually double the array to A + A so a wrap-around window becomes a single contiguous range.
With prefix sums P over the doubled array, the count of 1s for the window at index i is P[i + w] - P[i].
A jump by k just moves the cursor to (cursor + k) % n; reduce k modulo n first so large k still costs O(1).

Quick Overview

This question evaluates proficiency with sliding-window techniques, handling of circular arrays and modular indexing, design of constant-time update mechanisms, and rigorous algorithmic time/space complexity analysis.