News for hackers. Stuff that matters.
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.

Re:The Median of a Trillion Numbers by eru on Monday August 24, 2009 @09:00AM (#782014)
And getting the exact number is already a linear problem.
Re:The Median of a Trillion Numbers by rjprins on Tuesday August 25, 2009 @04:00AM (#784419)
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.
Re:The Median of a Trillion Numbers by eru on Tuesday August 25, 2009 @08:48AM (#784700)
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.

[1] http://en.wikipedia.org/wiki/Selection_algorithm