Skip to question
ASIC.FYI

Q233FreeSystemVerilog

Trailing sliding window maximum

Difficulty
Medium
Topic
Arrays
Language
SV
Interview prompt

Question

Change the window direction: for every index i, compute the maximum from a[max(0, i - K + 1)] through a[i], using a truncated window near the beginning.

Starting point

Question code

function automatic void sliding_window_max_trailing(
  int k,
  ref int a[],
  ref int out[]
);
Reviewed example

Trace one case

Input
a=[1,3,-1,-3,5,3,6,7]; K=3
Expected output
[1,3,3,3,5,5,6,7]

Each output covers the current value and at most two predecessors; expired deque indices are removed before reporting the front.

What to cover

Requirements

  1. Return one output per input index.
  2. Evict indices that are no longer in the trailing window.
  3. Maintain remaining candidates in decreasing-value order.
  4. Run in O(n) time.
Continue practicing
Q232 · ArraysForward-looking sliding window maximumQ167 · Data StructuresTrack top-K frequencies in a sliding windowQ082 · Firmware AlgorithmsParse a bounded Roman board revision