Получить 100 старших чисел из бесконечного списка

53

Один из моих друзей задал этот вопрос интервью -

«Существует постоянный поток чисел, поступающих из некоторого бесконечного списка чисел, из которого вам необходимо поддерживать структуру данных, чтобы возвращать первые 100 старших чисел в любой заданный момент времени. Предположим, что все числа являются только целыми числами».

Это просто, вам нужно держать отсортированный список в порядке убывания и отслеживать наименьшее число в этом списке. Если полученный новый номер больше, чем этот самый низкий номер, то вам нужно удалить этот самый низкий номер и вставить новый номер в отсортированный список по мере необходимости.

Тогда вопрос был расширен -

«Можете ли вы убедиться, что ордер на вставку должен быть O (1)? Возможно ли это?»

Насколько я знаю, даже если вы добавите новый номер в список и снова отсортируете его, используя любой алгоритм сортировки, лучше всего будет O (logn) для быстрой сортировки (я думаю). Так что мой друг сказал, что это невозможно. Но он не был убежден, он попросил сохранить любую другую структуру данных, а не список.

Я думал о сбалансированном бинарном дереве, но даже там вы не получите вставку с порядком 1. Так что тот же вопрос у меня тоже сейчас. Хотел узнать, существует ли какая-либо такая структура данных, которая может выполнять вставку в порядке 1 для вышеуказанной проблемы, или это вообще невозможно.

Сачин Шанбхаг
источник
19
Может быть, это только я неправильно понял вопрос, но зачем вам вести сортированный список? Почему бы просто не следить за наименьшим номером, а если встречается номер, превышающий этот номер, удалить наименьший номер и ввести новый номер, не сохраняя отсортированный список. Это дало бы вам O (1).
EdoDodo
36
@EdoDodo - и после этой операции, как вы узнаете, что такое новое наименьшее число?
Damien_The_Unbeliever
19
Сортируйте список [O (100 * log (100)) = O (1)] или выполните линейный поиск по минимуму [O (100) = O (1)], чтобы получить новое наименьшее число. Ваш список имеет постоянный размер, поэтому все эти операции также имеют постоянное время.
Random832
6
Вам не нужно держать весь список отсортированным. Вам все равно, что самое высокое или второе по величине число. Вам просто нужно знать, что является самым низким. Таким образом, после того, как вы вставите новое число, вы просто пересекаете 100 чисел и видите, какое из них является самым низким. Это постоянное время.
Том Зыч
27
Асимптотический порядок операции интересен только тогда , когда размер проблемы может расти неограниченно. Из вашего вопроса очень неясно, какое количество растет без ограничений; звучит так, будто вы спрашиваете, каков асимптотический порядок для задачи, размер которой ограничен на 100; это даже не разумный вопрос; что-то должно расти без границ. Если вопрос звучит так: «Можете ли вы сделать это, чтобы сохранить верхние n, а не верхние 100 за O (1) время?» тогда вопрос разумный.
Эрик Липперт

Ответы:

35

Допустим, k - это число старших чисел, которые вы хотите знать (100 в вашем примере). Затем вы можете добавить новый номер, в O(k)котором также O(1). Потому что O(k*g) = O(g) if k is not zero and constant.

duedl0r
источник
6
O (50) - это O (n), а не O (1). Вставка в список длины N в O (1) означает, что время не зависит от значения N. Это означает, что если 100 становится 10000, то 50 НЕ должно становиться 5000.
18
@hamstergene - но в случае этого вопроса Nразмер отсортированного списка или количество обработанных элементов? Если вы обрабатываете 10000 элементов и сохраняете 100 лучших элементов в списке или обрабатываете 1000000000 элементов и сохраняете 100 лучших элементов в отсортированном списке, затраты на вставку в этом списке остаются прежними.
Damien_The_Unbeliever
6
@hamstergene: В этом случае вы неправильно поняли основы. В вашей ссылке википедии есть свойство ( «Умножение на константу»): O(k*g) = O(g) if k not zero and constant. => O(50*1) = O(1).
duedl0r
9
Я думаю, что duedl0r прав. Давайте уменьшим проблему и скажем, что вам нужны только минимальные и максимальные значения. Это O (n), потому что минимум и максимум 2? (п = 2). № 2 является частью определения проблемы. Является константой, так что это ak в O (k * что-то), что эквивалентно O (что-то)
xanatos
9
@hamstergene: о какой функции ты говоришь? значение 100 кажется мне довольно постоянным ..
duedl0r
19

