Compute rolling standard deviation in O(n)
Company: DRW
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an array of numbers and a window size k, compute the rolling standard deviation for every contiguous window. Design an O(n) algorithm that updates statistics incrementally rather than recomputing each window from scratch. Use the variance identity by maintaining running sum and sum of squares (or adapt a one-pass method like Welford’s algorithm for a sliding window), discuss numerical stability, analyze time and space complexity, and handle edge cases (k ≤ 0, k > n, k = 1, NaNs). Implement and provide tests.
Quick Answer: This question evaluates understanding of streaming statistics, numerical stability, and incremental algorithm design for rolling variance and standard deviation while also testing handling of edge cases and special numeric values.