Готовиться к собеседованию можно по‑разному: смотреть ролики на 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 для работы и собеседований».
Вы научитесь
? решать задачи, которые не могут решить другие программисты
? узнаете, как знание алгоритмов и структур данных помогает устроиться в топовые компании FAANG: Apple, Amazon, Netflix, Google
Эти навыки помогут вам участвовать в сложных высокооплачиваемых проектах, а также успешно подготовиться к алгоритмическим задачам на собеседованиях в топовые компании.
В экспресс-курсе нет детального разбора существующих алгоритмов — здесь то, что используется на практике чаще всего. Знание алгоритмов и структур данных — не достаточное, но необходимое условие успешного прохождения собеседований.
Курс «Алгоритмы: roadmap для работы и собеседований» доступен в любое время. Вас ждут ёмкие лекции, практические задачи, приближенные к реальным, полезная литература по теме и доступ к материалам курса на 2 года.
Сомневаетесь? Посмотрите первые две темы экспресс-курса бесплатно.
