Ты уже знаешь, что алгоритмическая секция — один из самых частых стоп-факторов на пути к офферу. Давай разберёмся, как она устроена изнутри и почему здесь «сыплются» даже сильные разработчики с крутыми проектами за плечами.
Как устроена алгоритмическая секция
Ты подключаешься к видеозвонку — и начинается алгоритмическое собеседование. Давай разберём, как всё будет происходить, чтобы ты заранее понимал, что ждёт на этом этапе.
Первым делом интервьюер представится и расскажет, как будет проходить секция. Обычно проговаривают такие моменты:
- Время собеседования — 60 минут.
- Нужно решить две задачи. Первая будет проще — на неё стоит заложить около 20 минут. Вторая — посложнее, может занять до 40 минут. Если справишься раньше — могут предложить дополнительную задачу.
- Проговаривай свои мысли вслух, чтобы интервьюер понимал ход твоих рассуждений.
- Сначала расскажи идею решения и оцени сложность по времени и памяти — только после этого переходи к написанию кода.
После этого интервьюер озвучивает тебе условие первой задачи.
Условие задачи
Дан массив целых чисел numstruefalse
Пример 1:
Ввод: nums = [1,3,3,4] Вывод: true Объяснение: элемент со значением 3 встречается дважды — на индексах 1 и 2.
Пример 2:
Ввод: nums = [1,2,3,4] Вывод: false Объяснение: все элементы уникальны.
Опытные кандидаты начинают с этого…
Первым делом стоит задать уточняющие вопросы. Например: “В примерах массив отсортирован. Это всегда так или это случайность?”
В зависимости от ответа на этот вопрос будут разные варианты решения. Умение задавать правильные вопросы — ключевой навык опытных кандидатов.
Если массив отсортирован, интервьюер ожидает такое решение:
// Время: O(n), где n — размер массива.
// Память: O(1).
function contains_duplicate(nums) {
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) {
return true;
}
}
return false;
}// Время: O(n), где n — размер массива.
// Память: O(1).
bool ContainsDuplicate(List<int> nums) {
for (int i = 1; i < nums.Count; i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}// Время: O(n), где n — размер массива.
// Память: O(1).
#include <vector>
using namespace std;
bool contains_duplicate(const vector<int>& nums) {
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}// Время: O(n), где n — размер массива.
// Память: O(1).
func containsDuplicate(nums []int) bool {
for i := 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return true
}
}
return false
}// Время: O(n), где n — размер массива.
// Память: O(1).
boolean containsDuplicate(List<Integer> nums) {
for (int i = 1; i < nums.size(); i++) {
if (nums.get(i).equals(nums.get(i - 1))) {
return true;
}
}
return false;
}# Время: O(n), где n — размер массива.
# Память: O(1).
def contains_duplicate(nums: List[int]) -> bool:
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return True
return FalseЕсли массив не отсортирован — понадобится другой подход:
// Время: O(n), где n — размер массива.
// Память: O(n).
bool ContainsDuplicate(List<int> nums) {
Dictionary<int, bool> used = new Dictionary<int, bool>();
foreach (int num in nums) {
if (used.ContainsKey(num)) {
return true;
}
used[num] = true;
}
return false;
}// Время: O(n), где n — размер массива.
// Память: O(n).
#include <vector>
#include <unordered_map>
using namespace std;
bool contains_duplicate(const vector<int>& nums) {
unordered_map<int, bool> used;
for (int num : nums) {
if (used.count(num)) {
return true;
}
used[num] = true;
}
return false;
}// Время: O(n), где n — размер массива.
// Память: O(n).
func containsDuplicate(nums []int) bool {
used := make(map[int]bool)
for _, num := range nums {
if used[num] {
return true
}
used[num] = true
}
return false
}// Время: O(n), где n — размер массива.
// Память: O(n).
boolean containsDuplicate(List<Integer> nums) {
Map<Integer, Boolean> used = new HashMap<>();
for (int num : nums) {
if (used.containsKey(num)) {
return true;
}
used.put(num, true);
}
return false;
}# Время: O(n), где n — размер массива.
# Память: O(n).
def contains_duplicate(nums: List[int]) -> bool:
used = dict()
for num in nums:
if num in used:
return True
used[num] = True
return False// Время: O(n), где n — размер массива.
// Память: O(n).
function contains_duplicate(nums) {
const used = {};
for (const num of nums) {
if (num in used) {
return true;
}
used[num] = true;
}
return false;
}Согласись, теперь ты точно будешь обращать внимание на такие детали. Один маленький нюанс в задаче — и решение может измениться кардинально.
Именно такому подходу мы будем обучать тебя: не просто решать конкретную задачу, а вырабатывать навык, который позволяет уверенно разбираться даже в сложных задачах и выходить победителем.
Допустим, массив не отсортирован
Пусть интервьюер сказал, что массив не отсортирован. Тогда тебе нужно озвучить идею решения примерно так:
Так как массив не отсортирован, будем использовать хеш-сет для оптимального решения. Идея простая: проходим по каждому элементу массива и проверяем — встречался ли он раньше. Если встречался — возвращаем true, если нет — добавляем в хеш-сет и двигаемся дальше. Если дошли до конца — возвращаем false.
После этого стоит сразу проговорить оценку сложности:
Решение работает за O(n) по времени и O(n) по памяти, где n — размер массива nums
Если ты пока не знаешь, что такое O(n)
Пройти собеседование без знания Big-O практически невозможно — это базовый вопрос, поэтому мы обязательно подробно разберем в следующих уроках.
Наконец — пишем код
Когда ты озвучил идею решения и оценил сложность, можно переходить к написанию кода. Главное — следовать той идее, которую проговорил в начале, и не менять подход на ходу без предупреждения. Иногда кандидаты так увлекаются, что переписывают решение на лету, а в итоге код не совпадает с тем, что они объясняли — и приходится начинать сначала.
В нашем случае интервьюер ожидает такое решение:
// Время: O(n), где n — размер массива.
// Память: O(n).
bool ContainsDuplicate(List<int> nums) {
HashSet<int> used = new HashSet<int>();
foreach (int num in nums) {
if (!used.Add(num)) {
return true;
}
}
return false;
}#include <vector>
#include <unordered_set>
using namespace std;
// Время: O(n), где n — размер массива.
// Память: O(n).
bool containsDuplicate(const vector<int>& nums) {
unordered_set<int> used;
for (int num : nums) {
if (!used.insert(num).second) {
return true;
}
}
return false;
}// Время: O(n), где n — размер массива.
// Память: O(n).
func containsDuplicate(nums []int) bool {
used := make(map[int]struct{})
for _, num := range nums {
if _, ok := used[num]; ok {
return true
}
used[num] = struct{}{}
}
return false
}// Время: O(n), где n — размер массива.
// Память: O(n).
boolean containsDuplicate(List<Integer> nums) {
Set<Integer> used = new HashSet<>();
for (int num : nums) {
if (!used.add(num)) {
return true;
}
}
return false;
}from typing import List
# Время: O(n), где n — размер массива.
# Память: O(n).
def contains_duplicate(nums: List[int]) -> bool:
used = set()
for num in nums:
if num in used:
return True
used.add(num)
return False// Время: O(n), где n — размер массива.
// Память: O(n).
function containsDuplicate(nums) {
const used = new Set();
for (const num of nums) {
if (used.has(num)) {
return true;
}
used.add(num);
}
return false;
}Предварительная проверка
Перед тем как сдавать код на проверку, проверь его дважды:
- Первый раз — синтаксис: всё ли правильно написано, нигде не потерялась ли скобка, нет ли опечаток в именах переменных.
- Второй раз — логику решения: проходят ли все кейсы? Учитываются ли пустые массивы, массивы из одного элемента?
Такое разделение проверки помогает быстрее замечать ошибки.
Что дальше
Задача решена, ты переходишь ко второй — придерживаясь того же алгоритма действий. А чтобы не сбиться с пути, забирай чеклист, который поможет получать максимум баллов на алгоритмической секции.
План решения алгоритмической задачи
Самая частая ошибка кандидатов — сразу бросаться писать код. Даже если задача кажется лёгкой, всегда держись алгоритма 1. Задать уточняющие вопросы. 2. Озвучить идею решения. 3. Оценить время и память решения. 4. Написать код. 5. Проверить синтаксис. 6. Проверить логику. 7. Сдать на проверку.
Следуй этому плану — и ты будешь на шаг впереди большинства кандидатов.