Solve sliding-window and heap problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Design an algorithm using a sliding window to compute the maximum sum of any contiguous subarray of length k; explain time- and space-complexity optimizations and how you would adapt the solution for concurrent execution. Maintain the median of the last k numbers of a real-time integer stream; choose appropriate data structures (e.g., two heaps, hashmap) and discuss trade-offs and optimizations.
Quick Answer: This question evaluates algorithm design and data structure proficiency, focusing on sliding-window techniques for fixed-length subarray aggregates and heap- or hashmap-based approaches for maintaining medians in a real-time integer stream, along with considerations for concurrent execution.
Given an integer array nums and an integer k, return a list of the medians of every contiguous subarray (sliding window) of length k. The median of a window is the middle value after sorting the k elements; if k is even, it is the average of the two middle values. Return each median as a float, in the order of the windows from left to right.
Constraints
- 1 <= len(nums) <= 200000
- 1 <= k <= len(nums)
- -10^9 <= nums[i] <= 10^9
- Return medians as floats; for even k, use (a + b) / 2.0 with no rounding beyond floating-point defaults
- Target time complexity: O(n log k), space: O(k)
Hints
- Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half of the window.
- Balance heaps so that the max-heap has either the same number of valid elements as the min-heap or one more.
- Use a hashmap for lazy deletion to remove elements that slide out without direct heap deletion.
- When computing the median, prune invalid (delayed) elements from heap tops.
- For even k, average the max of the lower half and the min of the upper half.