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.
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.
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).