Держите список несортированным. Выяснение того, вставлять или нет новый номер, займет больше времени, но вставка будет O (1).

Эмилио М Бумачар
источник
7
Я думаю, что это даст вам награду умного алека, если ничего больше. * 8 ')
Марк Бут
4
@ Emilio, ты технически прав - и, конечно, это самый лучший вид…
Гарет
1
Но вы также можете оставить наименьшее из ваших 100 чисел, тогда вы также можете решить, нужно ли вам вставлять в O (1). Только тогда, когда вы введете номер, вам придется искать новый наименьший номер. Но это случается реже, чем решение вставлять или нет, что происходит для каждого нового номера.
Андрей Вайна II
12

Это просто. Размер списка постоянен, поэтому время сортировки списка постоянно. Операция, которая выполняется в постоянное время, называется O (1). Поэтому сортировка списка - это O (1) для списка фиксированного размера.

Кирк Бродхерст
источник
9

После того, как вы передадите 100 номеров, максимальная цена, которую вы когда-либо понесете за следующее число, - это стоимость проверки того, находится ли число в самых высоких 100 числах (давайте пометим это CheckTime ) плюс стоимость, чтобы ввести его в этот набор и извлечь наименьший (назовем это EnterTime ), который является постоянным временем (по крайней мере, для ограниченных чисел), или O (1) .

Worst = CheckTime + EnterTime

Затем, если распределение чисел является случайным, средняя стоимость уменьшается, чем больше у вас чисел. Например, вероятность того, что вам нужно будет ввести 101-й номер в максимальный набор, составляет 100/101, шансы на 1000-й номер будут 1/10, а шансы для n-го номера будут 100 / n. Таким образом, наше уравнение для средней стоимости будет:

Average = CheckTime + EnterTime / n

Таким образом, когда n приближается к бесконечности, важен только CheckTime :

Average = CheckTime

Если числа связаны, CheckTime является постоянным, и, следовательно, это O (1) время.

Если числа не связаны, время проверки будет расти с увеличением числа. Теоретически, это потому, что если наименьшее число в максимальном наборе становится достаточно большим, ваше время проверки будет больше, потому что вам придется учитывать больше битов. Это создает впечатление, что оно будет немного выше, чем постоянное время. Тем не менее, вы также можете утверждать, что вероятность того, что следующее число находится в самом высоком наборе, приближается к нулю, когда n приближается к бесконечности, и поэтому вероятность того, что вам потребуется учесть больше битов, также приближается к 0, что будет аргументом для O (1) время.

Я не уверен, но моя интуиция говорит, что это O (log (log (n))) время. Это связано с тем, что вероятность увеличения наименьшего числа является логарифмической, а вероятность того, что число бит, которое необходимо учитывать для каждой проверки, также является логарифмической. Меня интересуют другие народы, потому что я не совсем уверен ...

Briguy37
источник
За исключением того, что список произвольный, что если это список постоянно растущих чисел?
dan_waterworth
@dan_waterworth: Если бесконечный список является произвольным и когда-нибудь будет увеличиваться (шансы которого будут 1 / ∞!), это будет соответствовать сценарию наихудшего случая CheckTime + EnterTimeдля каждого числа. Это имеет смысл только , если числа не ограничены, и так CheckTimeи EnterTimeбудет как увеличиваться , по крайней мере , логарифмически в связи с увеличением размера цифр.
Briguy37
1
Числа не случайны, есть произвольные. Нет смысла говорить о шансах.
dan_waterworth
@dan_waterworth: Вы уже дважды говорили, что числа произвольные. Откуда ты это взял? Кроме того, я полагаю, что вы все еще можете применять статистику к произвольным числам, начиная со случайного регистра, и повышать их точность, поскольку вы больше знаете об арбитре. Например, если бы вы были арбитром, оказалось бы, что у вас будет больше шансов выбрать постоянно растущие числа, чем если бы, скажем, я был арбитром;)
Briguy37
7

