Quick Overview

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.

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.

Overview: 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

  1. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half of the window.
  2. Balance heaps so that the max-heap has either the same number of valid elements as the min-heap or one more.
  3. Use a hashmap for lazy deletion to remove elements that slide out without direct heap deletion.
  4. When computing the median, prune invalid (delayed) elements from heap tops.
  5. For even k, average the max of the lower half and the min of the upper half.

Loading coding console...

Show the approach

Approach

Maintain two heaps representing the lower and upper halves of the current window: a max-heap (as negatives) for the lower half and a min-heap for the upper half. Insert each new element into the appropriate heap, and lazily delete elements that slide out using a hashmap (value -> count). Balance heaps so that the max-heap has either the same count as the min-heap or one more valid element. The median is either the top of the max-heap (odd k) or the average of both heap tops (even k). Pruning removes any delayed elements from heap tops just before they are used or moved. This approach yields O(n log k) time with O(k) space.

Time complexity:
O(n log k)
Space complexity:
O(k)