Простой вопрос интервью усложнился: по номерам 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

Еще один способ - использовать фильтрацию остаточных графов.

Предположим, у нас есть числа от 1 до 4, а 3 отсутствует.Двоичное представление выглядит следующим образом:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

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

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Обратите внимание, что потоковый граф содержит х узлов, а х - количество битов.И максимальное количество ребер (2 * х) -2.

Таким образом, для 32-разрядного целого числа потребуется O (32) пробел или O (1) пробел.

Теперь, если я уберу емкость для каждого числа, начиная с 1,2,4, тогда яосталось с остаточным графом.

0 ----------> 1 ---------> 1

Наконец, я выполню цикл, подобный следующему:

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Теперь результат в result содержит числа, которые также не пропущены(ложно положительный).Но k <= (размер результата) <= n </strong> при наличии k пропущенных элементов.

Я еще раз пройду по указанному списку, чтобы отметить пропущенный результат или нет.

Таким образом, сложность времени будет O (n).

Наконец, этоМожно уменьшить количество ложных срабатываний (и необходимое пространство), взяв узлы 00, 01, 11, 10 вместо просто 0 и 1.

Answer 2

Очень хорошая проблема.Я бы пошел за использование разницы набора для Qk.Многие языки программирования даже поддерживают его, как в Ruby:

missing = (1..100).to_a - bag

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

Answer 3

Вы можете мотивировать решение, думая об этом с точки зрения симметрии (группы, на языке математики). Независимо от порядка набора чисел, ответ должен быть одинаковым. Если вы собираетесь использовать функции k для определения отсутствующих элементов, вам следует подумать о том, какие функции имеют это свойство: симметричное. Функция s_1(x) = x_1 + x_2 + ... + x_n является примером симметричной функции, но есть и другие, более высокой степени. В частности, рассмотрим элементарные симметричные функции . Элементарная симметричная функция степени 2 равна s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n, сумме всех произведений двух элементов. Аналогично для элементарных симметрических функций степени 3 и выше. Они явно симметричны. Кроме того, оказывается, что они являются строительными блоками для всех симметричных функций.

Вы можете строить элементарные симметричные функции по ходу, отметив, что s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Дальнейшие размышления должны убедить вас, что s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1)) и так далее, чтобы их можно было вычислить за один проход.

Как нам определить, какие элементы отсутствовали в массиве? Подумайте о полиноме (z-x_1)(z-x_2)...(z-x_n). Он оценивается как 0, если вы введете любое из чисел x_i. Разложив полином, вы получите z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Здесь также появляются элементарные симметричные функции, что неудивительно, поскольку полином должен оставаться неизменным, если мы применим любую перестановку к корням.

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

Наконец, если нас беспокоит переполнение памяти большими числами (n-й симметричный многочлен будет порядка 100!), мы можем выполнить эти вычисления mod p, где p - простое число больше 100. В этом случае мы оцениваем полином mod p и находим, что он снова оценивается в 0, когда вход является числом в наборе, и он оценивается как ненулевое значение, когда вход является числом, не входящим в набор. Однако, как отмечали другие, чтобы получить значения из полинома во времени, которое зависит от k, а не N, мы должны разложить полином mod p.

Answer 4

Для разных значений k подход будет другим, поэтому не будет общего ответа в терминах k.Например, для k = 1 можно воспользоваться суммой натуральных чисел, но для k = n / 2 нужно использовать какой-то набор битов.Точно так же для k = n-1 можно просто сравнить единственное число в сумке с остальными.

Answer 5

Попробуйте найти произведение чисел от 1 до 50:

Пусть произведение, P1 = 1 х 2 х 3 х ............. 50

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

Произведение двух сгущающихся членов, a x b = P1 - P2.

Вы уже знаете сумму, a + b = S1.

Из приведенных выше двух уравнений решите для a и b квадратное уравнение. a и b - ваши пропущенные числа.

Answer 6

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

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

Answer 7

Я написал код, используя Java 8 и до Java 8. Он использует формулу: (N * (N + 1)) / 2 для суммы всех чисел.

Answer 8

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

import random

K = 2
missingNums = range(0, 101)
incompleteList = range(0, 101)

#Remove K numbers
for i in range(K):
    valueToRemove = random.choice(incompleteList)
    incompleteList.remove(valueToRemove)

dummyVariable = [missingNums.remove(num) for num in p if num in missingNums]

print missingNums

Answer 9

Я полагаю, что у меня есть O(k) время и O(log(k)) пространство алгоритма, учитывая, что у вас есть функции floor(x) и log2(x) для произвольно больших целых чисел:

У вас есть k -битное длинное целое число (отсюда и пробел log8(k)), где вы добавляете x^2, где x - следующее число, которое вы найдете в сумке: s=1^2+2^2+... Это занимает O(N) время (что не является проблемой для интервьюера). В конце вы получите j=floor(log2(s)), что является самым большим числом, которое вы ищете. Затем s=s-j и вы снова делаете выше:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Теперь у вас обычно нет функций floor и log2 для 2756 -битных целых чисел, но вместо этого для двойных. Так? Проще говоря, для каждых 2 байтов (или 1, или 3, или 4) вы можете использовать эти функции для получения желаемых чисел, но это добавляет коэффициент O(N) к сложности времени

Answer 10

Предположим, что это массив от 1 до N, а его элементы a1, a2, ...., aN:

1+N=N+1;
2+N-1=N+1;

..... Таким образом, сумма здесь уникальна.Мы можем просканировать массив с начала и с конца, чтобы добавить оба элемента.Если сумма N + 1;тогда ладно, иначе они отсутствуют.

for (I <= N/2) {
    temp = a[I] + a[n-I];
    if (temp != N+1) then
        Find the missing number or numbers
}

Повторяйте этот цикл, и вы легко получите ответ.