4 ms·
I liked the question and after thinking hard about potential algorithms, I came to a different conclusion: - In general for data sets of this size, you don't w
by rjprins 17y ago
I liked the question and after thinking hard about potential algorithms, I came to a different conclusion:
- 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.
- roundsquare 17y agoThats 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.
- eru 17y agoAnd getting the exact number is already a linear problem.
- rjprins 17y agoIn 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.
- eru 17y agoNo. 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. [1] http://en.wikipedia.org/wiki/Selection_algorithm http://en.wikipedia.org/wiki/Selection_algorithm