FastPrep
Problem · Array

Sliding-Window Averages as Reduced Fractions

Learn this problem
● MediumCoinbase logoCoinbaseFULLTIMEONSITE INTERVIEW

Problem statement

You are given a positive integer windowSize and an array values. Process the values from left to right as successive calls to a sliding-window statistic.

After each value arrives, compute the average of the most recent windowSize values, or of all values seen so far when fewer have arrived. Return one pair [numerator, denominator] per arrival. Every fraction must be reduced to lowest terms, and its denominator must be positive.

The result therefore preserves every state transition of the ordered stream without floating-point rounding.

Function

slidingWindowAverages(windowSize: int, values: int[]) → long[][]

Examples

Example 1

windowSize = 3values = [1,10,3,5]return = [[1,1],[11,2],[14,3],[6,1]]

The active windows are [1], [1,10], [1,10,3], and [10,3,5]. Their reduced averages are 1, 11/2, 14/3, and 6.

Example 2

windowSize = 2values = [-1,2,-3]return = [[-1,1],[1,2],[-1,2]]

The final active window is [2,-3], whose average is -1/2.

Example 3

windowSize = 5values = [0,0]return = [[0,1],[0,1]]

Zero averages are normalized to 0/1.

Constraints

  • 1 <= windowSize <= 100000.
  • 0 <= values.length <= 100000.
  • -1000000000 <= values[i] <= 1000000000.
  • Process values in their supplied order.
  • Use signed 64-bit arithmetic for the running sum and returned fraction components.

More Coinbase problems

drafts saved locally
public long[][] slidingWindowAverages(int windowSize, int[] values) {
    // Write your code here.
}
windowSize3
values[1,10,3,5]
expected[[1,1],[11,2],[14,3],[6,1]]
checking account