Собеседование. Часть 1: Как простая задача на разворот массива вскрывает понимание Computer Science

За свою карьеру я провел сотни технических собеседований на самые разные грейды — от джунов до системных архитекторов. И делал я это в разных локациях: в России, Европе и США. Процессы найма везде немного отличаются, но есть подходы, которые работают безотказно в любой точке земного шара.

Многие кандидаты боятся алгоритмических секций, ожидая зубодробительных задач с LeetCode. Но моя цель — не завалить, а понять инженерное мышление. Поэтому я часто начинаю с элементарной задачи: дан массив чисел, его нужно отзеркалить (перезаписать в обратном порядке).

Эта задача — идеальная «лесенка», раскрывающая реальный уровень инженера. Давайте пройдем по ней вместе.

Шаг 1: Уровень Джуниора. Просто сделай это

От джуна я жду умения перевести бизнес-требование в код. Самый очевидный способ решить задачу в лоб — создать второй массив и скопировать туда элементы с конца.

fun reverseArrayNaive(arr: IntArray): IntArray {
    val result = IntArray(arr.size)
    for (i in arr.indices) {
        result[i] = arr[arr.size - 1 - i]
    }
    return result
}

Если код написан без ошибок с индексами — отлично. Если человек путается и не может подойти к задаче — для меня это красный флаг. Если код готов, я задаю первый вопрос: «Какова вычислительная сложность?». Ожидаемый ответ: сложность O(N) по времени, так как мы проходим массив один раз.

Шаг 2: Уровень Мидла. Экономим память

Переходим на следующий уровень. Я спрашиваю: «А что со сложностью по памяти?». Кандидат логично отвечает, что раз мы создаем массив того же размера, сложность — O(N).

Усложняем задачу: «Представь устройство с жестким лимитом ресурсов. Нам нельзя выделять память под второй массив. Как переписать алгоритм, чтобы сложность по памяти стала O(1)?»

Продвинутый разработчик сразу предложит in-place решение: менять элементы местами с начала и с конца.

fun reverseArrayInPlace(arr: IntArray) {
    var left = 0
    var right = arr.size - 1
    
    while (left < right) {
        val temp = arr[left]
        arr[left] = arr[right]
        arr[right] = temp
        left++
        right--
    }
}

Шаг 3: Уровень Синьора. Психологическая ловушка

Если in-place вариант написан, я подкидываю вопрос с подвохом: «В первом варианте цикл делал N итераций. Во втором указатели встретились посередине, то есть цикл выполнился N/2 раз. Уменьшилась ли вычислительная сложность по времени?»

И тут многие радостно отвечают: «Да! Мы сократили операции в два раза, код стал быстрее!». И это ловушка.

Правильный ответ: Нет, сложность осталась O(N). Давайте посчитаем атомарные операции присваивания:

1. В наивном подходе мы делали 1 присваивание за итерацию. Цикл шел N раз. Итого: N операций.

2. В in-place подходе мы делаем swap. Это три операции (temp = a, a = b, b = temp). Цикл идет N/2 раз. Умножаем 3 на N/2 и получаем 1.5 × N операций!

С точки зрения процессора мы не сэкономили время, а совершили даже больше базовых действий. Мы просто обменяли такты на память. В нотации Big O константы отбрасываются, поэтому оба алгоритма линейные. Но синьор обязан видеть код насквозь, понимая его цену на уровне регистров.

За 10 минут с помощью одной задачи мы проверили:

1. Умение писать циклы (Джун).

2. Понимание Big O и расхода памяти (Мидл).

3. Понимание реальной цены оптимизаций (Синьор).

Это не спортивное программирование с хитрыми математическими трюками. Это проверка базовой инженерной гигиены.