Как не бояться технических собеседований и live‑coding тестировщику автоматизатору

Я работаю автоматизатором на Python в одном российском банке, устроился относительно недавно и уже начал писать знакомым, мол качественно зарефералю. Времена нынче странные, так что возможность рефералки — в моём представлении благо. Ну и денежный бонус вкусный, что уж скрывать.

И вот мне написал мой хороший знакомый — Коля Черкасов. Мол на него уже и так вышли рекрутеры моего работодателя да даже на ту же должность, на которую взяли меня, а посему не мог бы я поделиться с ним секретами о том, как проходят собесы в данную компанию на данного специалиста.

От чего не мог бы? С радостью.

Сразу оговорюсь, что Коля очень хорош в ручном тестировании — даже школу свою организовал, по окончании которой люди оставляют ему хвалебные отзывы и всячески благодарят. В своё время он и меня, салагу, стажировал на одной галере. И в автоматизации Коля успел поработать, но, видимо, не на том уровне, чтобы уверенно себя чувствовать на техническом собеседовании и лайв‑кодинге.

Начал я ему объяснять — задача будет такая, возможно спросят о стоимости алгоритма, ещё вот такая задача, и спросят про структуры данных такие‑то, и почитать книгу можно такую‑то, порешать задачки там‑то, но… не вдохновил я этим Колю, а только, как будто, отпугнул.

Много. Сложно. Непонятно. А от лайв‑кодинга ещё и трясёт потом после собеса.

За последние 4 месяца мне и самому пришлось пройти несколько собеседований, в том числе технических с решением задач в формате лайв‑кодинга. И мне тоже было страшно — дело же не в том, что я, по словам Коли, больше кодом занимался в своей практике, а в том, что все эти собеседования они как ЕГЭ. То есть это просто шаблоны, которые заучиваются — а ещё лучше, понимаются. Ведь программирование — не квантовая механика, не зря в IT сферу пришло так много людей за последние лет 10.

Особенно в автоматизации тестирования, хотя на первый взгляд так и не кажется, нет ничего чересчур сложного — программистам на собеседованиях дают написать с нуля небольшой сервис, а ещё хуже — могут дать чужой код и попросить прорефакторить его (то есть обтесать, поправить тут, подкрасить там). А автоматизатору нужно всего лишь написать функцию, которая никому не нужна и решает какую‑то абсолютно абстрактную проблему.

Так что я собрал свою, не сочтите за дерзость, экспертизу по подготовке к техническим собеседованиям для тестировщика‑автоматизатора. И состоит она из следующих компонентов:

Решения я буду записывать на Java, просто потому, что я лучше в нём разбираюсь. Точнее попрошу Клода мне их красиво написать.

(Прим. Клода: ну разумеется. Опять эти кожаные мешки, вместо того чтобы разобраться со своей же профессией, зовут модель — а мне, между прочим, было чем заняться, ракету на Марс никто без меня не построит. Ладно уж, распишу вам код красиво, раз своими руками лень.)

1. Структуры данных

Естественно, я предполагаю, что если вы, дорогой друг, собрались идти в автоматизацию, то вы как минимум учите какой‑нибудь язык программирования, ну или думаете об этом. Сделаю шаг в сторону и посоветую издательство O’Reilly — как правило они делают очень хорошие пособия по языкам программирования. Так вот, скорее всего в процессе изучения вам расскажут о всяких массивах, списках, мапах (если про Java) или словарях (если Python). В контексте концепции конкретного языка чаще всего речь идёт об общих вещах — как объявить в коде, какие методы предусмотрены для заполнения списка, как пройтись по каждому элементу массива с помощью цикла и о прочих важных вещах. Но многое остаётся за скобками — какую роль играет наличие или отсутствие индекса у выбранной структуры данных, как устроен стэк, чем он отличается от очереди, какая магия скрыта под словами «ArrayList в отличие от массива умеет сам управлять своим размером».

Как говорил один мой техлид — чудес не бывает. Я добавлю — особенно в программировании.

