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

Ответ 1

Как ни странно, вопрос состоит в том, чтобы определить НЕ-СУЩЕСТВУЮЩЕЕ значение, а не существование.

Это может означать, что они относятся к фильтру Bloom (http://en.wikipedia.org/wiki/Bloom_filter). Фильтр Bloom может рассказать вам, есть ли элемент:

• не существует
• или, возможно, существует

Ответ 2

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

N достаточно большой, чтобы охватить несколько дисков

Теперь, если вы хотите найти или определить отсутствие номера, вы можете просто спросить у лиц, находится ли номер, который вы ищете, на карте, на которой они держатся.

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

Я не знаю много о физике (скорость звука, трение воздуха, время для каждого человека, мозг смотреть на свою карточку и т.д.)

Ответ 3

Если использовать только сравнения, мы имеем нижнюю границу Omega (log N) (худший случай) (т.е. O (1) невозможно).

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

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

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

Как уже упоминалось в другом ответе, вы можете сделать вероятностный поиск по постоянному времени, который дает вам правильный ответ с разумной вероятностью, например. используя цветные фильтры.

Ответ 4

В письме вопроса они, вероятно, ищут интерполяционный поиск, который является средним случаем O (log log n). Да, это O (n) в худшем случае, но его можно улучшить с помощью знания распределения или использования интерполяционно-двоичного поиска.

Это воспроизводится в подсказке M → N. Средний анализ случая для поиска интерполяции довольно сложный, поэтому я даже не буду пытаться модифицировать при M → N. Но концептуально, при M → N и предполагая равномерное распределение, вы можете предположить, что значение будет ограничено +/- 1 начальной позиции поиска, что дает O (1).

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

Не знаю, как использовать несколько дисков для использования в этом подходе, хотя...

Ответ 5

Первый взгляд

M → N - это не подсказка, я думаю, она просто препятствует созданию растрового изображения, которое прямо скажет вам в O (1) раз, если число существует.

Я думаю, что здравомыслящее предположение с N, охватывающим несколько жестких дисков, - это то, что вы можете ожидать, что у вас не будет порядка magnitutde больше дисков в вашем распоряжении. Поскольку для производительности O (1) потребуется 2 ^M а если N охватывает несколько дисков, то M охватывает → несколько дисков и 2 ^M охватывает → диски, чем доступно,

Кроме того, он сообщает вам, что подход к хранению недостающих чисел будет неэффективным, так как тогда вам нужно будет хранить X-номера, где

X = M - N = > X ~ M (так как M → N)

что является худшим случаем.

Итак, поначалу кажется, что вы можете доказать, что лучшего ответа нет.

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

Ответ 6

Если все, что мы можем сделать, это сравнить, то, как указано выше, мы не можем сделать лучше, чем O (log (N)).

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

Ответ 7

Так как мы знаем диапазон чисел (M), мы можем выполнить интерполированный бинарный поиск. Вместо того, чтобы делить пополам диапазон поиска на 1/2, разделите его на N/(HI-LO). Результат будет по-прежнему O (log N), но с более низкой константой. Этот метод работает лучше, если мы знаем, что в данных нет дубликатов, и, похоже, вопрос подсказывает, что это может быть так, но оно не является окончательным.

Смотрите, например, этот блог: Быстрее, чем двоичный поиск

Ответ 8

Ну, согласно моим знаниям. В этой проблеме вы можете воспользоваться двумя подсказками. 1. Числа сортируются и 2. N и M очень большие (N → M), а M охватывает несколько дисков

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

Ответ 9

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

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

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

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

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

Ответ 10

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

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

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

Фильтры Bloom - это операции с постоянным временем после создания фильтра. Но, чтобы компенсировать ложные срабатывания, нужно выполнить двоичный поиск (или даже интерполяционный поиск, например, кто-то предложил предполагать равномерное распределение) будет способствовать увеличению коэффициента, чем константа log (n) в случае двоичного поиска.

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

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

Ответ 11

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

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

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

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

Ответ 12

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

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

Ответ 13

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

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

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

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

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

Ответ 14

Вопрос не о существовании, поэтому нет необходимости искать в дисках. Мы можем проверить, не является ли число X вне всего круга min и max в 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

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

Ответ 15

вы можете решить этот вопрос, проверив размер файла, который содержит номер, а затем создайте номер, размер которого больше размера файла (не говоря о abt int или lar

Ответ 16

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

const int N = 15;
int xs[N] = {1, 3, 7, 9, 13, 16, 17, 19, 21, 24, 25, 26, 27, 28, 30};

Вы должны ответить на один запрос (менее чем на O(logN)), и поэтому вы не можете выполнить какую-либо предварительную обработку. Я полагаю, что вопрос был бы сформулирован по-разному в таком случае, если бы вы могли потратить на амортизацию.

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

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

Это по существу x / M * N, в коде может быть что-то вроде этого:

double hint = static_cast<double>(x) / M; // between [0,1)
int m = static_cast<int>(hint * N); // guess the position in xs
// do binary search using m as initial "middle" point.

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