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

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

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

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

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

В этот момент я подумал, что у меня все хорошо, но вопрос неожиданно обернулся неожиданно:

Q2: Это правильно, но теперь, как бы вы это сделали, еслиДВА номера отсутствуют?

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

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

Ответ интервьюера удивил меня: вы можете обобщить технику, чтобы найти 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 пропущенные цифры как-то.