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

Чтобы решить вопрос о 2 (и 3) пропущенных числах, вы можете изменить quickselect, который в среднем работает в O(n) и использует постоянную память, если разбиение выполняется на месте.

1. Разбить набор относительно случайного центра p на разбиения l, которые содержат числа, меньшие, чем точка, и r, которые содержат числа, большие, чем центр.

2. Определите, в каких разделах находятся 2 пропущенных числа, сравнивая значение сводной диаграммы с размером каждого раздела (p - 1 - count(l) = count of missing numbers in l и n - count(r) - p = count of missing numbers in r)

3. a) Если в каждом разделе отсутствует одно число, используйте подход с разностью сумм, чтобы найти каждое отсутствующее число.

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1 и ((p+1) + (p+2) ... + n) - sum(r) = missing #2

   b) Если в одном разделе отсутствуют оба числа, а раздел пуст, то пропущенные числа: (p-1,p-2) или (p+1,p+2) в зависимости от того, в каком разделе пропущены цифры.

   Если в одном разделе пропущены 2 числа, но он не пустой, выполните возврат в этот раздел.

При наличии только 2 пропущенных чисел этот алгоритм всегда отбрасывает хотя бы один раздел, поэтому он сохраняет O(n) среднюю сложность быстрого выбора. Точно так же с 3 пропущенными числами этот алгоритм также отбрасывает по крайней мере один раздел с каждым проходом (потому что как с 2 пропущенными числами, самое большее только 1 раздел будет содержать несколько пропущенных чисел). Однако я не уверен, насколько снижается производительность при добавлении новых пропущенных чисел.

Вот реализация, которая не использует разделение на месте, поэтому этот пример не соответствует требованию к пространству, но иллюстрирует шаги алгоритма:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Демо

Answer 2

Можете ли вы проверить, существует ли каждый номер? Если да, вы можете попробовать это:

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

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

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

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

Answer 3

Может быть, этот алгоритм может работать для вопроса 1:

1. Предварительно вычислить xor первых 100 целых чисел (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
2. или для элементов, поступающих из входного потока (val1 = val1 ^ next_input)
3. окончательный ответ = val ^ val1

Или даже лучше:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Этот алгоритм фактически может быть расширен для двух пропущенных чисел. Первый шаг остается прежним. Когда мы вызываем GetValue с двумя пропущенными числами, результатом будет a1^a2 - два пропущенных числа. Скажем

val = a1^a2

Теперь, чтобы отсеять a1 и a2 от val, мы берем любой установленный бит в val. Допустим, бит ith установлен в значение val. Это означает, что a1 и a2 имеют разную четность в битовой позиции ith. Теперь мы делаем еще одну итерацию для исходного массива и сохраняем два значения xor. Один для чисел, у которых установлен i-й бит, а другой - без установленного i-го бита. Теперь у нас есть два блока чисел, и мы гарантируем, что a1 and a2 будет лежать в разных сегментах. Теперь повторите то же самое, что мы сделали для нахождения одного пропущенного элемента в каждом ведре.

Answer 4

Вы можете решить Q2, если у вас есть сумма обоих списков и произведение обоих списков.

(l1 - оригинал, l2 - модифицированный список)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

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

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Теперь мы знаем, что (если a и b - удаленные числа):

a + b = d
a * b = m

Таким образом, мы можем переставить:

a = s - b
b * (s - b) = m

И умножить:

-b^2 + s*b = m

И переставить так, чтобы правая сторона была равна нулю:

-b^2 + s*b - m = 0

Тогда мы можем решить с помощью квадратной формулы:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Пример кода Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Я не знаю сложности функций sqrt, Reduce и Sum, поэтому я не могуВыясните сложность этого решения (если кто-то знает, пожалуйста, прокомментируйте ниже.)

Answer 5

Для Q2 это решение, которое немного более неэффективно, чем другие, но все еще имеет время выполнения O (N) и занимает пространство O (k).

Идея состоит в том, чтобы запустить оригинальный алгоритм два раза. В первом из них вы получаете общее число, которое отсутствует, что дает вам верхнюю границу пропущенных чисел. Давайте назовем этот номер N. Вы знаете, что пропущенные два числа будут суммироваться до N, поэтому первое число может быть только в интервале [1, floor((N-1)/2)], тогда как второе будет в [floor(N/2)+1,N-1].

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

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

Answer 6

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

Допущения в форме ввода:

Количество чисел в сумке = n

Количество пропущенных чисел= k

Числа в сумке представлены массивом длины n

Длина входного массива для алгоритма = n

Отсутствующие записи в массиве (взятые числаиз пакета) заменяются значением первого элемента в массиве.

Например.Изначально сумка выглядит как [2,9,3,7,8,6,4,5,1,10].Если выбрано 4, значение 4 станет 2 (первый элемент массива).Следовательно, после извлечения 4 сумка будет выглядеть как [2,9,3,7,8,6,2,5,1,10]

Ключом к этому решению является пометка INDEX посещаемогочисло путем отрицания значения в этом INDEX, когда массив пройден.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

Answer 7

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

• Создание массива a размера u = k^2.
• Выбор любой универсальной хеш-функции, h : {1,...,n} -> {1,...,u}.(Как кратное смещение )
• Для каждого i в 1, ..., n увеличение a[h(i)] += i
• Для каждого числа x во входном потоке, уменьшение a[h(x)] -= x.

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

Вероятность того, чтоконкретная пара отправляется в одно и то же ведро, меньше чем 1/u по определению универсальной хеш-функции.Поскольку существует около k^2/2 пар, мы имеем вероятность ошибки не более k^2/2/u=1/2.То есть мы добиваемся успеха с вероятностью не менее 50%, и если мы увеличиваем u, мы увеличиваем наши шансы.

Обратите внимание, что этот алгоритм занимает k^2 logn бит пространства (нам нужно logn бит на массивведро.) Это соответствует пространству, требуемому для ответа @Dimitris Andreou (В частности, требование к пространству для полиномиальной факторизации, которая также бывает рандомизированной.) Этот алгоритм также имеет постоянное время на обновление, а не время k в случаесуммы мощности.

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

Answer 8

Возможно, вам понадобится уточнить, что означает O (k).

Вот тривиальное решение для произвольного k: для каждого v в вашем наборе чисел накапливайте сумму 2 ^ v.В конце, цикл i от 1 до N. Если сумма поразрядно ANDed с 2 ^ i равна нулю, то i отсутствует.(Или численно, если пол суммы, деленной на 2 ^, четен. Или sum modulo 2^(i+1)) < 2^i.)

