## Problem You are given a list of daily prices for a product and a window size `w`. For each day `i >= w-1`, compute the minimum price seen in the window `[i-w+1, i]`. Return an array of these rolling minimums. ```python def rolling_min(prices: list[int], w: int) -> list[int]: ``` ## Example ``` prices = [3, 1, 2, 5, 4, 2, 6], w = 3 windows: [3,1,2]=1, [1,2,5]=1, [2,5,4]=2, [5,4,2]=2, [4,2,6]=2 Output: [1, 1, 2, 2, 2] ``` Brute force is O(n*w). Expected solution uses a monotonic deque for O(n). ## Follow-ups 1. Adapt the solution to compute rolling maximum instead. 2. How would you compute rolling median in a window? What data structure supports this? 3. The window is variable per day (e.g., `windows[i] = i % 5 + 1`). How does this affect the deque approach? 4. Implement `rolling_min` as a generator that yields one result at a time, supporting infinite price streams.

InterviewDB Question

Low Price - Sliding Window Minimum Price Tracker

phone

Question Details

Problem You are given a list of daily prices for a product and a window size w. For each day i >= w-1, compute the minimum price seen in the window [i-w+1, i]. Return an array of these rolling minimums. Example Brute force is O(n*w). Expected solutio…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding Onsite Phone

More from Google

Reddit Why did you create those day in a life video? Reddit It works Reddit Brave Software director screening went south fast, these companies are weird Reddit Job finished Reddit Anxiety and brain freeze during interview

← All Google questions Google Software Engineer Questions → All Sliding Window Questions →