Description

Table: Numbers

Column NameType
numint
frequencyint
  • num is the primary key (column with unique values) for this table.
  • Each row of this table shows the frequency of a number in the database.

The median is the value separating the higher half from the lower half of a data sample.

Problem Statement

Write a solution to report the median of all the numbers in the database after decompressing the Numbers table. Round the median to one decimal point. The result format is in the following example.

Example 1:

Input:

  • Numbers table:
numfrequency
07
11
23
31

Output:

median
0.0

Explanation: If we decompress the Numbers table, we will get [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3], so the median is (0 + 0) / 2 = 0.

Solution

In this case, we will have total of 12 numbers if they are inserted frequency number of times. So, median record is at index position 6 and 7.

  1. First, you need to find the position of the median number based on frequency. This you can find using sum of frequency divided by 2. That will be the position of the median number.
1SELECT num, frequency, 
2    (SUM(frequency) OVER ()) / 2 AS 'median_position'
3    FROM Numbers
numfrequencymedian_num
076
116
236
316

As you can see from above, we have found the median_position, that is the record number from this table that contains median value.

  1. You also need to find what will be the position of each number if they were inserted frequency number of times in the array. This can be done using the running sum of frequency ordered by number.
1SELECT num, frequency,
2    SUM(frequency) OVER (ORDER BY num) AS running_position
3    FROM Numbers;
numfrequencyrunning_position
077
118
2311
3112

This gives us the position for each number in the inpute table.

  1. Now to find the median number, you have to find number which is having running_position - frequency and running_position.
1WITH cte AS (
2    SELECT num, frequency, 
3        SUM(frequency) OVER (ORDER BY num) running_position,
4        (SUM(frequency) OVER ()) / 2 AS median_position
5        FROM Numbers
6) SELECT AVG(num) AS median 
7    FROM cte
8    WHERE median_position BETWEEN (running_position - frequency)
9        AND running_position;