The Middle Ground

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Meta

Problem

An on-call engineer has stopped trusting the median on her clock-skew panel, where hosts report offsets in whole milliseconds that are often negative, zero, or repeated. Implement a RunningMedian class whose get_median() returns the median of every offset passed to add(num) so far, and a run_operations(operations) driver that replays the operations on one instance and returns one result per operation in the order they arrive, None for each add. An even count's median is the average of the two middle offsets, always a float, while an odd count returns the middle offset unchanged.

The middle value keeps moving.

Example 1

Input:

operations = [["add",5],["get_median"],["add",3],["get_median"],["add",8],["get_median"]]

Output:

[null,5,null,4,null,5]

Example 2

Input:

operations = [["add",1],["add",2],["get_median"]]

Output:

[null,null,1.5]

Worked solution and explanation

What this really is

This is an order-statistics question dressed up as a flaky dashboard. The median is a position in value order, and offsets never arrive in value order. Anyone can write the class and the driver; what separates candidates is whether get_median() reads the middle of the values ranked by size or the middle of whatever happened to arrive. Feed it 5, 3, 8 and the arrival-order middle is 3 while the real median is 5. That is exactly the number the on-call engineer stopped trusting.

Building it

Step 1: Store the offsets in value order

Each add puts the new offset into the list and calls sort(). The list was already sorted, so only one element is out of place and the sort finishes in roughly linear time instead of a full n log n pass.

Step 2: Read the middle by position

With count values, mid = count // 2. An odd count returns values[mid] untouched, so an integer offset comes back as an integer. An even count averages values[mid - 1] and values[mid] with /, which always yields a float: 3 and 5 give 4.0.

Step 3: Replay the operations on one instance

run_operations builds a single RunningMedian, walks the operations in order, and appends None for every add and the current median for every query. One shared instance is the point: each query sees everything added before it and nothing after.

Step 4: Refuse to answer an empty query

Asking before anything is added has no answer, so get_median() raises ValueError rather than inventing one. The replays never do this, but a class that returns a made-up number here is how a panel starts lying.

The solution

Sorted offsets in `RunningMedian`, replayed by `run_operations`
class RunningMedian:
    values = []  # empty default; add() binds a fresh list to each instance

    def add(self, num):
        updated = self.values + [num]
        updated.sort()
        self.values = updated

    def get_median(self):
        if not self.values:
            raise ValueError("No values added yet")
        count = len(self.values)
        mid = count // 2
        if count % 2 == 1:
            return self.values[mid]
        return (self.values[mid - 1] + self.values[mid]) / 2


def run_operations(operations):
    tracker = RunningMedian()
    results = []
    for op in operations:
        if op[0] == "add":
            tracker.add(op[1])
            results.append(None)
        elif op[0] == "get_median":
            results.append(tracker.get_median())
    return results
Middle of arrival order
After adding 5, 3, 8 the raw list is [5, 3, 8] and its middle slot holds 3. After -5, -1, -3 it reports -1. Both numbers look plausible, which is exactly why this version ships.
Middle of value order
Sorted, those lists are [3, 5, 8] and [-5, -3, -1], so the medians are 5 and -3: the numbers a hand count produces.

Common follow-up questions