Design a Structure That Returns the Max of the Last k Inserted Numbers

Design a data structure that receives a stream of numbers and reports the maximum of the most recent `k` numbers inserted. Implement this interface: ```python class SlidingWindow: def __init__(self, k: int) -> None: ... def put(self, number: int) -> None: ... def getMax(self) -> int: ... ``` - `SlidingWindow(k)` creates an empty structure for a window of size `k`. - `put(number)` inserts the next number of the stream. - `getMax()` returns the largest of the `k` most recently inserted numbers. For example, with `k = 3`, after `put(4)`, `put(2)`, `put(12)` and `put(3)`, `getMax()` returns 12, because the last three numbers are 2, 12 and 3. After a further `put(1)` and `put(5)`, it returns 5, because 12 has left the window. ### Clarifying Questions - Before `k` numbers have been inserted, should `getMax` return the maximum of everything inserted so far? - What should `getMax` do when nothing has been inserted yet: raise an error or return a sentinel? - Can numbers be negative or repeated? Is `k` fixed for the life of the object, and how large can it be? - Roughly how often is `getMax` called compared with `put`? ### Part 1 — A basic version Implement a straightforward working version and analyze its time and space complexity. ```hint Start simple Begin with the most direct correct version, then state each cost in terms of both `k` and `n`, the total number of puts. ``` #### What This Part Should Cover - A correct implementation, including the cases with fewer than `k` numbers and with no numbers - Time per `put` and per `getMax` - Space as a function of the number of puts ### Part 2 — Reduce space to O(k) How do you avoid storing the whole history, so that the structure uses only O(k) space? ```hint Only the last k matter Numbers older than the window can never be returned again. Think about storage of a fixed size that new numbers overwrite. ``` #### What This Part Should Cover - Storage that stops growing with the number of puts - How the oldest number is evicted on each put - The effect of the change on the time complexity ### Part 3 — Compare data structures Compare arrays, hash maps, linked lists (including doubly linked lists) and heaps as the basis for this structure: the time and space cost of `put` and `getMax`, and the trade-offs between them. ```hint Three costs per structure For each structure, ask separately what it costs to add the newest number, to drop the oldest number and to find the largest. ``` #### What This Part Should Cover - Time for `put`, time for `getMax`, and space for each structure - Which structures find the maximum quickly and which evict the oldest number quickly, and why few do both - When each choice is reasonable ### Part 4 — The monotonic deque Explain how a monotonic deque gives the optimal solution, implement it, and analyze its complexity. ```hint Some numbers can never win When a new number arrives, some older numbers in the window can never be the maximum again. Decide what to do with them at that moment. ``` #### What This Part Should Cover - The invariant the deque maintains and why its front is the maximum - How numbers that have left the window are detected and removed - Amortized versus worst-case cost per operation, and the space bound ### What a Strong Answer Covers - Clarifies the partial-window and empty cases and the mix of reads and writes before coding - Correct, runnable code at each stage, checked on a small trace - Accurate complexity in terms of both `k` and `n`, separating amortized from worst-case cost - A fair comparison of structures that recognizes what each can and cannot do efficiently - A monotonic-deque solution with a clearly stated invariant and correct expiry logic ### Follow-up Questions - Also support `getMin()` in O(1). What do you add? - The window becomes time-based: the maximum of the numbers inserted in the last 60 seconds. What changes? - Many threads call `put` and `getMax` concurrently. How do you keep the structure correct, and what does it cost? - What if you also need the median of the window?