Вычисление медианы (или приблизительной медианы) 1 триллиона удвоений
Это был вопрос для интервью, размещенный на Glassdoor.
Рассмотрим файл с 1 триллионом двойников. Как вы можете найти медиану или приблизительную медиану? Ваш компьютер не может прочитать 1 триллион двойников. Допускается распараллеливание алгоритма.
Последняя часть указывает на то, что я, вероятно, могу использовать медианное значение медиан или даже некоторую параллельную быструю сортировку. В первом случае просто разделите файл между определенным количеством процессоров, чтобы каждый процесс мог читать свою часть файла в память.
Я также думаю, что подход, предложенный @DJClayworth в разделе Рассчитать медиану миллиарда чисел, также может быть использован. Я думаю, что остальные методы из этого поста неосуществимы.
Какие еще подходы можно использовать для этого? Меня интересуют, возможно, рандомизированные алгоритмы, которые могут найти приблизительную медиану с приличной вероятностью.