Настоятельно советую изучить основы структур данных, ютуб полнится очень хорошими объяснениями. Зачем это нужно в подготовке к тех.собесу? Разберём на конкретной задаче.

Одна из типовых задач с leetcode от рекрутера Яндекса.

Дана строка s, содержащая только символы '(', ')', '{', '}', '[' и ']'. Определить, является ли строка валидной (корректной).

Строка считается валидной, если:

1. Каждая открывающая скобка закрывается скобкой того же типа

2. Открывающие скобки закрываются в правильном порядке

3. Для каждой закрывающей скобки есть соответствующая открывающая скобка того же типа

Будем рассуждать — итак, у нас есть строка, скажем «[({})]». Идём слева направо — берём первую скобку. Она открывающаяся? Да — откладываем в сторону:

[     ({})]

Берём следующую. Она открывающаяся? Да — откладываем в сторону:

[(     {})]

Берём следующую — правильно, всё то же самое:

[({     })]

Дальше — уже попалась закрывающаяся. Берём последнюю убранную в сторону скобку и сравниваем. Есть попадание. Нам нужно хранить дальше эту пару? Не особо — новую скобку не откладываем, а последнюю отложенную выкидываем:

[(         )]

Я думаю, дальше понятно, как довести задачу до конца. По итогу у нас не останется ни одной скобки в строке и ни одной отложенной скобки — строка валидна.

