Простой вопрос интервью усложнился: по номерам 1..100 найдите пропущенные числа, по которым точно k отсутствуют

Question

Некоторое время назад у меня был интересный опыт собеседования.Вопрос начался очень просто:

Q1 : у нас есть сумка с номерами 1, 2, 3,…, 100.Каждый номер появляется ровно один раз, поэтому есть 100 номеров.Теперь один номер случайно выбирается из сумки.Найдите пропущенное число.

Я, конечно, уже слышал этот вопрос на собеседовании, поэтому очень быстро ответил так:

A1 : Ну, сумма чисел 1 + 2 + 3 + … + N равна (N+1)(N/2) (см. Википедия: сумма арифметических рядов ).Для N = 100 сумма составляет 5050.

Таким образом, если в сумке присутствуют все числа, сумма будет точно 5050.Так как отсутствует одно число, сумма будет меньше этой, а разница в этом числе.Таким образом, мы можем найти это пропущенное число во O(N) времени и O(1) пространстве.

В этот момент я думал, что у меня все получилось, но внезапно вопрос принял неожиданный поворот:

Q2 : Это правильно, но как теперь это сделать, если пропущено TWO номеров?

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

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

Ответ интервьюера удивил меня: вы можете обобщить технику, чтобы найти 3 пропущенных числа.На самом деле, вы можете обобщить его, чтобы найти k пропущенных чисел.

Qk : если точно k чисел отсутствует вКак бы вы нашли это эффективно?

Это было несколько месяцев назад, и я до сих пор не могу понять, что это за техника.Очевидно, существует нижняя граница времени Ω(N), поскольку мы должны отсканировать все числа хотя бы один раз, но интервьюер настаивал на сложности ВРЕМЯ и ПРОСТРАНСТВО сложности метода решения (минус O(N) время сканирования сканирования) определяется в k не N .

Так что вопрос здесь прост:

• Как бы вырешить Q2 ?
• Как бы вы решили Q3 ? ​​
• Как бы вы решили Qk ?

---

Пояснения

• Как правило, существует N чисел от 1 .. N , а не только 1..100.
• Я не ищу очевидного решения, основанного на множествах, например, с использованием набора битов , кодирующего присутствие / отсутствие каждого числа значением назначенного бита, поэтому с использованием O(N) битовдополнительное пространствоМы не можем позволить себе дополнительное пространство, пропорциональное N .
• Я также не ищу очевидного подхода первого порядка.Этот и основанный на множестве подходы стоит упомянуть в интервью (они просты в реализации и в зависимости от N могут быть очень практичными).Я ищу решение Святого Грааля (которое может или не может быть практичным для реализации, но, тем не менее, имеет желаемые асимптотические характеристики).

Итак, еще раз, конечно, вы должны отсканировать вход в O(N), но вы можете захватить только небольшое количество информации (определяемой в терминах k , а не N ), и затем должны каким-то образом найти пропущенные числа k .

Answer 1

Вот краткое изложение Димитриса Андреу ссылка .

Запомните сумму i-й степени, где i = 1,2, .., k.Это сводит задачу к решению системы уравнений

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

Использование тождеств Ньютона , зная b _i , позволяет вычислять

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ +a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Если развернутьполином (xa ₁ ) ... (xa _k ) коэффициенты будут точно c ₁ , ..., c _k - см. формулы Виете .Поскольку каждый полиномиальный фактор однозначно (кольцо полиномов является евклидовым доменом ), это означает, что _i однозначно определены с точностью до перестановки.

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

Однако, когда k меняется, прямой подход вычисления c ₁ , ..., c _k чрезмерно дорого, поскольку, например, c _k является произведением всех пропущенных чисел, величина n! / (nk) !.Чтобы преодолеть это, выполните вычисления в Z _q поле , где q - простое число такое, что n <= q <2n - оно существует по <a href="https://en.wikipedia.org/wiki/Bertrand's_postulate" rel="noreferrer"> постулату Бертрана .Доказательство менять не нужно, поскольку формулы все еще выполняются, а факторизация полиномов по-прежнему уникальна.Вам также нужен алгоритм для факторизации по конечным полям, например алгоритм Berlekamp или Cantor-Zassenhaus .

Псевдокод высокого уровня для константы k:

• Вычислить i-й степени заданных чисел
• Вычесть, чтобы получить суммы i-й степени неизвестных чисел.Вызовите суммы b _i .
• Используйте тождества Ньютона для вычисления коэффициентов из b _i ;называть их с _я .В основном, c ₁ = b ₁ ;c ₂ = (c ₁ b ₁ - b ₂ ) / 2;см. Википедию для точных формул
• Коэффициент многочлена x ^k -c ₁ x ^k-1 + ... + c _k .
• Корнями полинома являются необходимые числа a ₁ , ..., a _k .

Для варьирования k найдите простое число n <= q <2n, используя, например, Миллера-Рабина, и выполните шаги с уменьшением всех чисел по модулю q. </p>

