FastPrepSliding-Window Frequency Snapshots

Sliding-Window Frequency Snapshots

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given an integer array nums and a fixed windowSize, report the frequency of every distinct value in every contiguous window.

Return one row [windowStart, value, count] for each distinct value in each window. Process windows by increasing windowStart; within one window, order rows by increasing value.

Update the frequency state as the left and right edges move instead of recounting every window from scratch.

Function

windowFrequencies(nums: int[], windowSize: int) → int[][]

Examples

Example 1

nums = [1,2,1,3]windowSize = 3return = [[0,1,2],[0,2,1],[1,1,1],[1,2,1],[1,3,1]]

The first window is [1,2,1]; the second is [2,1,3]. Each window contributes rows sorted by value.

Example 2

nums = [5,5,5]windowSize = 2return = [[0,5,2],[1,5,2]]

Both length-two windows contain only value 5, with frequency two.

Example 3

nums = [-1,2]windowSize = 1return = [[0,-1,1],[1,2,1]]

A size-one window produces exactly one frequency row.

Constraints

  • 1 <= nums.length <= 500.
  • -1000000 <= nums[i] <= 1000000.
  • 1 <= windowSize <= nums.length.
  • The total number of returned rows is at most 250000.

More Google problems

See Google hiring insights
public int[][] windowFrequencies(int[] nums, int windowSize) {
    // write your code here
}
nums[1,2,1,3]
windowSize3
expected[[0,1,2],[0,2,1],[1,1,1],[1,2,1],[1,3,1]]
Checking account…