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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Trexquant during technical interviews.

Streaming Median Tracker | Trexquant Coding Question

Quick Overview

This question evaluates a candidate's ability to design a data structure that maintains a running median over a stream of numbers, testing knowledge of heaps and balanced data partitioning. It is a classic coding and algorithms interview problem used to assess understanding of amortized time complexity and efficient online statistics tracking, requiring practical implementation rather than just conceptual discussion.

Streaming Median Tracker

Company: Trexquant

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

# Streaming Median Tracker Design a data structure that ingests integers one at a time from a stream and can report the **median of every integer inserted so far** at any moment. The median of a collection of numbers is the middle value once the numbers are arranged in non-decreasing order: - If the collection has an **odd** number of elements, the median is the single middle element. - If the collection has an **even** number of elements, the median is the **average of the two middle elements**. Implement a class `MedianTracker` with the following operations: - `MedianTracker()` — initialize an empty tracker. - `add(num)` — insert the integer `num` into the structure. Duplicates and negative values are allowed. - `median()` — return the median of all integers inserted so far as a floating-point number. This method is only invoked after at least one call to `add`. ### Example ``` MedianTracker t t.add(1) // multiset = [1] t.median() // returns 1.0 t.add(3) // multiset = [1, 3] t.median() // returns 2.0 (average of the two middle values 1 and 3) t.add(2) // multiset = [1, 2, 3] t.median() // returns 2.0 (single middle value) t.add(10) // multiset = [1, 2, 3, 10] t.median() // returns 2.5 (average of 2 and 3) ``` ### Constraints - Values passed to `add` are 32-bit signed integers; they may be negative and may repeat. - `add` can be called up to $10^5$ times, interleaved arbitrarily with `median` calls. A solution that re-sorts the data on every `median` call (overall $O(n^2 \log n)$) is too slow — aim for roughly $O(\log n)$ per `add` and $O(1)$ per `median`. - `median` is never called before the first `add`. - The returned median must be exact: when the count is even, return the true average of the two middle elements (which may be a non-integer such as `2.5`). ### Required Output Each call to `median()` returns a single floating-point number equal to the median of all integers inserted up to that point.

Quick Answer: This question evaluates a candidate's ability to design a data structure that maintains a running median over a stream of numbers, testing knowledge of heaps and balanced data partitioning. It is a classic coding and algorithms interview problem used to assess understanding of amortized time complexity and efficient online statistics tracking, requiring practical implementation rather than just conceptual discussion.

Design a data structure that ingests integers one at a time and can report the median of everything inserted so far at any moment. Because the online judge drives a class through a scripted sequence of calls, implement a single driver function `solution(operations, values)`: - `operations` is a list of method names. The first is always `"MedianTracker"` (construct/reset an empty tracker). The rest are `"add"` or `"median"`. - `values` is a parallel list of argument lists. For an `"add"` op the entry is `[num]`; for `"MedianTracker"` and `"median"` it is `[]`. - For each `"median"` op, compute the median of every integer inserted so far and append it (as a float) to a results list. Return that results list. Median rules: sort the values inserted so far in non-decreasing order. If the count is odd, the median is the single middle value; if even, it is the average of the two middle values (which may be a non-integer such as `2.5`). Duplicates and negative values are allowed, and `median` is never invoked before the first `add`. Example: operations `["MedianTracker", "add", "median", "add", "median", "add", "median", "add", "median"]` with values `[[], [1], [], [3], [], [2], [], [10], []]` returns `[1.0, 2.0, 2.0, 2.5]`. Aim for about O(log n) per add and O(1) per median; re-sorting on every median call is too slow for up to 10^5 operations.

Constraints

The first operation is always "MedianTracker"; every subsequent op is "add" or "median".
Values passed to add are 32-bit signed integers; they may be negative and may repeat.
add can be called up to 10^5 times, interleaved arbitrarily with median calls.
median is never called before the first add.
When the running count is even, return the exact average of the two middle elements (may be non-integer, e.g. 2.5).

Examples

Input: (["MedianTracker", "add", "median", "add", "median", "add", "median", "add", "median"], [[], [1], [], [3], [], [2], [], [10], []])

Expected Output: [1.0, 2.0, 2.0, 2.5]

Explanation: Running medians after each add: [1]->1.0, [1,3]->avg(1,3)=2.0, [1,2,3]->2.0, [1,2,3,10]->avg(2,3)=2.5. Matches the prompt example.

Input: (["MedianTracker", "add", "median"], [[], [5], []])

Expected Output: [5.0]

Explanation: Single element: the median is that element as a float.

Input: (["MedianTracker", "add", "add", "add", "median", "add", "median"], [[], [-1], [-1], [-1], [], [-5], []])

Expected Output: [-1.0, -1.0]

Explanation: All-duplicate negatives: [-1,-1,-1]->-1.0; after adding -5 -> [-5,-1,-1,-1], the two middle values are both -1 so the average is -1.0.

Input: (["MedianTracker", "add", "add", "median"], [[], [1], [2], []])

Expected Output: [1.5]

Explanation: Even count with a non-integer median: avg(1, 2) = 1.5.

Input: (["MedianTracker", "add", "add", "add", "add", "add", "median"], [[], [6], [10], [2], [6], [5], []])

Expected Output: [6.0]

Explanation: Sorted so far: [2,5,6,6,10]; odd count of 5, the single middle value is 6.0. Confirms unsorted insertion order and duplicates are handled.

Input: (["MedianTracker", "add", "median", "add", "median"], [[], [-10], [], [10], []])

Expected Output: [-10.0, 0.0]

Explanation: Negatives with a running median: [-10]->-10.0; after adding 10 -> [-10,10], avg(-10,10)=0.0.

Hints

Keep the values split into two halves: a max-heap holding the smaller half and a min-heap holding the larger half. Maintain the invariant that the max-heap has the same size as the min-heap, or exactly one more element.
Python's heapq is a min-heap; simulate a max-heap by pushing negated values.
On each add, push then rebalance so |len(small) - len(large)| <= 1. The median is the top of the larger heap when sizes differ, otherwise the average of the two tops.
Return a float even when the median is a whole number (e.g. 1.0), and use true division so even counts can yield values like 2.5.

Last updated: Jul 1, 2026

Loading coding console...