Find the median of a stream of ages

Question

Recently, I was given a coding question where the statement was that I would be given a stream of ages of people and then at any point the median would be asked for.

Something like this:

add(20)
add(30)
add(30)
add(40)
getMedian() // prints 30

Now this problem is similar to this Leetcode problem:

Find Median from Data Stream

So I gave the 2 heaps approach - one max heap and one min heap.

The interviewer was not impressed and hinted that there was an optimization possible since all the ages of people could be assumed to be between 1 to 130, and also there would be a lot of repeated ages ie. there are a lot of people with the age 20, for example.

I was unable to come up with any better optimizations, so I gave an approach with a HashMap counting all the frequencies and then counting the occurances. This was completely incorrect.

What am I missing here ? How does the ages being bounded help me ?

EDIT:

Answer here: https://stackoverflow.com/a/23603511/7134737

user_585411 · Answer

The approach that the interviewer was probably looking for is this.

Maintain an array of frequency counts.

Maintain the overall count of the array.

Maintain a variable saying which bucket the median value is in, and a second where in that bucket it is.

Inserts are O(1) because you have to update an array entry, update the overall count, update where in that median bucket you are, and occasionally scan through a fixed number of buckets for the next one with entries.

Returning the median is O(1) as well because you are maintaining that answer in a variable that you can look up.

Using a HashMap instead of an array is just constant factor different. However having to calculate the answer on demand is slower.

Note that this answer is optimized for the median. Suppose that we wanted to calculate any particular percentile instead. We can make that easy with a different data structure.

I would solve this one with a 257 element array arranged like this:

0: 0
1: Count of people aged 0
2: Count of people aged 0 or 1
3: Count of people aged 2
4: Count of people aged 0, 1, 2, or 3
5: Count of people aged 4
6: Count of people aged 4 or 5
7: Count of people aged 6
8: Count of people aged 0, 1, 2, 3, 4, 5, 6, or 7
...

In general the 2^i * jth entry, with j odd, will be the count of people in the range 2^i * (j-1) to 2^i * j - 1.

To insert a value, I start at n+1 and jump to increasing powers of 2 for a maximum of 8 entries. For example if I have a 21 year old to insert in the data structure, I would increment the values at 22, 24, 32, 64, 125, and 256.

To get a count of people who are less than or equal to 21 I similarly look down by powers of 2. So I'd read the values at 22, 20, 16 and 0.

To get the total people in the data structure, I'd look at the value in position 256.

To find what age a specific count falls at is more complicated. I'd fall down by powers of 2 then do a binary search. So suppose that the final answer was 21. I'd have had to look at 256, 128, 64, 32, 16, and then locked in the age range 0..15. Then look for the 16..31 year olds by looking in 24 then 20. That locks in the 16..19 year olds. Repeat with 22, 21 and lock in the 20 year olds. And my answer is somewhere in the 21 year olds.

In the given example this data structure is O(1) for all operations because it has fixed size. But if you had a larger number of buckets, then all operations are O(log(# of buckets)).

Find the median of a stream of ages

1 Answers