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

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

Достаточно странно, вопрос заключается в том, чтобы определить НЕ СУЩЕСТВОВАНИЕ значения, а не его существования.

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Не уверен, как несколько дисков могут быть использованы для преимущества в этом подходе, хотя ...

Answer 5

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Я все еще придерживаюсь рассуждений выше, что также еще лучше подтверждается ответом Морон.Тем не менее, сделав вывод, посмотрев на Bloom Filter из ответа Патрика, я считаю, что интервьюер, возможно, рассматривал этот и другие вероятностные алгоритмы (которые должны были быть отмечены в вопросе об интервью).

Answer 6

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

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

Answer 7

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

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

Answer 8

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

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

Answer 9

Я думаю, что проблема ясно утверждает, что вы дали список размером 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).

Answer 10

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