Design circular sliding-window ratio tracker

Q: Design circular sliding-window ratio tracker

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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(

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

Design circular sliding-window ratio tracker

Overview

Comments (0)