Найти наличие номера в отсортированном списке за постоянное время? (Вопрос интервью)

Question

Я готовлюсь к предстоящим собеседованиям и несколько раз сталкивался с этим вопросом (дословно)

Найти или определить несуществование числа в отсортированном списке из N чисел, где числа колеблютсяM, M >> N и N достаточно большие, чтобы охватить несколько дисков.Алгоритм бить O (log n);бонусные баллы за алгоритм постоянного времени.

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

• Есть ли повторы в отсортированном списке?
• Какое отношение имеет количество дисков к N?

Один из подходов, которые я рассмотрел, заключался в бинарном поиске мин / макс каждого диска, чтобы определить диск, который должен содержать это число, если он существует, а затем бинарный поиск на самом диске.Конечно, это только на порядок ускорение, если количество дисков велико, и у вас также есть отсортированный список дисков.Я думаю, что это приведет к некоторому времени O (log log n).

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

Кроме того, «бонусные баллы за алгоритм с постоянным временем» вызывают у меня некоторое подозрение.

Есть мысли, решения или история этой проблемы?

Answer 1

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

bool not_exists=true
for each disk_i in disks:
  not_exists &&= (X <min_element(disk_i)  || X > max_element(disk_i) )
return not_exists

, если результат равен true.тогда мы можем быть уверены, что в дисках нет X.в противном случае X может быть на дисках.

Answer 2

Просто скромная мысль.

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

Предположим, у меня достаточно машин, чтобы проиндексировать все отсортированные N целых чисел, причем каждая машина содержит только фиксированное количество K документов, представляющих K из N целых чисел.

Таким образом, для любого заданного числа X сетевое время, в течение которого клиентский сервер запросов достигает узлов поиска, можно рассматривать как постоянное время;время для поискового узла для поиска документа, представляющего число X, также является постоянным временем, поскольку количество документов в каждом поисковом узле является фиксированным числом K.

Таким образом, общее время является постоянным.Однако это более или менее похоже на то, что упоминал Энрике.

Answer 3

Один аспект, который еще не был упомянут, заключается в том, что вопрос не является конкретным относительно того, какой компьютер вы используете.Делать это в постоянное время тривиально, если каждый жесткий диск просто подключен к собственному ЦП.

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

Answer 4

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

Учитывая, что решение с постоянным временем возможно с множеством предположений:

• Числа записываются последовательно
• Вы точно знаете, где начинается последовательность цифр и где она точно заканчивается (смещение диска)
• Все диски имеют одинаковый размер и имеют точные одинаковые битовые емкости
• Вы точно знаете, сколько битов может быть записано на диск

Учитывая эти предположения, просто умножьте k на размер в битах числа.Найдите в этом месте (O (1)) + смещение и считайте правильное количество бит.

Answer 5

Скорее всего, это неправильно сформулированный вопрос.

Если фильтры Блума - это тот ответ, который они искали, что, скорее всего, не нужно путать кандидата с потенциальным элементом распределенного / параллельного алгоритма.(несколько дисков).

Предполагается, что один диск

Фильтры Блума являются операциями с постоянным временем после создания фильтра.Но, чтобы компенсировать ложные срабатывания, нужно будет выполнить бинарный поиск (или даже интерполяционный поиск, как кто-то предложил предположить равномерное распределение), что будет способствовать увеличению коэффициента больше чем log (n) в случае бинарного поиска.* Итак, это O (k) + 1% * log (n).O (k) постоянное время для проверки фильтра Блума.затем при условии, что с помощью фильтра Блума используется 1% ошибок (ложных срабатываний), много раз придется выполнять бинарный поиск, чтобы убедиться, что он действительно существует.

Я не уверен, что это можно уменьшить до постоянного времени с помощью амортизированного анализа (не слишком разбирающегося там).

Answer 6

Я думаю, вы можете получить более быстрое время поиска, если позволите себе использовать некоторые метаданные.

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

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

Надеюсь, что это помогает и имеет смысл.

Отказ от ответственности: я собираюсь на обед через минуту, и поэтому я не до конца продумал это - это может быть непрактично.