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

Вы найдете его, прочитав пару страниц книги Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers . Он показывает именно то обобщение, которое вы ищете . Вероятно, это то, что прочитал ваш интервьюер и почему он задал эти вопросы.

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

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

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

Затем мы можем свести проблему к

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

, где x и y - насколько суммы ниже ожидаемых значений.

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

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

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

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

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

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

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

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

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

Вы можете проверить, все ли числа существуют? Если да, вы можете попробовать следующее:

S = сумма всех чисел в сумке (S <5050)
Z = сумма пропущенных чисел 5050 - S

, если пропущенные числа x и y , то:

x = Z - y и
max (x) = Z - 1

Итак, вы проверяете диапазон от 1 до max (x) и находите число

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

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

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

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

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

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

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

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

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

Произведение двух ошибочных терминов, a x b = P1 - P2.

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

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