Valid Max Pooling
NVIDIA● MediumFULLTIMEONSITE INTERVIEWProblem statement
Implement the forward max-pooling operation over one rectangular integer feature map image. A pooling window has kernelHeight rows and kernelWidth columns. Its row and column strides are strideHeight and strideWidth.
- The top-left window begins at
[0,0]. - Subsequent row starts are
strideHeight, 2 * strideHeight, ..., and column starts arestrideWidth, 2 * strideWidth, .... - Use only windows lying completely inside the input. There is no padding or dilation; discard every incomplete trailing window.
- For each complete window, return the maximum of all its covered input values, including negative values and duplicates.
The output is a rectangular matrix in the same row and column orientation: output[r][c] pools the window beginning at [r * strideHeight, c * strideWidth]. Its dimensions are 1 + floor((image.length - kernelHeight) / strideHeight) by 1 + floor((image[0].length - kernelWidth) / strideWidth).
Every input is valid, and the kernel fits in both dimensions. Strides may exceed the kernel dimensions or the input dimensions. Return maximum values only; gradients, maximum indices, batch and channel axes are outside this exercise. Implement the operation without a pooling library.
What the interview report shared
The onsite optimization interview ends with a request to implement max pooling. The report does not disclose tensor layout, pooling parameters, padding, the interface, examples, bounds, or forward-versus-gradient behavior.
Function
maxPool2D(image: int[][], kernelHeight: int, kernelWidth: int, strideHeight: int, strideWidth: int) → int[][]Examples
Example 1
image = [[1,3,2,0],[4,6,5,1],[7,2,9,8]]kernelHeight = 2kernelWidth = 2strideHeight = 1strideWidth = 2return = [[6,5],[7,9]]The row anchors are 0, 1 and column anchors are 0, 2. Their four window maxima are 6, 5, 7, 9, placed in that row and column order.
Example 2
image = [[-4,-8,-3,-9,-2],[-6,-7,-5,-1,-10],[-11,-12,-13,-14,-15]]kernelHeight = 2kernelWidth = 3strideHeight = 2strideWidth = 2return = [[-3,-1]]The two complete windows start at [0,0] and [0,2], giving -3 and -1. A start at row 2 would not fit, so the final input row contributes to neither output.
Example 3
image = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]kernelHeight = 1kernelWidth = 1strideHeight = 2strideWidth = 3return = [[1,4],[9,12]]A unit kernel returns its covered input value. The row starts are 0, 2, and the column starts are 0, 3; cells between those starts are skipped.
Constraints
1 <= image.length, image[0].length <= 48.- All image rows have the same nonzero length.
-10^9 <= image[r][c] <= 10^9.1 <= kernelHeight <= image.length.1 <= kernelWidth <= image[0].length.1 <= strideHeight, strideWidth <= 100.