How should I practice Sparse Valid One-Dimensional Convolution?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Sparse Valid One-Dimensional Convolution associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Sparse Valid One-Dimensional Convolution

Microsoft● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Implement one-dimensional valid cross-correlation over integer arrays signal and kernel. At output position start, multiply signal[start + tap] by kernel[tap] for every tap and sum the products. Return the output for each start from zero through signal.length - kernel.length, in increasing start order.

This exercise uses the common ML convention: do not reverse the kernel. Use one channel, unit stride, no padding and no dilation. An optimized implementation can precompute nonzero taps and avoid copying each input window.

Function

convolve1D(signal: int[], kernel: int[]) → int[]

Examples

Example 1

signal = [2,1,3,4]kernel = [1,0,-1]return = [-1,-3]

Asymmetric taps take the first value minus the value two positions later.

Example 2

signal = [3,-2,5]kernel = [2]return = [6,-4,10]

A one-tap kernel scales each signal value.

Example 3

signal = [1,2,3]kernel = [0,0,0]return = [0]

An all-zero kernel yields one zero for this full-width window.

Constraints

1 <= kernel.length <= signal.length <= 1000.
Each signal and kernel entry is an integer in [-1000,1000].
Every resulting sum fits in a signed 32-bit integer.