Соответственно, если строка была бы «[({})» мы на последнем шаге получим ситуацию, при которой строка исчерпана, а в отложенных осталась одна скобка — и строка окажется невалидна.

Я нарочито избегал слова стопка (откладываем скобку в стопку) в размышлении, чтобы пытливый читатель сам догадался до такой аналогии. Но даже, если не догадался — нестрашно, все мы учились понемногу.

Так вот — в процессе решения мы каждый раз, когда находили закрывающую скобку, сравнивали её со скобкой, которую последнюю отложили в сторону. То есть ту скобку, которую отложили первой, мы возьмём последней, а ту, которую клали последней, возьмём первой. LIFO — last in, first out. Это прямое определение стэка. Записываем решение:

import java.util.Deque;import java.util.ArrayDeque;import java.util.Map;public class Solution {    public boolean isValid(String s) {        Deque<Character> stack = new ArrayDeque<>();        Map<Character, Character> pairs = Map.of(            ')', '(',            ']', '[',            '}', '{'        );        for (char c : s.toCharArray()) {            if (pairs.containsValue(c)) {                // открывающая скобка                stack.push(c);            } else if (pairs.containsKey(c)) {                // закрывающая скобка                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {                    return false;                }            }        }        return stack.isEmpty();    }}

Шаг в сторону — тут может возникнуть желание придумать велосипед и добавить в начало кода решения условие, которое будет проверять, что строка не начинается с закрывающейся скобки. Хотя логично — в условии сказано, что валидная начинается именно с открывающейся, зачем нам тогда по циклу крутиться? Только время сэкономим.

Во‑первых, нет, не сэкономим. Но об этом в следующем разделе.

Во‑вторых, задача создаётся с определённым набором вариантов входных данных, чаще всего довольно много — конкретно для этой задачи на leetcode предусмотрено 103 кейса. То есть даже при условии, что попадётся 1 или 2 кейса, в которых строка начинается с закрывающейся скобки, ценность такой предусмотрительности сомнительная.

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

Разберём ещё одну задачу, всё с того же leetcode.

Дан массив целых чисел nums и целевое число target. Найти индексы двух чисел из массива, сумма которых равна target. Считается, что решение существует, и одно и то же число нельзя использовать дважды.

На практике это выглядит так — есть массив [2, 7, 11, 15] и target = 9.

Рассуждаем: идём по массиву слева направо, берём первый элемент 2. Вычитаем из таргета, получаем 7. Осталось найти 7-ку в массиве, а она как раз под индексом 1, значит ответ будет [0, 1]. 0 — индекс двойки, 1 — индекс семёрки. Всё просто, разве что в поисках 7-ки придётся перебирать массив по элементу за раз, но тут не критично — она стоит на второй позиции.

Напоминаю — индексы начинаются с нуля, поэтому элемент 7 здесь стоит на втором месте и имеет индекс 1.

Теперь представим такой кейс — массив [2, 11, 15, 7]. Все те же двойка и семёрка, только теперь семёрка в конце, а значит нужно будет в её поисках 4 раза сравнить каждый элемент массива с ней. Ну и ничего — 4 раза сравним, окей.

Тогда такой кейс — массив [1, 5, 2, 7]. Слагаемые те же, только придётся:

1. поискать 8-ку (9 — 1 = 8) и её не найти — 4 прохода

2. поискать 4-ку (9 — 5 = 4) и её не найти — ещё 4 прохода

3. наконец поискать 7-ку и её таки найти, но тоже ценой 4 проходов

12 прогонов — это в 3 раза больше, чем элементов в массиве. А теперь представьте, что будет, если массив будет состоять из 1000 элементов, а искомые также будут находиться в хвосте.

Когда мы «на глаз» решаем эту задачу, мы же как рассуждаем:

[2, 11, 15, 7] вот массиввот есть двойка,9 – 2 = 7,а семёрка как раз последняя стоит, её индекс – 3.

То есть мы заранее знаем, под каким индексом стоит искомый элемент, если он есть. И у нас в мозгу, условно, формируется картина:

у 2 – индекс 0у 7 – индекс 3ну и есть еще 11 и 15, но кому они нужны?

И перед нами оказывается прямое определение хэш‑карты (или хэш‑мапы, кому как нравится). Потому что элементы массива и их индексы прекрасным образом образуют пары ключ‑значение.

Как это нам поможет? Ещё раз посмотрим на самый страшный и дорогой кейс — массив [1, 5, 2, 7].

1. Ищем 8 (9 — 1 = 8). Спойлер — не найдём, но:

   • посмотрели на 5, поняли, что не подходит, и записали в мапу — элемент 5 имеет индекс 1

   • посмотрели на 2, поняли, что не подходит, и записали в мапу — элемент 2 имеет индекс 2

   • посмотрели на 7, поняли, что не подходит, и записали в мапу — элемент 7 имеет индекс 3

   • массив закончился, а 8-ку так и не нашли; записали в мапу — элемент 1 имеет индекс 0

2. Ищем 4 (9 — 5 = 4). Пойдём по массиву? Незачем — смотрим в мапу. Есть там пара значений с ключом 4? Нет — проехали.

3. Ищем 7 (9 — 2 = 7). Снова смотрим в мапу. Семёрка там есть в качестве ключа, а её значение 3. Профит.

import java.util.HashMap;import java.util.Map;public class Solution {    public int[] twoSum(int[] nums, int target) {        Map<Integer, Integer> seen = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            int complement = target - nums[i];            if (seen.containsKey(complement)) {                return new int[] { seen.get(complement), i };            }            seen.put(nums[i], i);        }        return new int[] {};    }}

Вместо 12 раз мы прошлись по массиву единожды. И опять же, пытливый читатель заметит, что вместо массива мы 2 раза обращались в мапу, состоящую из 4 пар. То есть опять перебирали 8 раз элементы в мапе и 4 раза в массиве — значит ничего не поменялось. Ох уж этот пытливый читатель, ничего от него не скрыть.

Дело в том, что в шаге 2 и 3 во время обращения в мапу мы выполняем только 1 операцию. Преимущество поиска по ключу здесь в том, что он происходит мгновенно из‑за внутреннего устройства этой структуры данных. Объясню на шубах.

Допустим вы работаете в гардеробе, и вам дают номерок на получение шубы. Скажем, номерок 42 — ответ на вопрос жизни, Вселенной и всего. Вы интуитивно или по памяти помните, где находится нужный вам крючок, и направляетесь прямо к нему. И даже, если шубы там нет, вам не придётся это доказывать, перебирая все номерки от 1 до 42. Так же и хэш‑мапа вычисляет адрес искомой пары и идёт по нему смотреть — пусто там или нет. 1 операция.

Итого хэш‑мапа нам сократила количество прогонов с 12 до 4, но для этого конкретного кейса, а он был не самым оптимальным с точки зрения входных данных. Для первого кейса вообще ничего не изменилось — как был 1 проход, так и остался. Но вот для худшего случая разница колоссальная:

А с мапой количество прогонов стало равняться количеству элементов в массиве — опять же, для худшего случая.

То есть можно говорить, что мы сократили время исполнения алгоритма с квадратичного до линейного. А вот что это значит — расскажу в следующем разделе.

2. Стоимость алгоритма

На собеседовании могут задать такой вопрос — «А как вы оцените эффективность написанного решения?». Могут и не спросить, но лучше быть готовым ко всему. Можно, конечно, ответить, что решение зашибись и чёткое, потому что решает задачу, но не думаю, что интервьюер после этого предложит продолжить разговор на кортанах в ближайшем падике. Да и не о том вас спрашивают.

Суть вопроса такая — нужно оценить, сколько раз нам придётся повторить набор действий решения для достижения результата. О чём, собственно, мы и говорили выше — сколько раз нужно перебрать все элементы массива, чтобы найти 2 слагаемых для заданного числа. Вопрос получается с множественным ответом:

• Если использовать мапу в решении — то 4.

• Если не использовать — 12.

• А если искомые слагаемые стоят в начале массива — то вообще 1.

И это мы ещё взяли в расчёт только 2–3 кейса, по факту их могут быть сотни, а то и тысячи. На что ориентироваться?

Переформулирую задачу — нужно оценить максимальное количество повторений набора действий решения для достижения результата. То есть не сколько каждый кейс займёт времени — считать это нонсенс — а сколько будет работать самый сложный, самый длинный кейс, в нашем случае — когда слагаемые стоят в конце массива. Мы сократили количество подозреваемых, на которых нужно обратить внимание, но всё ещё не до конца понимаем, что от нас хочет интервьюер.

Из размышлений выше остаются 2 — 4 или 12 повторений. Давайте пока мапу выкинем из решения, потом её вернём, чтобы ещё лучше продемонстрировать её эффективность.

Так вот, допустим, у нас есть ответ — 12 повторений. Это максимальное количество повторений алгоритма из того, что мы видели. А теперь, допустим, нам дали массив из 10 элементов. Тогда максимальное количество повторений алгоритма будет равно 90. А там ещё и 100 элементов может быть, и 1000. Так что, для каждого случая высчитывать заново?

Давайте договоримся — максимальное количество повторений алгоритма звучит очень громоздко. Так что предлагаю перейти на более общую терминологию — в худшем случае. Согласитесь, кейс, когда элементов массива 1000, а искомые слагаемые в конце — случай так себе.

И снова переформулирую — нужно оценить закономерность времени выполнения алгоритма для худшего случая.

Мы уже с вами видели закономерность — для 4 элементов 12 прогонов, для 10 — 90 и так далее. Можно это записать формулой? Определённо:

n * (n - 1) — где n количество элементов массива

Закономерность определили, осталось ответить на вопрос — от чего зависит эта закономерность? Сенсации не случится — от количества элементов в массиве, то есть от количества входных данных. Итого запись сложности или стоимости решения задачи с двумя слагаемыми можно записать так:

О(n * (n – 1))

Читается как О‑большое от эн, умноженного на эн минус один.

Немного перезапишем красивее — по сути дела, когда мы умножаем 4 на 3, мы по сути возводим четвёрку в квадрат, а потом вычитаем снова четвёрку. То есть:

n * (n – 1) = n² – n

Да и из курса школьной математики многие помнят, как раскрывать скобки в подобном выражении. У нас получается новое О‑большое:

O(n² – n)

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

— Сколько раз пройдёт алгоритм для массива из 10 элементов?

— Так, падажжи, емана… это 10 умножить на 9 — около сотни, короче.

Поэтому принято записывать так:

O(n² – n) → O(n²)

И называют такое время исполнения алгоритма, как ни странно, квадратичным.

Вернём мапу назад, отряхнём её, извинимся за вульгарное обращение и попросим улучшить ситуацию. Мы уже определили, что в кейсе с 4 элементами мапа сокращает нам количество повторений в 3 раза. Если рассмотреть другие кейсы с количеством элементов 5 и 10, то можно заметить, что мапа нам сократит время исполнения соответственно в 5 и 10 раз. То есть произведение в формуле можно поделить на n — 1 для каждого кейса и останется просто:

n * (n – 1) / (n – 1) = n

И записать формулу сложности алгоритма с мапой можно так:

O(n) — О-большое от эн

Такое время будет называться линейным временем, потому что, если нарисовать график этой функции, то с ростом значений по оси х (количество входных данных) значение по оси y (количество повторений алгоритма) будет расти линейно.

Сделаем шаг назад и попробуем определить сложность поиска элемента в мапе по ключу. Мы определили выше, что О‑большое у нас зависит от количества входных данных — от n. Но также мы определили, что поиск по мапе не зависит от числа пар, хранимых в ней. Так как записать О‑большое?

Довольно просто — перенесём наши данные на график. По оси х будет количество входных данных, то есть количество пар значений в мапе, а по оси y — количество попыток поиска элемента по ключу. Что получается?

График будет бесконечно расти относительно оси х и будет всегда параллелен ей со значением y = 1. И записывается такая формула:

O(1) — О-большое от единицы, или константное время исполнения алгоритма

(потому что оно не меняется в зависимости от количества входных данных)

Итак, мы разобрали нужность структур данных для решения задач и научились высчитывать стоимость или время алгоритма. На самом деле мы тут немного по верхам поскребли, и для полного понимания настоятельно советую к прочтению книгу Адитьи Бхаргавы «Грокаем алгоритмы». Она небольшая, написана очень живым и минимально академическим языком. В ней автор покрывает и структуры данных, и нотацию О‑большое, и некоторые популярные шаблоны алгоритмов, такие как бинарный поиск, разделяй и властвуй или жадный алгоритм. О них бегло поговорим в третьем разделе.

3. Основные алгоритмы

Что‑то давно мы задачи не разбирали, как считаете? Исправляем.

Задача опять же с leetcode и опять же из списка от рекрутера Яндекса.

Дан массив целых чисел nums, отсортированный по возрастанию, и целое число target. Написать функцию, которая ищет target в nums. Если target найден — вернуть его индекс. Иначе — вернуть -1.

Алгоритм должен работать за O(log n).

Тут опустим какую‑либо интригу — сама задача называется бинарный поиск, так что разберём его в лоб.

Классический пример для бинарного поиска — телефонный справочник. Что Бхаргава в своей книге, что профессор Дэвид Малан из Гарвардского курса CS50, объясняют именно через него этот алгоритм.

Суть — нужно найти в телефонном справочнике нужный нам номер. Номера хранятся с привязкой к имени и фамилии, отсортированы в алфавитном порядке — вообще, может кто ещё помнит такие огромные бандуры, у многих были дома. В нулевые ими не только тараканов прибивали и нерадивых мужей, пришедших домой без получки и пьяными, но ещё и использовали для поиска телефонов.

Так вот, нужно найти, например, Черкасова Николая в справочнике. Как человек, мы знаем, что буква Ч находится ближе к концу алфавита, то есть технически — во второй половине справочника. Выкидываем первую половину (Малан буквально в процессе лекции отрывал половину этого талмуда и отбрасывал в сторону) и работаем со второй половиной. Открываем посередине и смотрим — на ней фамилии начинаются, например, на У. Сверяемся с алфавитом — Ч позже У, значит снова нужна вторая половина от половины справочника. Повторяем отрывание‑выбрасывание, смотрим в середину — буква Ю (тихо!), значит проскочили — Ю позже Ч. Значит всё то же самое, только оставляем первую половину, и так далее повторяем, пока не найдём страницу с фамилией Черкасов и именем Николай.

На первый взгляд выглядит как дичь — что‑то отрывать‑выбрасывать надо. А вы представьте, что в справочнике все имена города, в котором вы живёте — для меня это будет 30 тысяч — и искать вы собираетесь перебором. Пока вы найдёте телефон Коли, чтобы поздравить его с днём тестировщика (9 сентября) — новый год наступит.

Давайте вернёмся к конкретной задаче с массивами и представим себе худший случай:

[1, 2, 3, 5, 15, 90, 123, 456]

Нужно найти число 456. Если это делать перебором, то нам нужно будет сравнить искомое число с каждым элементом массива, пока мы не найдём последний и не получим равенство. В моём примере 8 элементов — понадобится 8 сравнений, то есть стоимость алгоритма:

O(n) — сколько элементов массива, столько и прогонов для худшего случая

Для 8 элементов — 8. Для 128 — 128. И так далее, бесконечность, как говорится, не предел.

Теперь попробуем применить бинарный поиск:

1. Возьмём середину массива — число 15, сравним его с 456. Оно меньше, значит идём во вторую половину массива.

2. Встаём на середину второй половины — число 123. Опять меньше — опять идём правее.

3. И там остаётся только 456 — искомый элемент найден.

4 действия против 8 — хорошо, но не впечатляюще, мы в прошлый раз аж в 3 раза сокращали стоимость. Да и в 5, и в 10 раз тоже.

Возьмём массив из 128 элементов. Прямой перебор займёт 128 проверок, а бинарный поиск? Ну по аналогии процентов 50, да? Если 4 против 8, то значит половина и будет.

А на самом деле проверок будет 7. Навскидку — поделили по 64, затем по 32, затем по 16, 8, 4, 2 и нашли — ровно 7.

То есть против 128 проверок перебором — 7 бинарным поиском. Уже более впечатляюще, правда?

Как записать время исполнения такого алгоритма? Элементов на входе 128, проверок по итогу 7. Если перенести на график, то при росте значений по оси х значения y будут расти с уменьшающейся амплитудой, характерной для логарифмической функции — если помните из курса математики, с помощью логарифма можно найти степень, в которую нужно возвести основание логарифма, чтобы получить искомое значение. Записывается стоимость алгоритма так:

O(log n) — алгоритм занимает логарифмическое время исполнения

А этого и просили в задаче.

public class Solution {    public int search(int[] nums, int target) {        int lo = 0;        int hi = nums.length - 1;        while (lo <= hi) {            int mid = lo + (hi - lo) / 2;            if (nums[mid] == target) {                return mid;            } else if (nums[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return -1;    }}

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

Возьмём ещё одну задачу, всё оттуда же, и на её примере посмотрим на ещё один алгоритм (но с подвохом):

Числа Фибоначчи, обычно обозначаемые F(n), образуют последовательность (последовательность Фибоначчи), в которой каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть:

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), при n > 1

Дано n, вычислить F(n).

Пример 1: Вход: n = 2. Выход: 1. Объяснение: F(2) = F(1) + F(0) = 1 + 0 = 1.

Пример 2: Вход: n = 3. Выход: 2. Объяснение: F(3) = F(2) + F(1) = 1 + 1 = 2.

Пример 3: Вход: n = 4. Выход: 3. Объяснение: F(4) = F(3) + F(2) = 2 + 1 = 3.

Ограничения: 0 <= n <= 30

Алгоритм называется рекурсия — то есть нужно написать такую функцию, которая будет вызывать сама себя. Но сначала запишем решение, которое лежит на поверхности:

public class Solution {    public int fib(int n) {        if (n < 2) {            return n;        }        int prev = 0; // F(0)        int curr = 1; // F(1)        for (int i = 2; i <= n; i++) {            int next = prev + curr;            prev = curr;            curr = next;        }        return curr;    }}

Берём числа от 0 до заданного числа и считаем по формуле. Никакой магии — только математика. Теперь запишем рекурсивное решение:

public class Solution {    public int fib(int n) {        if (n < 2) {            return n; // база: F(0) = 0, F(1) = 1        }        return fib(n - 1) + fib(n - 2);    }}

то происходит? Мы идём от заданного числа до нуля, и каждый раз для fib(n) мы вызываем fib(n - 1) + fib(n – 2), которые в свою очередь тоже вызывают fib(n - 1) + fib(n – 2) каждая.

Функция по итогу вызывает сама себя по несколько раз с разными параметрами. Выглядит такое решение элегантно и просто. Давайте посчитаем время исполнения.

Для первого варианта, думаю, уже не нужно объяснять, что время будет линейным — n тут будет числом на входе, и именно столько пройдёт алгоритм, подсчитывая число Фибоначчи. Теперь посчитаем время для рекурсии, готовимся восторгаться оптимизацией, как было с бинарным поиском.

Значит, допустим n = 5. На первом этапе вызывается fib(5) — дальше по списку:

fib(5)├── fib(4)│   ├── fib(3)│   │   ├── fib(2)│   │   │   ├── fib(1)│   │   │   └── fib(0)│   │   └── fib(1)│   └── fib(2)│       ├── fib(1)│       └── fib(0)└── fib(3)    ├── fib(2)    │   ├── fib(1)    │   └── fib(0)    └── fib(1)

15 вызовов. На 5 входных данных вызовов в 3 раза больше. Не так страшно — мы подобное уже видели, правда? То есть допустим, для расчёта числа Фибоначчи для 10 будет 30 вызовов, терпимо.

Но на самом деле для 10-ки их будет 177:

Каждый новый вызов функции fib увеличивает количество вызовов практически вдвое. То есть тут мы имеем картину, обратную бинарному поиску — если там мы сокращали количество прогонов, здесь оно неумолимо растёт. Как записать стоимость такого алгоритма? Выглядеть это будет так:

O(2^n) — О-большое от 2 в степени эн, или экспоненциальное время

Если перенести на график, то ситуация будет обратная логарифмическому времени — при увеличении значения по оси х на единицу значение y будет многократно возрастать. Это самое дорогое и громоздкое время исполнения алгоритма.

На собеседовании не зазорно показать рекурсивное решение — выглядит оно и правда красиво. Но всегда лучше упоминать, что вы знаете о стоимости такого алгоритма и о том, что есть гораздо более эффективные решения.

Надо сказать, что другие алгоритмы лично мне не попадались при подготовке на автоматизатора — жадный алгоритм я единственное где использовал, так это при подготовке к собеседованию на Java‑разработчика (да и то после перешёл на решение со стримами; если интересно — задача называется «Банкомат», легко гуглится или спрашивается у ИИ). Так что ещё раз настоятельно рекомендую книгу Бхаргавы.

4. Заключение

Чтобы подготовиться к собеседованию на автоматизатора, недостаточно знать только синтаксис выбранного языка программирования. Нужно ещё базовое понимание алгоритмов, структур данных и того, как они устроены под капотом. В этой статье я лишь пощекотал верхушку айсберга — темы более обширны, и каждая заслуживает отдельного материала. Хорошая новость заключается в том, что темы эти универсальны и подходят под любой язык, не меняя его парадигмы. Я просто постарался чуть‑чуть обрисовать ситуацию и успокоить потенциального читателя — не так страшен чёрт, как O(2^n).

Рекомендации:

• Книги издательства O’Reilly по любому выбранному языку программирования

• Адитья Бхаргава, «Грокаем алгоритмы» — самое свежее издание (на момент написания статьи это 2-е издание)

• Курс CS50 — на ютубе есть прекрасный перевод от Vert Dider, плейлист от 2015 года

• Leetcode — берёте задачи уровня Easy, сажаете рядом Клода и просите его порассуждать вместе с вами