Katkat
Back

Design circular sliding-window ratio tracker

VoleonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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(
  2. 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.