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

Мы можем сделать Q1 и Q2 в O (log n) большую часть времени.

Предположим, что наш memory chip состоит из массива n число test tubes.И число x в пробирке представлено x milliliter химически-жидкой.

Предположим, наш процессор - laser light.Когда мы зажигаем лазер, он пересекает все трубки перпендикулярно его длине.Каждый раз, когда он проходит через химическую жидкость, светимость уменьшается на 1.И прохождение света с определенной отметкой в ​​миллилитрах - это операция O(1).

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

• равно предварительно рассчитанному значению (вычисленному, если не пропущено ни одного числа), тогда пропущенные числа больше n/2.
• Если наши выходные данные меньше, то существует по крайней мере одно пропущенное число, котороеменьше чем n/2.Мы также можем проверить, уменьшается ли светимость на 1 или 2.если оно уменьшается на 1, то одно пропущенное число меньше n/2, а другое больше n/2.Если его уменьшить на 2, то оба числа будут меньше, чем n/2.

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

Параллельные алгоритмы, которые стоит упомянуть (потому что они интересны),

• сортировка по некоторому параллельному алгоритму, например, параллельное объединение может бытьсделано в O(log^3 n) время.И затем пропущенное число может быть найдено с помощью бинарного поиска во O(log n) времени.
• Теоретически, если у нас есть n процессоров, то каждый процесс может проверить один из входов и установить некоторый флаг, который идентифицирует число (удобно в массиве).И на следующем шаге каждый процесс может проверить каждый флаг и, наконец, вывести номер, который не помечен.Весь процесс займет O(1) время.У него есть дополнительное O(n) пространство / память.

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

Answer 2

Возможное решение:

public class MissingNumber {
    public static void main(String[] args) {
        // 0-20
        int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
        printMissingNumbers(a,20);
    }

    public static void printMissingNumbers(int [] a, int upperLimit){
        int b [] = new int[upperLimit];
        for(int i = 0; i < a.length; i++){
            b[a[i]] = 1;
        }
        for(int k = 0; k < upperLimit; k++){
            if(b[k] == 0)
                System.out.println(k);
        }
    }
}

Answer 3

Допустим, объект ArrayList (myList) заполнен этими числами, и в этом случае 2 числа x и y отсутствуют. Поэтому возможное решение может быть:

int k = 1;
        while (k < 100) {
            if (!myList.contains(k)) {
                System.out.println("Missing No:" + k);
            }
            k++;
        }

Answer 4

// Size of numbers
def n=100;

// A list of numbers that is missing k numbers.
def list;

// A map
def map = [:];

// Populate the map so that it contains all numbers.
for(int index=0; index<n; index++)
{
  map[index+1] = index+1;  
}

// Get size of list that is missing k numbers.
def size = list.size();

// Remove all numbers, that exists in list, from the map.
for(int index=0; index<size; index++)
{
  map.remove(list.get(index));  
}

// Content of map is missing numbers
println("Missing numbers: " + map);