Я столкнулся с этой проблемой в недавнем интервью:
У вас есть поток входящих чисел в диапазоне 0 to 60000
, и у вас есть функция, которая возьмет число из этого диапазона и вернет количество вхождений этого числа до этого момента. Дайте подходящую структуру данных/алгоритм для реализации этой системы.
Мое решение:
Создайте массив размером 60001, указывающий на битовые -векторы. Эти битовые векторы будут содержать количество входящих чисел, и входящие числа также будут использоваться для индексации массива для соответствующего числа. Векторы битов -будут динамически увеличиваться по мере того, как число становится слишком большим, чтобы их можно было удерживать.
Таким образом, если числа идут со скоростью 100numbers/sec
, то через 1 миллион лет общее количество будет = (100*3600*24)*365*1000000 = 3.2*10^15
. В худшем случае, когда все числа в потоке одинаковы, потребуется ceil((log(3.2*10^15) / log 2) )= 52bits
, и если числа распределены равномерно, у нас будет (3.2*10^15) / 60001 = 5.33*10^10
количество вхождений для каждого числа, что потребует всего 36 bits
для каждого числа. Итак, предполагая 4-байтовые указатели, нам нужно (60001 * 4)/1024 = 234 KB
памяти для массива, а для случая с теми же числами нам нужен размер битового вектора = 52/8 = 7.5 bytes
, который по-прежнему составляет около 234 КБ. А для другого случая нам нужно (60001 * 36 / 8)/1024 = 263.7 KB
для битового вектора общим размером около 500 КБ. Таким образом, это вполне возможно сделать с помощью обычного ПК и памяти.
Но интервьюер сказал, что, поскольку это бесконечный поток, он в конечном итоге переполнится, и дал мне подсказку, например, как мы можем это сделать, если было много компьютеров, и мы могли бы передавать сообщения между ними или думать о файловой системе и т. д. Но я продолжал думать, если это решение не работал тогда, другие тоже. Излишне говорить, что я не получил работу.
Как решить эту проблему с меньшим объемом памяти?Можете ли вы придумать альтернативный подход (с использованием сети ПК )?