Легко, верно?O (N) время, O (1) хранилище, и оно поддерживает произвольные значения k.

За исключением того, что вы вычисляете огромные числа, которые на реальном компьютере каждый потребует O (N) места.На самом деле, это решение идентично битовому вектору.

Таким образом, вы можете быть умнее и вычислить сумму и сумму квадратов и сумму кубов ... с точностью до суммы v ^ k, исделать причудливую математику, чтобы извлечь результат.Но это тоже большие цифры, поэтому возникает вопрос: о какой абстрактной модели работы идет речь?Сколько места в O (1) пространстве и сколько времени нужно, чтобы сложить числа любого нужного вам размера?

Answer 9

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

Например,может случиться так, что интервьюер собирается отправлять n сообщения и ему нужно знать k, который не привел к ответу, и ему нужно знать его как можно быстрее после n-k thответ приходит.Давайте также скажем, что характер канала сообщений таков, что даже при работе на полную длину у вас есть достаточно времени для некоторой обработки между сообщениями без какого-либо влияния на время, необходимое для получения конечного результата после получения последнего ответа.Это время можно использовать для вставки некоторого идентифицирующего аспекта каждого отправленного сообщения в набор и удаления его по мере поступления каждого соответствующего ответа.После получения последнего ответа единственное, что нужно сделать, это удалить его идентификатор из набора, что в типичных реализациях занимает O(log k+1).После этого набор содержит список k пропущенных элементов, и дополнительная обработка не требуется.

Это, безусловно, не самый быстрый подход для пакетной обработки предварительно сгенерированных пакетов чисел, потому что все этоработает O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)).Но оно работает для любого значения k (даже если оно не известно заранее) и в приведенном выше примере оно было применено таким образом, чтобы минимизировать самый критический интервал.

Answer 10

Вы можете попробовать использовать Bloom Filter .Вставьте каждый номер в сумке в цвету, затем итерируйте полный набор 1-k, пока не сообщите о каждом не найденном.Это может не найти ответ во всех сценариях, но может быть достаточно хорошим решением.