Design circular sliding-window ratio tracker
Problem Description
You are given a circular binary array A of length n, where each element A[i] is either 0 or 1. You are also given a fixed window size w, such that 1 ≤ w ≤ n.
Define r(i) as the fraction of 1s within the length-w window starting at index i. This window wraps around the array as needed (i.e., it's a circular window).
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. After every move, you must output
rwithO(1)time complexity per step. - (B) Step-by-k moves: Each query provides an integer
k ≥ 0. The cursor jumps forward bykpositions. After each jump, you must outputrwithO(1)time complexity per query, following any preprocessing you choose.
For both parts, describe your data structures, how you handle circularity, any preprocessing steps (if applicable), and provide proofs for the time and space complexities of your solutions.
AI interview prep
Core dilemma
Balancing the need for O(1) update/query time for a sliding window in a circular array, considering both single-step and arbitrary-step movements, which often requires different data structures and preprocessing strategies.
2 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design circular sliding-window ratio tracker
Problem Description
You are given a circular binary array A of length n, where each element A[i] is either 0 or 1. You are also given a fixed window size w, such that 1 ≤ w ≤ n.
Define r(i) as the fraction of 1s within the length-w window starting at index i. This window wraps around the array as needed (i.e., it's a circular window).
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. After every move, you must output
rwithO(1)time complexity per step. - (B) Step-by-k moves: Each query provides an integer
k ≥ 0. The cursor jumps forward bykpositions. After each jump, you must outputrwithO(1)time complexity per query, following any preprocessing you choose.
For both parts, describe your data structures, how you handle circularity, any preprocessing steps (if applicable), and provide proofs for the time and space complexities of your solutions.