РЕДАКТИРОВАТЬ: в предыдущей версии этого ответа говорилось, что вместо Z _q , где q - простое число, можно использовать конечное поле характеристики 2 (q = 2 ^ (log n)).Это не так, поскольку формулы Ньютона требуют деления на числа до k.

Answer 2

Вы найдете его, прочитав пару страниц Мутукришнан - Алгоритмы потока данных: Головоломка 1: Поиск пропущенных чисел . Он показывает именно то обобщение, которое вы ищете .Возможно, именно это прочитал ваш интервьюер и почему он задал эти вопросы.

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

---

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

Answer 3

Мы можем решить Q2 путем суммирования как самих чисел, так и квадратов чисел.

Затем мы можем уменьшить задачу до

k1 + k2 = x
k1^2 + k2^2 = y

Гдеx и y - это то, как далеко суммы находятся ниже ожидаемых значений.

Подстановка дает нам:

(x-k2)^2 + k2^2 = y

Что мы можем затем решить, чтобы определить наши пропущенные числа.*

Answer 4

Как указал @j_random_hacker, это очень похоже на Поиск дубликатов в O (n) времени и O (1) пространстве , и адаптация моего ответа там работает здесь тоже.

Предполагая, что "мешок" представлен массивом на основе 1 A[] размера N - k, мы можем решить Qk за O(N) время и O(k) дополнительное пространство.

Во-первых, мы расширяем наш массив A[] на k элементов, так что теперь он имеет размер N. Это дополнительное пространство O(k). Затем мы запускаем следующий алгоритм псевдокода:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

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

Второй цикл переставляет расширенный массив, так что если элемент x присутствует хотя бы один раз, то одна из этих записей будет в позиции A[x].

Обратите внимание, что, хотя у него есть вложенный цикл, он все равно выполняется за O(N) время - своп происходит только при наличии i, таком, что A[i] != i, и каждый своп устанавливает как минимум один элемент, такой, что A[i] == i, где это не было правдой раньше. Это означает, что общее количество перестановок (и, следовательно, общее количество выполнений тела цикла while) не более N-1.

Третий цикл печатает те индексы массива i, которые не заняты значением i - это означает, что i должно отсутствовать.

Answer 5

Я попросил 4-летнего ребенка решить эту проблему. Он отсортировал числа и затем сосчитал. Для этого требуется пространство O (пол на кухне), и оно работает так же просто, как и многие шары.

Answer 6

Не уверен, что это наиболее эффективное решение, но я бы перебрал все записи и использовал набор битов, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит.

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

Answer 7

Я не проверял математику, но подозреваю, что вычисление Σ(n^2) за тот же проход, что и вычисление Σ(n), даст достаточно информации для получения двух пропущенных чисел, также выполните Σ(n^3), если их три,и т. д.

Answer 8

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

Мы можем проанализировать временную и пространственную сложность алгоритмов sdcvvc и Dimitris Andreou.

Хранение:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

То есть l_j \in \Theta(j log n)

Общее количество использованного хранилища: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Используемое пространство: при условии, что для вычисления a^j требуется ceil(log_2 j) время, общее время:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Общее время: \Theta(kn log n)

Если это время и пространство удовлетворительное, вы можете использовать простой рекурсивный алгоритм. Пусть b! I будет i-й записью в сумке, n числом чисел перед удаления и k количество удалений. В синтаксисе Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Используемое хранилище: O(k) для списка, O(log(n)) для стека: O(k + log(n)) Этот алгоритм более интуитивен, имеет ту же сложность времени и использует меньше места.

Answer 9

Подожди минутку.Поскольку вопрос установлен, в сумке есть 100 чисел.Независимо от того, насколько велико k, проблему можно решить за постоянное время, потому что вы можете использовать набор и удалять числа из набора в самое большее 100 - k итераций цикла.100 постоянна.Множество оставшихся чисел - ваш ответ.

Если мы обобщим решение для чисел от 1 до N, ничего не изменится, кроме N не является константой, поэтому мы находимся в O (N - k) = O (Н) время.Например, если мы используем набор битов, мы устанавливаем биты в 1 за O (N) время, перебираем числа, устанавливая биты в 0 по ходу (O (Nk) = O (N)), а затем мыполучите ответ.

Мне кажется, что интервьюер спрашивал вас, как распечатать содержимое окончательного набора в O (k) времени, а не O (N) времени.Ясно, что с установленным битом вам нужно пройти через все N битов, чтобы определить, следует ли вам печатать число или нет.Однако, если вы измените способ реализации набора, вы можете распечатать числа за k итераций.Это делается путем помещения чисел в объект, который будет храниться как в хэш-наборе, так и в двусвязном списке.Когда вы удаляете объект из хеш-набора, вы также удаляете его из списка.Ответы останутся в списке, который теперь имеет длину k.

Answer 10

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

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}