это легко, если вы знаете Binary Heap Trees . Двоичные кучи поддерживают вставку в среднем постоянном времени, O (1). И дать вам легкий доступ к первым х элементов.

чокнутый урод
источник
Зачем хранить элементы, которые вам не нужны? (значения, которые являются слишком низкими) Похоже, пользовательский алгоритм является более подходящим. Не говоря, что вы не можете «не добавлять» значения, когда они не выше, чем самые низкие.
Стивен Джеурис
Я не знаю, моя интуиция говорит мне, что куча (какого-то аромата) могла бы справиться с этим довольно хорошо. Это не значит, что ему придется сохранить все элементы для этого. Я не исследовал это, но это "чувствует себя хорошо" (ТМ).
Рог
3
Куча может быть изменена так, чтобы отбрасывать что-либо ниже некоторого m-го уровня (для двоичных куч и k = 100, m будет равно 7, поскольку число узлов = 2 ^ m-1). Это замедлит его, но все равно будет амортизироваться постоянным временем.
Plutor
3
Если вы использовали двоичную min-heap (потому что тогда верх - это минимум, который вы проверяете все время), и вы нашли новое число> min, то вам нужно удалить верхний элемент, прежде чем вы сможете вставить новый , Удаление верхнего (минимального) элемента будет O (logN), потому что вы должны пройти каждый уровень дерева один раз. Таким образом, технически верно, что вставки - это среднее значение O (1), потому что на практике это значение равно O (logN) каждый раз, когда вы находите число> min.
Скотт Уитлок
1
@Plutor, вы предполагаете, что некоторые гарантии, что бинарные кучи не дают вам. Визуализируя его как двоичное дерево, может случиться так, что каждый элемент в левой ветви будет меньше, чем любой элемент в правой ветви, но вы предполагаете, что самые маленькие элементы находятся ближе всего к корню.
Питер Тейлор
6

Если из-за вопроса, который интервьюер действительно хотел задать, «можем ли мы убедиться, что каждый входящий номер обрабатывается в постоянное время», то, как уже указывалось многими (например, см. Ответ @ duedl0r), решение вашего друга уже O (1), и это было бы так, даже если бы он использовал несортированный список, или использовал сортировку по пузырькам, или что-то еще. В этом случае вопрос не имеет особого смысла, если только он не был сложным, или вы не помните его неправильно.

Я предполагаю, что вопрос интервьюера был осмысленным, что он не спрашивал, как сделать что-то, чтобы быть O (1), что, очевидно, уже так.

Поскольку сложность алгоритма опроса имеет смысл только тогда, когда размер входных данных растет бесконечно, и единственный вход, который может увеличиваться, это 100 - размер списка; Я предполагаю, что реальный вопрос заключался в том, «можем ли мы удостовериться, что мы получим Top N тратя O (1) раз на число (не O (N), как в решении вашего друга), возможно ли это?».

Первое, что приходит на ум, это подсчет сортировки, который купит сложность O (1) времени на число для задачи Top-N по цене использования пространства O (m), где m - длина диапазона входящих чисел. , Так что да, это возможно.

hamstergene
источник
4

Используйте очередь с минимальным приоритетом, реализованную с кучей Фибоначчи , которая имеет постоянное время вставки:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)
Гейб Моутарт
источник
4
«Операции удаления и удаления минимального объема работы в O(log n)амортизированном времени» , поэтому это все равно приведет к тому, O(log k)где kбудет храниться количество элементов.
Стивен Джеурис
1
Это ничем не отличается от ответа Эмилио, который получил название «Награда умного алека», поскольку минус удаления работает в O (log n) (согласно Википедии).
Николь
@ Возрождение Эмилио ответит O (k), чтобы найти минимум, мой - O (log k)
Гейб Моутарт
1
@ Достаточно честно, я просто имею в виду. Другими словами, если вы не берете 100, чтобы быть константой, то этот ответ также не является постоянным временем.
Николь
@Renesis Я удалил (неправильное) утверждение из ответа.
Гейб Моутарт
2

