Compute sliding-window medians
Overview
This question evaluates proficiency in designing and analyzing efficient sliding-window algorithms and data structures for computing running medians, including correct handling of duplicates, deletions, and the convention for defining the median when k is even.
Meta
Jul 31, 2025, 12:00 AM
Machine Learning Engineer
Technical Screen
Coding & Algorithms
0
0
Given an array nums and an integer k, compute the median for each contiguous subarray (window) of length k and return the sequence of medians in order. Describe an algorithm running in O(n log k) time that handles duplicates and deletions efficiently, specify how to define the median when k is even, and analyze space complexity.