How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Compute sliding-window medians | Meta Coding Question

Quick 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.

Compute sliding-window medians

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

Given an integer array `nums` and an integer `k`, compute the median of every contiguous subarray (window) of length `k`, and return the sequence of medians in order. The median is the middle value in an ordered window. When `k` is odd, it is the single middle element. When `k` is even, define it as the average of the two middle elements. Return each median as a floating-point number. **Approach for O(n log k):** Maintain a sorted multiset of the current window. For each step, remove the element leaving the window (binary-search its position to handle duplicates and deletions correctly) and insert the new element, then read the middle element(s). A balanced two-heap structure (a max-heap for the lower half and a min-heap for the upper half) with lazy deletion achieves the same O(log k) per slide. **Space complexity:** O(k) for the window structure plus O(n - k + 1) for the output sequence. Example: `nums = [1, 3, -1, -3, 5, 3, 6, 7]`, `k = 3` → windows are `[1,3,-1]`, `[3,-1,-3]`, `[-1,-3,5]`, `[-3,5,3]`, `[5,3,6]`, `[3,6,7]`, giving medians `[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]`.

Constraints

1 <= k <= nums.length
Window length k is fixed across all windows.
Array values may include duplicates and negative numbers.
Median for even k is the average of the two middle elements (returned as a float).
Return medians as floating-point values in window order.

Examples

Input: ([1, 3, -1, -3, 5, 3, 6, 7], 3)

Expected Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]

Explanation: Odd k=3: median is the middle element of each sorted window.

Input: ([1, 2, 3, 4], 2)

Expected Output: [1.5, 2.5, 3.5]

Explanation: Even k=2: each median is the average of the two window elements.

Hints

Keep the current window in a sorted structure so the median is just the middle element(s) — index k//2 for odd k, average of indices k//2-1 and k//2 for even k.
When sliding, binary-search for the outgoing element's exact position before removing it; this keeps duplicate handling correct (bisect_left finds the leftmost equal value).
For a strict O(n log k) bound, use two balanced heaps (a max-heap for the lower half, a min-heap for the upper half) with lazy deletion, rebalancing so their sizes differ by at most one.