Задача состоит в том, чтобы найти алгоритм O (1) длины N необходимого списка чисел. Так что не имеет значения, если вам нужны первые 100 или 10000 номеров, время вставки должно быть O (1).

Хитрость заключается в том, что хотя требование O (1) упомянуто для вставки списка, в вопросе ничего не сказано о порядке времени поиска во всем числовом пространстве, но оказывается, что это можно сделать O (1) также. Решение тогда следующее:

  1. Организовать хеш-таблицу с номерами для ключей и парами связанных списков указателей для значений. Каждая пара указателей является началом и концом последовательности связанных списков. Обычно это будет просто один элемент, затем следующий. Каждый элемент в связанном списке идет рядом с элементом со следующим наибольшим номером. Таким образом, связанный список содержит отсортированную последовательность требуемых номеров. Сохраните запись с наименьшим номером.

  2. Возьмите новое число x из случайного потока.

  3. Это выше, чем последнее записанное наименьшее число? Да => Шаг 4, Нет => Шаг 2

  4. Нажмите на хэш-таблицу с только что взятым номером. Есть ли запись? Да => Шаг 5. Нет => Возьмите новый номер x-1 и повторите этот шаг (это простой линейный поиск вниз, просто потерпите меня здесь, это можно улучшить, и я объясню как)

  5. С элементом списка, только что полученным из хеш-таблицы, вставьте новый номер сразу после элемента в связанном списке (и обновите хеш)

  6. Возьмите наименьшее записанное число l (и удалите его из хэша / списка).

  7. Нажмите на хэш-таблицу с только что взятым номером. Есть ли запись? Да => Шаг 8. Нет => Возьмите новое число l + 1 и повторите этот шаг (это простой линейный поиск вверх)

  8. При положительном попадании число становится новым самым низким числом. Перейти к шагу 2

Чтобы учесть дублирующиеся значения, хешу фактически необходимо поддерживать начало и конец последовательности связанного списка элементов, которые являются дубликатами. Таким образом, добавление или удаление элемента в данном ключе увеличивает или уменьшает указанный диапазон.

Вставка здесь - O (1). Упомянутые поиски, я думаю, что-то вроде, O (средняя разница между числами). Средняя разница увеличивается с размером пространства чисел, но уменьшается с требуемой длиной списка чисел.

Таким образом, стратегия линейного поиска довольно плохая, если числовое пространство велико (например, для 4-байтового типа int, от 0 до 2 ^ 32-1) и N = 100. Чтобы обойти эту проблему производительности, вы можете сохранить параллельные наборы хеш-таблиц, где числа округляются до более высоких величин (например, 1 с, 10 с, 100 с, 1000 с), чтобы получить подходящие ключи. Таким образом, вы можете увеличивать и уменьшать скорость, чтобы быстрее выполнять требуемые поиски. Я думаю, что производительность становится O (логарифмический диапазон), который является постоянным, то есть O (1) также.

Чтобы сделать это более понятным, представьте, что у вас есть номер 197 на руках. Вы попали в хэш-таблицу 10 с '190', она округляется до ближайшей десятки. Что-нибудь? Нет. Таким образом, вы понижаетесь в 10 с, пока не нажмете, скажем, 120. Затем вы можете начать с 129 в хэш-таблице 1 с, затем пробовать 128, 127, пока не нажмете что-нибудь. Теперь вы нашли, где в связанном списке вставить число 197. При его вставке необходимо также обновить хеш-таблицу 1 с записью 197, хеш-таблицу 10 с числом 190, 100 с 100 и т. Д. Большинство шагов Вы когда-либо должны сделать здесь в 10 раз журнал диапазона номеров.

Возможно, я ошибся в некоторых деталях, но так как это обмен программистами, а контекстом были интервью, я надеюсь, что вышеизложенное является достаточно убедительным ответом для такой ситуации.

