[Перевод] Лучшая задача по программированию для собеседования
Готовиться к собеседованию можно по-разному: смотреть ролики на YouTube, читать документацию, положиться на судьбу и тд. В большинстве случаев кандидатам предложат решить одну или несколько задач. В этой статье вас ждет подробный разбор реальной задачки, рекомендации к ее решению и объяснение ожиданий интервьюера от кандидатов.
Найдите любое повторяющееся число
Дано:
массив из N+1 целых чисел, который содержит элементы в диапазоне [1, N].
Найти:
любое повторяющееся число.
Вопрос очевидный, но кандидаты часто задают уточняющие вопросы, и это хорошо.
Вот что они обычно спрашивают:
Кандидат: Можно пример?
Интервьюер: [4, 3, 1, 1, 2].
Кандидат: Только одно число повторяется?
Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].
Кандидат: А там точно будут повторяющиеся числа?
Это плохой уточняющий вопрос, ведь мы уже знаем, что размер массива N+1, а уникальных элементов в нем только N, так что по принципу Дирихле каким-то кроликам придётся сидеть в одном домике.
Интервьюер: А разве может быть массив длиной N+1 с элементами в диапазоне [1, N], в котором числа не повторяются?
Кандидат понимает условия, начинает обдумывать решение и предполагает, что это довольно лёгкая задача.
Продолжаем диалог
Кандидат: Если решать в лоб, то можно проверить, встречается ли это число ещё раз в массиве.
С этого начинает каждый кандидат. Я считаю, что главное начать с какого-то более-менее оптимального решения.
Интервьюер: А есть более эффективные решения? (Можно ещё намекнуть на временную сложность)
Кандидат: Можно использовать HashMap и считать каждый элемент массива. Как только попадётся элемент, который встречается больше одного раза, это и будет наш ответ.
О, уже лучше. Мы нашли решение O (N), но всё равно слишком тривиальное. В идеале кандидат должен с него и начать.
Интервьюер: Посчитайте временную и пространственную сложность этого решения.
Кандидат: Временная сложность O (N), пространственная сложность O (N).
Пока всё хорошо, спрашиваем дальше.
Интервьюер: Можно решить эту задачу, не используя лишнее пространство?
Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.
Интервьюер: Тогда временная сложность вырастет до O (NLogN). Что ещё можно сделать?
На этом этапе кандидаты иногда думают, что это математическая задача и, например, пытаются посчитать сумму N*(N+1)/2 и т. д. В итоге запутываются и начинают решать другую задачу, в которой нужно найти недостающий и повторяющийся элемент, если в массиве только одно число повторяется дважды и элементы находятся в диапазоне [1, N], причём остальные элементы встречаются только один раз.
Сумма элементов в диапазоне нам никак не поможет, потому что мы не знаем, сколько элементов повторятся и сколько раз они повторяются. На этом этапе большинство кандидатов подвисает.
Подсказка: А если как с HashMap, только обозначать элементы индексами массива?
Кандидат: Аааааа, понятно! Если элементы находятся в диапазоне [1, N], а размер массива N+1, можно использовать индекс массива, чтобы помечать, присутствует элемент или нет. Берём число как индекс и меняем знак у числа по этому индексу на минус. Написать код? Или привести пример?
Интервьюер: Приведите пример.
Кандидат:
— Массив = [4, 1, 3, 2, 5, 4, 5, 5]
— Берём 4, переходим на 4-й индекс и меняем знак на минус
— Массив = [4, 1, 3, 2, -5, 4, 5, 5]
— Нужно взять абсолютное значение.
— Обрабатываем 1, массив = [4, -1, 3, 2, -5, 4, 5, 5]
— Обрабатываем 3, массив = [4, -1, 3, -2, -5, 4, 5, 5]
— Обрабатываем -2, массив = [4, -1, -3, -2, -5, 4, 5, 5]
— Обрабатываем -5, массив = [4, -1, -3, -2, -5, -4, 5, 5]
— Обрабатываем -4, массив = [4, -1, -3, -2, -5, -4, 5, 5], abs (-4) = 4, а число на четвёртом индексе уже отрицательное, значит число 4 встречается второй раз, это и есть наш ответ.
Интервьюер: Можете написать код?
Кандидат: Да.
Вот код:
int findAnyRepeatedNumber(int[] arr) {
for(int i = 0; i < arr.length; i++) {
int index = Math.abs(arr[i]);
if(arr[index] < 0) return index;
arr[index] = -arr[index];
}
throw new IllegalArgumentException("Invalid input array it should have elements in range [1, arr.length-1]");
}Кандидату может показаться, что он решил задачу. Но интервьюер ещё не закончил.
Интервьюер: Что если массив неизменяемый?
Кандидат: Нельзя менять входящий массив?
Интервьюер: Да.
Кандидат: А если мы изменим массив, а потом отменим изменения? Так можно?
Интервьюер: Нет. Сам по себе массив неизменяемый и нельзя использовать дополнительное пространство.
На этом этапе большинство кандидатов сдаётся. Но некоторые задают дополнительные вопросы.
Кандидат: Нам нужно решение O (N)?
Интервьюер: Сейчас у нас есть неизменяемый массив и нужно решение лучше O (N²). Как решить задачу с временной сложностью O (NLogN)?
Кандидат: Это задачка на поиск. Сложность LogN бывает у бинарного поиска или алгоритма «разделяй и властвуй». Но массив-то не отсортирован.
Подсказка: А если всё-таки применить бинарный поиск? Массив не отсортирован, но пространство поиска [1, N] отсортировано. Если сложность должна быть O (NLogN), можно выполнять операции O (N) с массивом LogN раз.
Эту подсказку кандидаты понимают редко.
Кандидат: Понимаю. Пожалуй, можно выполнить бинарный поиск повторяющегося числа. Например, можно пройтись по списку и посчитать число целых чисел от 1 до N/2. Если количество получилось больше, чем чисел в этом диапазоне, мы поймём, что повторяющееся число находится в этом диапазоне. В противном случае повторяется число из диапазона от N/2+1 до N. Когда мы поймём, в какой половине диапазона повторяющееся число, можно снова разделить диапазон пополам, и так пока не найдём само число. Временная сложность получается O (NLogN), а пространственная — O (1).
Реализация:
int findAnyRepeatedNumber(int[] arr) {
// Range [1, N]
int low = 1, high = arr.length - 1;
int duplicate = -1;
while (low <= high) {
int cur = (low + high) / 2;
int count = countLessThatOrEqual(cur, arr);
if (count > cur) {
duplicate = cur;
high = cur - 1;
} else {
low = cur + 1;
}
}
if(duplicate == -1) {
throw new IllegalArgumentException("Invalid input array it should have elements in range [1, arr.length-1]");
}
return duplicate;
}
int countLessThatOrEqual(int num, int[] arr) {
int count = 0;
for (int x : arr) {
if (x <= num)
count++;
}
return count;
}Временная сложность O (NLogN), пространственная сложность O (1)
Интервьюер: Отлично!
Интервьюер: Ещё один вопрос.
Кандидат: (про себя: Ну что ещё?!) Да?
Интервьюер: Если повторяется только одно число, можно решить задачу с временной сложностью O (N)?
Кандидат: (про себя: Вряд ли.) Дайте подумать.
На этом этапе большинство кандидатов отчаивается. А ведь поначалу задачка показалась им лёгкой! Почти всем нужна подсказка.
Курс «Алгоритмы: roadmap для работы и собеседований»
Подсказка: Про зайца и черепаху слышали?
Кандидат: Да, это алгоритм, который определяет цикл в связном списке и помогает найти начальную точку цикла.
Интервьюер: Так. В нашей задачке тоже можно увидеть цикл.
Кандидат: Где?
Интервьюер: Давайте представим, что наш массив — это связный список, в котором число по каждому индексу указывает на индекс, равный этому числу.
Кандидат: Можно пример?
Возьмём массив [2, 6, 4, 1, 3, 1, 5].
Нулевой индекс указывает на второй, второй указывает на четвёртый и так далее.
Кандидат: Понятно.
Интервьюер: Можете написать код?
Кандидат: Вот код.
int findAnyRepeatedNumber(int[] arr) {
int slow = arr[0];
int fast = arr[0];
do {
slow = arr[slow];
fast = arr[arr[fast]];
} while(slow != fast);
slow = arr[0];
while (slow != fast) {
slow = arr[slow];
fast = arr[fast];
}
return fast;
}Временная сложность O (N), пространственная сложность O (1), массив неизменяемый.
Это решение не сработает, если повторяться может несколько чисел.
Интервьюер: Ещё один вопрос.
Кандидат: (злится) С меня хватит.
Интервьюер: Да я же просто хотел спросить… когда вы сможете приступить к работе?
Это умный вопрос, потому что:
Кандидат разбирается в алгоритмах, пространственной и временной сложности и т. д.
Кандидат адаптируется к разным ограничениям и находит компромисс. Инженерам постоянно приходится работать в таких условиях, так что это важный навык.
Кандидат проявил креативность. Каждое ограничение заставляет начинать с нуля и придумывать совершенно новый подход.
Кандидат правильно смотрит на сложность. Некоторые кандидаты застревают, пытаясь найти решение с временной сложностью O (NlogN) и пространственной сложностью O (1). Им кажется, что использовать хеш или сравнивать все элементы списка с остальными элементами было бы слишком просто, поэтому они не предлагают эти банальные решения —, но и более сложные придумать не могут. Это указывает на то, что кандидат склонен чрезмерно всё усложнять. Обычно я прошу следующих интервьюеров обращать внимание на эту склонность.
Кандидат готов учиться и решать сложные задачи. Некоторые люди оживляются, когда условия задачи становятся сложнее, а другие опускают руки или ленятся прилагать усилия.
Как решать задачи, которые не могут решить другие программисты
Подготовка к собеседованию и само собеседование — то еще испытание для тех, кто только делает первые шаги в IT. В текущих реалиях не всегда достаточно знать теорию и уметь кодить. Чтобы получить долгожданный оффер и выделиться среди других соискателей, вам понадобится знание алгоритмов. В этом вам поможет наш экспресс-курс «Алгоритмы: roadmap для работы и собеседований».
Вы научитесь
