1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ232

Page ↗

Q232FWASIC interview problem

Forward-looking sliding window maximum

TechniquesSystemVerilogSliding windowMonotonic dequeReverse traversal

DifficultyMedium

TopicArrays

LanguageSystemVerilog

Requirements4 checkpoints

Problem

For every index i, compute the maximum from a[i] through a[min(i + K - 1, n - 1)]. Return one output per input index, using a truncated window near the end.

Function headerSystemVerilog

function automatic void sliding_window_max_forward(
  int k,
  ref int a[],
  ref int out[]
);

Example input and output

Use this case to check your interpretation

Input

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

Output

[3,3,5,5,6,7,7,7]

Explanation

Each output looks forward up to three positions, with naturally truncated windows for the last two indices.

Requirements (4)

Return an output array with the same length as the input.
Return an empty output for empty input and clamp K to 1 through n otherwise.
First explain the O(nK) scan, then implement an O(n) monotonic-deque solution.
Use indices in the deque so expired elements are identified unambiguously.