Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Favorite Algorithm: Linear Time Median Finding (2018)

rcoh.me

Post reply on HN
Print view View original

11–20 of 189 posts

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#11

Post by anonymoushn »

Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

Do you mean topK rather than median, for K small? You certainly cannot build a heap with trillions of items in it.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#12

Post by cosmic_quanta »

mgaunard wrote: post #7

You could also use one of the streaming algorithms which allow you to compute approximations for arbitrary quantiles without ever needing to store the whole data in memory.

That is cool if you can tolerate approximations. But the uncomfortable questions soon arise: Can I tolerate an approximate calculation? What assumptions about my data do I to determine an error bound? How to verify the validity of my assumptions on an ongoing basis?

Personally I would gravitate towards the quickselect algorithm described in the OP until I was forced to consider a streaming median approximation method.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#13

Post by Xcelerate »

anonymoushn wrote: post #11
Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

Do you mean topK rather than median, for K small? You certainly cannot build a heap with trillions of items in it.

No, I mean median. Here is an article describing a very similar problem since I can’t link to the leetcode version: https://www.geeksforgeeks.org/median-of-stream-of-running-in...

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#14

Post by jiggawatts »

Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

I've heard of senior people applying for jobs like this simply turning the interview question around and demanding that the person asking it solve it in the allotted time. A surprisingly high percentage of the time they can't.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#15

Post by conradludgate »

cosmic_quanta wrote: post #12
mgaunard wrote: post #7

You could also use one of the streaming algorithms which allow you to compute approximations for arbitrary quantiles without ever needing to store the whole data in memory.

That is cool if you can tolerate approximations. But the uncomfortable questions soon arise: Can I tolerate an approximate calculation? What assumptions about my data do I to determine an error bound? How to verify the validity of my assumptions on an ongoing basis? Personally I would gravitate towards the quickselect algorithm described in the OP until I was forced to consider a streaming median approximation method…

Well, I believe you could use the streaming algorithms to pick the likely median, so help choose the pivot for the real quickselect. quickselect can be done inplace too which is O(1) memory if you can afford to rearrange the data.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#16

Post by pfdietz »

Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

You don't need to load trillions of numbers into memory, you just need to count how many of each number there are. This requires 2^32 words of memory, not trillions of words. After doing that just scan down the array of counts, summing, until you find the midpoint.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#17

Post by Xcelerate »

jiggawatts wrote: post #14
Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

I've heard of senior people applying for jobs like this simply turning the interview question around and demanding that the person asking it solve it in the allotted time. A surprisingly high percentage of the time they can't.

This company receives so many candidates that the interviewer would have just ended the call and moved on to the next candidate.

I get the notion of making the point out of principle, but it’s sort of like arguing on the phone with someone at a call center—it’s better to just cut your losses quickly and move on to the next option in the current market.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#18

Post by conradludgate »

saagarjha wrote: post #6

This is hinted at in the post but if you're using C++ you will typically have access to quickselect via std::nth_element. I've replaced many a sort with that in code review :) (Well, not many. But at least a handful.)

Same with rust, there's the `select_nth_unstable` family on slices that will do this for you. It uses a more fancy pivot choosing algorithm but will fall back to median-of-medians if it detects it's taking too long

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#19

Post by Xcelerate »

pfdietz wrote: post #16
Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

You don't need to load trillions of numbers into memory, you just need to count how many of each number there are. This requires 2^32 words of memory, not trillions of words. After doing that just scan down the array of counts, summing, until you find the midpoint.

Yeah, I thought of that actually, but the interviewer said “very little memory” at one point which gave me the impression that perhaps I only had some registers available to work with. Was this an algorithm for an embedded system?

The whole problem was kind of miscommunicated, because the interviewer showed up 10 minutes late, picked a problem from a list, and the requirements for the problem were only revealed when I started going a direction the interviewer wasn’t looking for (“Oh, the file is actually read-only.” “Oh, each number in the file is an integer, not a float.”)

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#20

Post by sevensor »

mgaunard wrote: post #7

You could also use one of the streaming algorithms which allow you to compute approximations for arbitrary quantiles without ever needing to store the whole data in memory.

I’ve definitely had situations where a streaming quantile algorithm would have been useful, do you have any references?
Post reply on HN