Katkat
Back

C++ Sliding-Window Mean of a Float Array With Inf, -Inf and NaN Handling

HeadlandsData Scientist · Online Assessment
MediumData ScientistOnline AssessmentSoftware Engineering Fundamentals

Last updated

Implement an O(n) sliding-window mean over a 32-bit float array containing IEEE-754 special values (+inf, -inf, NaN) without poisoning subsequent windows or suffering numerical drift.

Sliding-Window Mean with IEEE-754 Special Values

In quantitative trading systems, market data feeds frequently emit irregular values such as missing entries (NaN) or saturation limits (+inf, -inf). A naive running sum accumulator sum += x[i] - x[i - k] fails in production because any NaN or inf permanently poisons the accumulator with NaN for all subsequent windows.

Implement a function in C++ that computes the arithmetic mean of every contiguous subarray of size k across an array of 32-bit floats.

Function Signature

#include 

std::vector sliding_window_mean(const std::vector& nums, int k);

Requirements & IEEE-754 Semantics

For each window of length k:

  1. If the window contains at least one NaN, the mean for that window must be NaN.
  2. If the window contains both +inf and -inf, the sum is undefined, so the mean must be NaN.
  3. If the window contains +inf (and no -inf or NaN), the mean is +inf.
  4. If the window contains -inf (and no +inf or NaN), the mean is -inf.
  5. If the window contains only finite floats, return their standard arithmetic mean.
  6. Non-poisoning guarantee: An invalid or infinite value in one window must not corrupt calculations after it exits the window.

Constraints

  • 1 <= k <= nums.size() <= 1,000,000
  • Elements are standard IEEE-754 32-bit floats (float).
  • Time complexity: O(n) where n = nums.size().
  • Auxiliary space complexity: O(1) beyond the returned vector.

Examples

Example 1:

Input: nums = [1.0, 2.0, NaN, 4.0, 5.0], k = 3
Output: [NaN, NaN, 3.666667]
Explanation:
- Window [1.0, 2.0, NaN] contains NaN -> NaN
- Window [2.0, NaN, 4.0] contains NaN -> NaN
- Window [NaN, 4.0, 5.0] slides out NaN to [4.0, 5.0] (once NaN exits, window 3 is [NaN, 4.0, 5.0] -> NaN, but the next window without NaN must recover).

Example 2:

Input: nums = [inf, 2.0, -inf, 4.0], k = 2
Output: [inf, NaN, -inf]
Explanation:
- Window [inf, 2.0]: only +inf present -> inf
- Window [2.0, -inf]: only -inf present -> -inf (Note: nums[0..1] = [inf, 2.0], nums[1..2] = [2.0, -inf], nums[2..3] = [-inf, 4.0])

Hints

Hint 1

A running sum that directly adds and subtracts `NaN` or `inf` becomes irreversible because `NaN - NaN` yields `NaN`.

Hint 2

Maintain separate counters for the number of `NaN`, `+inf`, and `-inf` entries currently inside the window, and only accumulate finite values into your running sum.

Hint 3

To avoid catastrophic cancellation and floating-point precision drift over large arrays, accumulate finite values using a 64-bit `double` and consider periodic compensation or recalibration.

Follow-up questions

  • How does compiling with `-ffast-math` or `-Ofast` break standard IEEE-754 checks like `std::isnan()` or `std::isinf()`, and how can you safeguard against this?
  • If the array size `n` exceeds 10^9 and values have vastly different magnitudes, how would you control numerical drift from repeated floating-point subtractions without resetting the sum?
  • How would you adapt this algorithm if window boundaries were defined by timestamps (time-based sliding window) with out-of-order data arriving in a live stream?