РЕДАКТИРОВАТЬ Я добавил некоторые дополнительные детали, чтобы объяснить схему параллельной хеш-таблицы и то, как это означает, что упомянутые мной плохие линейные поиски могут быть заменены поиском O (1). Я также понял, что, конечно, нет необходимости искать следующий наименьший номер, потому что вы можете перейти прямо к нему, посмотрев в хеш-таблицу с наименьшим номером и перейдя к следующему элементу.

Бенедикт
источник
1
Поиск должен быть частью функции вставки - они не являются независимыми функциями. Поскольку ваш поиск O (n), ваша функция вставки также O (n).
Кирк Бродхерст
Нет. Используя стратегию, которую я описал, где больше хеш-таблиц используются для более быстрого прохождения пространства чисел, это O (1). Пожалуйста, прочитайте мой ответ еще раз.
Бенедикт
1
@Benedict, ваш ответ совершенно ясно говорит о том, что он выполняет линейные поиски в шагах 4 и 7. Линейные поиски не являются O (1).
Питер Тейлор
Да, это так, но я разберусь с этим позже. Не могли бы вы на самом деле читать остальные, пожалуйста. При необходимости я отредактирую свой ответ, чтобы сделать его совершенно ясным.
Бенедикт
@Benedict Вы правы - исключая поиск, ваш ответ O (1). К сожалению, это решение не будет работать без поиска.
Кирк Бродхерст
1

Можем ли мы предположить, что числа имеют фиксированный тип данных, например, Integer? Если так, то ведите подсчет каждого добавленного числа. Это операция O (1).

  1. Объявите массив с максимально возможным количеством элементов:
  2. Читайте каждый номер, как он транслируется.
  3. Подсчет числа. Игнорируйте, если это число уже подсчитано 100 раз, так как оно вам никогда не понадобится. Это предотвращает подсчет переполнения бесконечное количество раз.
  4. Повторите с шага 2.

Код VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Когда вы возвращаете список, вы можете занять столько времени, сколько захотите. Просто перейдите от конца списка и создайте новый список из 100 самых высоких зарегистрированных значений. Это операция O (n), но это не имеет отношения к делу.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Изменить: На самом деле, это не имеет значения, если это фиксированный тип данных. Поскольку нет никаких ограничений на потребление памяти (или жесткого диска), вы можете сделать это для любого диапазона натуральных чисел.

Hand-E-Food
источник
1

Сотни чисел легко сохраняются в массиве размером 100. Любое дерево, список или набор излишни, учитывая поставленную задачу.

Если входящий номер больше самого низкого (= последнего) в массиве, запустите все записи. Как только вы найдете первый номер, который меньше вашего нового номера (для этого вы можете использовать причудливый поиск), пропустите остаток массива, нажимая каждую запись «вниз» на единицу.

Поскольку вы сохраняете список отсортированным с самого начала, вам не нужно запускать какой-либо алгоритм сортировки вообще. Это O (1).

Йорг З.
источник
0

Вы можете использовать бинарную Max-Heap. Вы должны будете отслеживать указатель на минимальный узел (который может быть неизвестным / нулевым).

Вы начинаете, вставляя первые 100 чисел в кучу. Макс будет на вершине. После этого вы всегда будете хранить там 100 номеров.

Затем, когда вы получите новый номер:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

К сожалению, findMinimumNodeэто O (n), и вы несете эту стоимость один раз за вставку (но не во время вставки :). Удаление минимального узла и вставка нового узла, в среднем, O (1), потому что они будут стремиться к нижней части кучи.

Если пойти по другому пути с бинарной мини-кучей, min находится сверху, что отлично подходит для нахождения минимума для сравнения, но отстой, когда нужно заменить минимум новым числом, которое> min. Это потому, что вы должны удалить минимальный узел (всегда O (logN)), а затем вставить новый узел (средний O (1)). Итак, у вас все еще есть O (logN), который лучше, чем Max-Heap, но не O (1).

Конечно, если N постоянно, то у вас всегда есть O (1). :)

Скотт Уитлок
источник