How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DRW.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at DRW during technical interviews.

Compute rolling standard deviation in O(n)

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute rolling standard deviation in O(n) states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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 interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute rolling standard deviation in O(n) states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an array of numbers `nums` and a window size `k`, compute the **sample** rolling standard deviation for every contiguous window of length `k`. Your algorithm must run in **O(n)** time by updating statistics incrementally as the window slides, rather than recomputing each window from scratch. Maintain a running sum `S` and running sum of squares `Q` over the current window. When the window slides by one element (dropping `out`, adding `in`): - `S += in - out` - `Q += in*in - out*out` The sample variance of a window is then `var = (Q - S*S/k) / (k - 1)`, and the standard deviation is `sqrt(var)` (clamp tiny negative values caused by floating-point error to 0). Return a list with one std value per window, in left-to-right order. There are `n - k + 1` windows. **Conventions / edge cases:** - If `k <= 0` or `k > n`, return an empty list. - If `k == 1`, the sample std of every single-element window is `0.0` (the `k-1` denominator is degenerate, so define it as 0 by convention). - Use the **sample** denominator `k - 1` (ddof = 1), not the population denominator `k` — interviewers at quant shops are picky about this. - Round each std to 6 decimal places.

Constraints

0 <= len(nums) <= 10^5
Window size k may be any integer; k <= 0 or k > len(nums) yields an empty result
Numbers fit in standard floating point; use the sample (k-1) denominator
Round each window's std to 6 decimal places

Examples

Input: ([1, 2, 3, 4, 5], 2)

Expected Output: [0.707107, 0.707107, 0.707107, 0.707107]

Explanation: Each 2-element window has values differing by 1; sample var = ((-0.5)^2+(0.5)^2)/1 = 0.5, std = sqrt(0.5) ≈ 0.707107.

Input: ([2, 4, 6, 8], 3)

Expected Output: [2.0, 2.0]

Explanation: Window [2,4,6]: mean 4, sample var = (4+0+4)/2 = 4, std = 2.0. Window [4,6,8] is identical by symmetry.

Input: ([5, 5, 5, 5], 2)

Expected Output: [0.0, 0.0, 0.0]

Explanation: Constant windows have zero spread, so every sample std is 0.0.

Input: ([10, 20, 30], 1)

Expected Output: [0.0, 0.0, 0.0]

Explanation: k=1: a single-element window has no spread; by convention the sample std is 0.0.

Input: ([1, 2, 3], 5)

Expected Output: []

Explanation: k > n, so there is no full window; return an empty list.

Input: ([1, 2, 3], 0)

Expected Output: []

Explanation: k <= 0 is invalid; return an empty list.

Input: ([], 2)

Expected Output: []

Explanation: Empty input with k > n (=0): no windows, return an empty list.

Input: ([-1, -2, -3, -4], 2)

Expected Output: [0.707107, 0.707107, 0.707107]

Explanation: Negative values behave like the positive case; consecutive pairs differ by 1, so std = sqrt(0.5) ≈ 0.707107 each.

Input: ([1, 3, 5, 7, 9, 11], 4)

Expected Output: [2.581989, 2.581989, 2.581989]

Explanation: Window [1,3,5,7]: mean 4, squared deviations 9+1+1+9=20, sample var = 20/3 ≈ 6.6667, std = sqrt(6.6667) ≈ 2.581989. Each shifted window has the same shape.

Hints

Don't recompute the mean and variance from scratch for each window — that is O(n*k). Maintain a running sum S and running sum of squares Q over the current window so each slide is O(1).
Use the variance identity: sample variance = (Q - S*S/k) / (k - 1), where S is the window sum and Q is the window sum of squares. Take the square root for std.
Handle the denominator carefully: the interviewer cares that you use k-1 (sample), not k (population). Treat k==1 as std 0, and clamp any tiny negative variance from float error up to 0.

Quick Overview