Find Median Given Frequency of Numbers

Find Median Given Frequency of Numbers

What is this problem about?

The Find Median Given Frequency of Numbers coding problem is a SQL task. You are given a table Numbers with columns number and frequency. You need to calculate the median of all the numbers in the dataset. Since the data is grouped by frequency, you are essentially dealing with a frequency distribution table.

Why is this asked in interviews?

Pinterest and other companies use this to test advanced SQL skills, specifically Cumulative Aggregation and Window Functions. Calculating a median in SQL is notoriously difficult because standard SQL doesn't have a built-in MEDIAN() function. It evaluates whether you can use cumulative sums to find the "middle" positions in a sorted frequency list.

Algorithmic pattern used

This problem follows the Cumulative Frequency pattern.

1. Calculate the total count of all numbers ($N$).
2. Calculate the running_sum of frequencies for each number when sorted.
3. Identify the middle position(s): $N/2$ and $(N+1)/2$.
4. A number is part of the median if its cumulative range (from running_sum - frequency to running_sum) covers one of those middle positions.
5. The final median is the average of the numbers found for those positions.

Example explanation

Number	Freq	Cumulative
0	7	7
1	1	8
2	3	11
Total $N=11$. Middle position is $(11+1)/2 = 6$.

• Number 0 covers positions 1 to 7. Since 6 is in this range, the median is 0.

If $N=12$, middle positions are 6 and 7. Both are covered by Number 0. Median = (0+0)/2 = 0.

Common mistakes candidates make

• Ignoring Frequencies: Calculating the median of the number column without considering how many times each number appears.
• Off-by-one: Mistakes in calculating the cumulative range boundaries.
• Inefficient Joins: Using cross-joins to expand the table instead of using window functions, which is far more efficient.

Interview preparation tip

Practice the SUM(freq) OVER(ORDER BY number) window function. It is the key to handling frequency-based data in SQL. Understanding how to find the "median row" using cumulative counts is a high-level skill that differentiates senior candidates.