Re:The Median of a Trillion Numbers
by roundsquare on Monday August 24, 2009 @04:48AM
(#781769)
Thats a good point. Two things come t mind though. One is that since its an interview question they are probably just using this to test your knowledge of (distributed) algorithms.
The second is that you might want the exact answer if you are using the statistic to convince someone of something and you don't want to leave any room for doubt.
And getting the exact number is already a linear problem.
In the ideal case you find the correct pivot immediately, but in worst case you will have to sort the whole list. Thus O(n) = n log n.
No. You can find every order statistic in O(n) [1]. And even if someone handed you the pivot, you still had to prove that this is right.
- In general for data sets of this size, you don't want anything more then a linear algorithm or less preferably.
- Also, because a median is a statistic measure, it's use will be of a predicting nature. (Why would anyone need the exact median of a trillion numbers?)
- Because of the uncertainty involved with predicting and the size of the data set, I think a sample approach would be appropriate.
- A sample size of 1000 - 10,000 numbers per machine is enough for significantly recognizing any reasonable distribution.
- We could take the median of those 1 - 10 million numbers directly or we could apply curve fitting techniques to gain a lot more insight.
Of course if someone could provide a reason for needing the exact median I am completely wrong.