Walmart Experienced-Hire Interview (August): Sliding Window Maximum with a Priority Queue + Optimization

Overview

Lots of experienced-hire SDE2 interviews have been going out recently — Amazon, Walmart, Google L6. Here's a priority queue question from Walmart. Useful if you're switching jobs or were recently laid off!

The problem was described entirely verbally, so take your own notes.

Problem

Given an array and a window size k, return the maximum of each window (sliding window maximum).

Solution 1: priority queue (max-heap)

Push (value, index) into a max-heap. Before reading the top, pop elements whose index has slid out of the window.

import heapq

def max_sliding_window_heap(nums, k):
    heap, res = [], []
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        while heap[0][1] <= i - k:      # lazy deletion: pop only when the top is stale
            heapq.heappop(heap)
        if i >= k - 1:
            res.append(-heap[0][0])
    return res

Time O(n log n), space O(n).

Follow-up: optimize

Use a monotonically decreasing queue (deque). It stores indices whose values decrease from front to back:

• Before pushing a new element, pop smaller elements from the back — they can never be the maximum again.
• Pop the front when its index slides out of the window.
• The front is the current window's maximum.

from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Each element is pushed and popped at most once: O(n) time and O(k) extra space.

Complexity comparison

Approach	Time	Space
Brute force	O(nk)	O(1)
Priority queue	O(n log n)	O(n)
Monotonic queue	O(n)	O(k)