Algorithmics: хакаем алгоритмические собесы

Столкновение астероидов

Привет, друзья. Помните задачку на валидацию скобочной последовательности? Она считается очень легкой и на leetcode она в разряде easy задач. Я же никогда не считал, что ее по сложности можно сравнить с каким-нибудь слиянием отсортированных массивов. Львиная доля ее легкости заключается в мейнстримности этой задачи - едва ли не каждый знает каноническое решение через стек. А между тем, это далеко не единственная задача, которую можно оптимально решить через эту структуру данных. И, если попросить кандидата решить немного другую задачу с похожей идеей решения, то вполне можно вогнать человека в ступор :). Как всегда, дело в умении распознать класс задачи, а вот применить паттерн решения уже не составляет труда.

Поэтому, сегодня мы разберем задачу о столкновении астероидов.

P.S. Если быть честным, у меня ушло около 40 минут на реализацию и отладку решения через 2 индекса, прежде чем я догадался воспользоваться стеком. Решение через стек вышло сильно лаконичнее и быстрее в реализации 🙂

Сложность: 🟠 Средняя

ℹ️ Описание

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

Входные данные: массив целых ненулевых чисел. Каждое число обозначает массу астероида, знак - направление движения.

Выходные данные: массив целых ненулевых чисел. Массив будет описывать множество астероидов, их массу и направление, после того, как все астероиды, которые могут столкнуться, столкнутся.

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

В отличие от реальной жизни, при столкновении масса и направление движение астероидов после никак не изменяются. Меньший из двух полностью уничтожается, больший продолжает лететь в прежнем направлении, не меняя массу.

⚠️ Ограничения

- Количество астероидов (длина входного массива) находится в диапазоне от 2 до 10000
- Масса астероида лежит в диапазоне от 1 до 1000 (знак влияет только на направление движения)
- Астероидов с нулевой массой не существует

1️⃣Пример

Входящие данные

[]int{5,10,-5}

Ответ

[]int{5,10}

Пояснение

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

2️⃣ Пример

Входящие данные

[]int{8,-8}

Ответ

[]int{}

Пояснение

Астероиды движутся навстречу друг другу и имеют одинаковую массу. В результате оба астероида будут уничтожены.


3️⃣ Пример

Входящие данные

[]int{10,2,-5}

Ответ

[]int{10}

Пояснение

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


✅ Решение

Посмотреть подробное объяснение решения

#stack #medium

Разворот целого числа

Привет, друзья. Сегодня рассмотрим с вами усложненную версию предыдущей задачи.

Сложность: 🟠 Средняя

ℹ️ Описание

Дано 32-битное целое число x со знаком. Напишите функцию reverse, которая принимает на вход x, а возвращает перевернутое число.

Если изменение x приводит к выходу значения за пределы диапазона 32-битных целых чисел со знаком [-2^31, 2^31 - 1], верните 0. Учтите, что среда исполнения функции не позволяет хранить 64-битные целые числа со знаком или без знака.

⚠️ Ограничения

Значение x находится в диапазоне от -2^31 до 2^31 - 1

1️⃣Пример

Входящие данные

x = 123

Ответ

321

2️⃣ Пример

Входящие данные

x = -123

Ответ

-321

3️⃣ Пример

Входящие данные

x = 2147483647

Ответ

0

✅ Решение

Посмотреть подробное объяснение решения

#math #medium

Число после двойного переворота

Сложность: 🟢 Легкая

ℹ️ Описание

Дано целое число num. Переверните число, чтобы получить reversed1, затем переверните reversed1, чтобы получить reversed2. Верните true, если перевернутое значение reversed2 равно исходному числу num. В противном случае верните false.

Переворот целого число означает, что вам необходимо перевернуть все его цифры.

Например, переворот числа 2021 дает число 1202.

Переворот числа 12300 дает 321, поскольку ведущие нули не сохраняются.

⚠️ Ограничения

Значение num находится в диапазоне от 0 до 10^6

1️⃣Пример

Входящие данные

num = 526

Ответ

true

2️⃣ Пример

Входящие данные

num = 1800

Ответ

false

✅ Решение

Посмотреть подробное объяснение решения

#math #easy

Fizz Buzz

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

Сложность: 🟢 Легкая

ℹ️ Описание

Дано целое число n. Напишите функцию, которая принимает в качестве параметра число n и возвращает массив строк answer, который формируется по следующим правилам:

▶️ answer[i] == "FizzBuzz", если i делится одновременно на 3 и 5;

▶️ answer[i] == "Fizz", если i делится только на 3;

▶️ answer[i] == "Buzz", если i делится только на 5;

▶️ answer[i] == i, во всех остальных случаях.



⚠️ Ограничения

Значение n находится в диапазоне от 1 до 10^4.

1️⃣Пример

Входящие данные

3

Ответ

["1", "2", "Fizz"]

2️⃣ Пример

Входящие данные

5

Ответ

["1", "2", "Fizz", "4", "Buzz"]

3️⃣ Пример

Входящие данные

15

Ответ

["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"]

✅ Решение

Для решения задачи нужно запустить цикл от 1 до n и на каждой итерации проверять 4 взаимоисключающих условия. Если условие выполняется, то в результирующий массив добавляется соответсвующая строка.

Посмотреть решение


🅾️ Оценка сложности

По времени

Сложность по времени линейная — O(n), так как мы итерируемся от 1 до n.

По памяти

Сложность по памяти константная — O(1), так как мы не создаем дополнительных переменных. Выходной массив не считается за выделение дополнительной памяти, потому что работа алгоритма от этого не зависит. При выборе любой реализации алгоритма, выходной массив нужно будет сформировать в любом слуае.

#arrays #easy

Произведение элементов массива исключая себя

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

Сложность: 🟠 Cредняя

ℹ️ Описание

Вам дан целочисленный массив nums. Напишите функцию, возвращающую в качестве ответа такой массив, в котором на i-ой позиции будет число, равное произведению всех элементов массива nums, кроме i-го.

Дополнительно попробуйте решить задачу так, чтобы обеспечить линейную сложность O(1) по памяти. Выходной массив не считается за выделение дополнительной памяти.

⚠️ Ограничения

🔹 В массиве может быть от 2 до 105 элементов

🔹 Значение каждого элемента находится в диапазоне от -30 до 30

🔹 Произведение любого префикса или суффикса чисел гарантированно вписывается в 32-битное целое число

🔹 Запрещено использовать операцию деления в реализации

1️⃣Пример

Входящие данные

[1, 2, 3, 4]

Ответ

[24, 12, 8, 6]

2️⃣ Пример

Входящие данные

[-1, 1, 0, -3, 3]

Ответ

[0, 0, 9, 0, 0]

✅ Решение

Подробный разбор решения вы найдете в нашем блоге.

Посмотреть решение

#arrays #medium

Валидное Судоку

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

Сложность: 🟠 Cредняя

ℹ️ Описание

Вам дана доска Судоку размером 9 x 9. Определите, является ли эта доска валидной. На валидность проверяются только заполненные ячейки в соответствии со следующими правилами.

▶️ Каждая строка должна содержать цифры от 1 до 9 без повторений.

▶️ Каждый столбец должен содержать цифры от 1 до 9 без повторений.

▶️ Каждый из девяти квадратов доски размером 3 x 3 должен содержать цифры от 1 до 9 без повторения.

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

⚠️ Ограничения

🔹В доске 9 строк
🔹В доске 9 столбцов
🔹В качестве значений используются числа 1 - 9 или "." для обозначения пустых строк

✅ Решение

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

Решение задачи

Поделитесь в комментариях, как вам такой формат разбора и наш блог 🙂.

#matrices #medium

Имплементировать префиксное дерево (Trie)

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

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

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

Что делать, если вам попалась такая задача и вы не знаете что от вас просят? Вспомните, что софт скилы не менее важны чем харды и попросите интервьюера рассказать, какую проблему должна решать структура, какие методы должны быть имплементированы, какие требование к скорости/памяти предъявляются и так далее.

Если интервьер адекватный, он обязательно поможет вам понять, что от вас требуется.

Сегодняшняя наша задача — имплементировать префиксное дерево.

Сложность: 🟠 Cредняя

ℹ️ Описание

Необходимо написать реализацию структуры данных «Префиксное дерево». Данная структура должна имплементировать следующие методы:

▶️ Insert(word string) —сохранение слова в дерево

▶️ Search(word string) bool —проверка наличия слова в дереве. Важно помнить, что данный метод должен отвечать true только в случае, если найдено конечное слово (а не префикс)

▶️ StartsWith(prefix string) bool — проверка наличия префикса в дереве. В отличии от предыдущего метода true вернется как в случае нахождения полноценного слова, так и при наличии префикса.

⚠️ Ограничения

🔹Длина одного слова не превышает 2000 символов
🔹Слова могут состоять только из латинских букв в нижнем регистре
🔹Суммарное максимальное кол-во вызовов всех методов - 30000

Пример

trie := Constructor()

trie.insert("apple")
trie.search("apple") // return True
trie.search("app") // return False
trie.startsWith("app") // return True
trie.insert("app")
trie.search("app") // return True


✅ Решение

Суть префиксного дерева — слово раскладывается посимвольно. Каждый символ будет нодой дерева. Связи между нодами соответствуют последовательности симолов в строке.

Таким образом, слово «apple» должно в нашей структуре превратиться в «ветку» a -> p -> p -> l -> e.

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

type Trie struct {
    children   map[rune]*Trie
    isFullWord bool
}

children — набор дочерних нод.

isFullWord — признак того, является ли текущая нода конечной буквой слова (нам нужен этот флаг, так как одно слово может полностью являться префиксом для более длинного слова).

Более подробное описание структуры можно найти по ссылке.

Для реализации метода вставки нам потребуется вспомогательный рекурсивный метод. На каждой итерации рекурсии мы будем отрезать по одной букве слева, превращая ее в префиксную ноду. В ноде последней буквы мы проставим флаг isFullWord в true.

Методы Search и StartsWith отличаются только тем, что в последней найденной ноде нам нужно проверить флаг isFullWord (для Search он должен оказаться true, а для StartsWith значение флага не имеет никакого значения). Поэтому для реализации обоих методов нам понадобится один вспомогательный метод traverse, который сможет рекурсивно обходить дерево вглубь. В этом методе мы будем отрезать по одной букве слева и искать ее в мапе children текущей ноды. Если такой ключ существует — переходить к найденной дочерней ноде.

Посмотреть подробное решение в блоге

🅾️ Оценка сложности

По времени

Функции Insert, Search и StartsWith используют рекурсивные вспомогательные функции insert и traverse. У обеих функций глубина рекурсии равна длине префикса.

Таким образом, все 3 функции имеют сложность O(n), где n - длина префикса.

По памяти

Для работы функций не используются промежуточные структуры, зависящие от длины префикса. Сложность по памяти O(1).

#tries #medium

Проверка массива на дубликаты

Сегодня я вам предлагаю немного снизить темп и в последний рабочий день недели посмотреть на очень простую классическую задачу.

Сложность: 🟢 Легкая

ℹ️ Описание

Дан целочисленный массив. Напишите функцию, которая принимает на вход массив и возвращает true, если какое-либо значение встречается в массиве более одного раза. Если каждое значение в массиве уникально, то функция должна возвращать false.

⚠️ Ограничения

🔹 В массиве может быть от 1 до 105 элементов
🔹 Каждое значение может быть в диапазоне от -109 до 109

1️⃣Пример

Входящие данные

[1, 2, 3, 1]

Ответ

true

2️⃣Пример

Входящие данные

[1, 2, 3, 4]

Ответ

false

✅ Решение через Hash Map

Для решения задачи этим способом достаточно проитерироваться по всем элементам массива. На каждой итерации нужно подсчитывать количество значений, которые встречаются. Для этого можно использовать Map:

▶️если в мапе не существует такого значения, то мы добавляем его туда и переходим к следующей итерации;

▶️если в мапе уже есть такое значение, то мы прерываем функцию и возвращаем true.

Посмотреть решение в блоге

🅾️ Оценка сложности

Сложность по времени

Сложность O(n), где n — количество элементов в массиве, так как в худшем случае мы пройдем в цикле по всем элементам.

Сложность по памяти

Сложность O(n), так как мы выделяем мапу для хранения частот значений.

✅ Решение через сортировку

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

Посмотреть решение в блоге

🅾️ Оценка сложности

Сложность по времени

Сложность алгоритма равна сложности сортировки, так как она больше линейной — O(n * logn).

Сложность по памяти

Сложность O(1), так как мы не выделяем дополнительной памяти.

#easy #arrays

Разворот массива

Я очень радуюсь, когда задачу получается сильно упростить и свести к какой-то простой последовательности, вместо разработки сложного алгоритма. Еще когда я только учился в универе программированию и не мог решить задачу, я часто выписывал данные на листочек и часами пытался разглядеть какие-то закономерности в их преобразовании, которые приведут меня к искомому решению.

Сегодня рассмотрим как раз такую задачу. У нее стоит средний уровень сложности, хотя на самом деле она очень легкая. И сейчас я вам это докажу 🙂.

Сложность: 🟡 Средняя

ℹ️ Описание

Дан целочисленный массив nums. Поверните массив вправо на k шагов, где k — неотрицательное число.

⚠️ Ограничения

🔹 В массиве может быть от 1 до 10^5 элементов
🔹 В качестве значений могут быть числа в диапазоне от -2^31 до 2^31 - 1
🔹 k в диапазоне от 0 до 10^5

1️⃣ Пример

Входящие данные

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3

Ответ
```
[```5, 6, 7, 1, 2, 3, 4```]```

Объяснение
1. Сдвинуть на 1 шаг вправо: [7,1,2,3,4,5,6]
2. Сдвинуть на 1 шаг вправо: [6,7,1,2,3,4,5]
3. Сдвинуть на 1 шаг вправо: [5,6,7,1,2,3,4]

2️⃣ Пример

Входящие данные

nums = [-1, -100, 3, 99]
k = 2

Ответ

[3, 99, -1, -100]

Объяснение
1. Сдвинуть на 1 шаг вправо: [99,-1,-100,3]
2. Сдвинуть на 1 шаг вправо: [3,99,-1,-100]

✅ Решение

В общем и целом разворот массива k раз в этой задаче подразумевает, что нам нужно сдвинуть все его элементы вправо на одну позицию k раз.

Поначалу в голову придет простой вариант: передвинуть все элементы вправо, а последний перенести на первую позицию и так k раз. Это простое и понятное решение, однако его сложность будет равна O(n * k), что не очень хорошо.

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

1. Под поворотом массива на 1 подразумевается смещение всех элементов массива вправо на одну позицию. Исходя из этого, если k будет равно или кратно длине массива, то после всех преобразований все элементы массива пройдут один «круг» и вернутся в исходное состояние.
Это означает, что мы можем отбросить повторяющиеся «круги» и взять только последний.

Для этого нужно найти остаток от деления k на длину массива. В результате мы найдем число count.

Именно на столько позиций надо сместить все элементы вправо.

2. Далее мы можем еще сильнее упростить алгоритм. Если внимательно посмотреть, то можно обнаружить, что для получения искомого результата надо произвести всего три операции:
- полностью развернуть исходный массив относительно центра
- развернуть первые k элементов относительно их центра
- развернуть оставшиеся элементы относительно их центра

Пример

nums = [1,2,3,4,5,6,7]
k = 3

1. Разворачиваем весь массив.

[7,6,5,4,3,2,1]

2. Разворачиваем первые 3 элемента относительно их центра.

[5,6,7,4,3,2,1]

3. Разворачиваем оставшиеся элементы относительно их центра.

[5,6,7,1,2,3,4]

Посмотреть решение в блоге

🅾️ Оценка сложности

n - количество элементов в массиве

По времени

Сложность по времени складывается из нескольких частей:
- O(n/2) — первый разворот массива
- O(k/2) — разворот первого подмассива, где k < n
- O(m/2) — разворот второго подмассива, где m < n

При этом m + k = n, поэтому в сумме сложность равна O(n).

По памяти

Сложность по памяти O(1), так как все изменения производятся in-place.

#medium #arrays

Из чего состоят собеседования. Culture Fit

Настало время поговорить о последнем и самом важном этапе собеседования. У него много имен: знакомство с командой, встреча с HR или CTO, проверка софт-скилов и много других. В общем и целом он называется Culture Fit.

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

Собственно, у данного этапа две основные задачи:

1️⃣ Первое и очевидное — нанимающий менеджер (или менеджеры) хотят проверить соответсвует ли кандидат принятой в компании или команде системе ценностей. Если проще, то на сколько комфортно будет работать с этим человеком и какой у него потенциал.

2️⃣ Второе — дать возможность кандидату также оценить своего будущего руководителя, познакомиться с другими членами команды (иногда) и позадавать вопросы непосредственно о проекте и своих будущих задачах.

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

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

1. Какой опыт работы у вас уже есть, в какой доменной области вы работали.

2. На сколько вы автономны как инженер и задачи какой сложности и длительности вы можете делать. Можно ли вам отдавать только подробно разобранные таски длиною в пару недель или в вас можно вкинуть большую проблему на квартал и вы сможете ее затащить.

3. Был ли у вас опыт в конфликтных ситуациях. Как вы их разрешали.

4. Проявляете ли вы инициативу, способны ли увидеть несовершенство в процессах/технологиях и предложить улучшения, или будете работать с тем, что есть.

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

6. Что для вас более ценно на работе, по каким критериям вы выбираете место работы.

7. Есть ли риски, что вы очень быстро уволитесь или не справитесь с работой и менеджеру заново придется тратить ресурсы на поиск нового кандидата.

8. И, наконец, соответствует ли сумма всех ваших ответов и уровень технических знаний той зарплате, которую вы запрашиваете.

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

Игра в грабителя

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

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


Сложность: 🟠 Cредняя

ℹ️ Описание

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

⚠️ Ограничения

🔹Нельзя грабить соседние дома
🔹Кол-во домов (размер входного массива) — от 1 до 100
🔹Размер грабежа с одного дома (значения входного массива) — от 1 до 400

1️⃣ Пример

Входящие данные: [1,2,3,1]

Ответ: 4

Выгоднее всего ограбить первый и третий дом.

2️⃣ Пример

Входящие данные: [2,7,9,3,1]

Ответ: 12

В данном примере - первый, третий и пятый дома

✅ Решение

Для решения этой задачи сразу стоит выявить несколько правил:
🔹Любой маршрут грабителя должен начинаться либо с первого, либо со второго дома — так как числа в массиве неотрицательные, а в любой другой дом мы можем попасть начав машрут с одного из этих двух домов.
🔹Любой маршрут грабителя должен завершиться либо на последнем, либо на предпоследнем доме (по тем же принципам, что и в предыдущем правиле).
🔹В процессе грабителю может оказаться выгодным сменить порядок обхода домов - т.е. пропустить не один соседний дом, а сразу два. Например, вот на таких входных данных - [10,1,1,10,1,1]. В. данном случае самый выгодный маршрут — первый, четвертый и последний дома. И такая смена на длинных массивах может случаться несколько раз.

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

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

Таким образом, так же как и в задаче на поиск пути в матрице, для решения этой задачи ам необходимо просто последовательно находить максимальный суммарный грабеж для кажого из домов (и также как в той здаче, изменения мы будем делать in-place для экономии памяти),

Алгоритм:
🔹 Запускаем цикл по исходному массиву
🔹Первые два элемента массива оставляем без изменений (так как это начала маршрутов)
🔹Третий элемент заменяем на сумму третьего и первого (так как в третий дом можно попасть только из первого)
🔹Для всех остальных элементов массива: заменяем исходное значение на сумму исходного значения и максимума из двух: значение (i-2) и (i-3) элементов, где i - индекс текущего элемента
🔹 Возвращаем максимум из двух значений: значение последнего элемента массива и значение предпоследнего элемента массива

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени
Для решения задачи нам необходимо один раз пройтись по всему исходному массиву. Итоговая сложность - O(n)

По памяти
Все изменения мы делаем in-place. Сложность по памяти константная — O(1).

#arrays #medium

Про секцию проектирования нужно добавить еще пару слов.

Это, по отзывам многих кандидатов, самая сложная и самая интересная секция на собеседованиях. И связано это с тем, что здесь весь процесс больше всего похоже на жизнь.

➖В чем сложность? ➖

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

Исходя из этого, секцию ведут опытные разработчики, которые пытаются дополнительными вопросами «копать» в глубь и прощупывать знания и кругозор кандидата. В конечном счете у двух человек может получаться кардинально разные архитектуры, которые будут решать поставленную задачу и удовлетворять требования.

➕А в чем же тогда плюсы? ➕

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

Помните, в архитектуре нет правильного решения. Важно лишь уметь обоснованно показать эффективность вашего.

Из чего состоят собеседования. System Design

Пришло время поговорить о секции проектирования. Она подразумевает оценку навыков кандидата в создании архитектуры масштабируемых и отказоустойчивых систем.

Обычно на эту секцию зовут кандидатов, которые претендуют на позицию уровня middle+. Предполагается, что инженеры до уровня мидла особо не участвуют в проектировании систем или же делают это под присмотром сеньоров.

Собственно, кандидату на старте дают абстрактную задачу из категории «Спроектируй аналог YouTube» или «Создай убийцу Twitter».

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

Дальше следуют три основных этапа.

1️⃣Сбор требований

Кандидату нужно активно задавать дополнительные вопросы заказчику (в данном случае интервьюеру), чтобы уточнить требования.

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

Кандидат должен активно исследовать и выявить максимальное количество требований и ограничений, чтобы спроектировать систему, которая им удовлетворяет. Неопределенность в требованиях может привести к неправильному проектированию, что в реальной работе приведет к затратам времени и ресурсов без результата, который ожидает заказчик.

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

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

2️⃣Верхнеуровневая архитектура

Задача кандидата на этом этапе заключается в проектировании верхнеуровневой архитектуры системы. Это означает, что необходимо создать общую структуру приложения, выделив крупные абстрактные блоки и описать взаимодействие между ними.

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

3️⃣ Детализация архитектуры

На этом этапе вам предложат проработать детальнее крупные блоки. Скорее всего не все, а только те, которые представляют больший интерес для интервьюера.

Например, если речь идет о клиент-серверном взаимодействии, то нужно выбрать протокол общения (HTTP, WebSocket и т. д.) и спроектировать API. Если обсуждается база данных, то кандидат может объяснить выбор конкретной БД, рассказать о её преимуществах и недостатках, а также затронуть вопросы масштабирования.

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

#собеседования

Генерация валидной скобочной последовательности (один вид скобок)

Мы уже делали пост об одной из самых заезженных задач — валидация скобочной последовательности. Эта задача у опытных собседуемых вызывает улыбку и желание сказать «hold my beer» интервьеру.

А вот вариация этой же самой задачи, где нужно сгенерировать все возможные валидные последовательности может загнать в ступор. Честно говоря, на практике я не сталкивался на собеседованиях с этой задачей, но, охотно верю, что ее могут практиковать вместо классической валидации (@avivasyuta несколько раз сталкивался 😀). Подобный трюк может выбить из колеи и заставить обеседуемого идти не по заученной формуле, а изобретать решение из головы.

Хорошая новость — у задачи очень понятный брутфорс с фоллбеком - мы можем сперва просто нагенерить все возможные строки из скобок, а потом провалидировать их :). Даже если в стрессовой ситуации вы не придумаете ничего другого, вы покажите, что умеете оптимально валидировать :).

Но, можно немного улучшить решение.

Сложность: 🟠 Cредняя

ℹ️ Описание

Дано целое неотрицательное число n. Напшите функцию, которая сгенерирует все возможные варианты правильных скобочных последовательностей длиной 2n, состоящих из круглых скобок — «(» и «)».

⚠️ Ограничения

🔹Количество пар скобок от 1 до 8
🔹Допустимые символы в строках - «(» и «)».

1️⃣ Пример

Входящие данные: 3

Ответ: ["((()))","(()())","(())()","()(())","()()()"]

2️⃣ Пример

Входящие данные: 1

Ответ: ["()"]

✅ Решение

Суть оптимального решения — отбрасывать невалидные строки на моменте генерации. Задача сильно упрощается тем фактом, что нам нужно использовать только один тип скобок, поэтому мы можем воспользоваться счетчиками открытых/закрытых скобок (хотя, кажется, если в решении мы заменим счетчики на стек и немного модифицируем, то мы сможем генерировать последовательности и для n видов скобок).

Мы можем выделить несколько правил:
🔹 Любая строка должна начинаться с открывающей скобки
🔹 Количество открытых и закрытых скобок должно быть равно n
🔹 Количество закрывающих скобок в любой итерации не должно превышать количество открывающих

Исходя из этих правил легко написать рекурсивную функцию по генерации.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени
В данной задачи мы генерируем m строк длиной 2*n. На любой позиции строки может быть один из двух символов. Если предположить, что символы ставятся независимо друг от друга и вспомнить простенькую формулу из комбинаторики, то m = 2^(2*n-1).
В нашем оптимальном решениии символы зависят друг от друга, так что диапазон возможных решений сильно снижается. Но, думаю, на интервью будет валидно сказать, что сложность сравнима с O(2^(2*n-1)).

По памяти
Нам нужно выделить память для хранения всех результирующих строк. Каждая строка имеет длину 2*n. Также как и в случае сложности, валидно будет сказать, что кол-во строк сравнимо с O(2^(2*n-1)).
Таким образом, оценка по памяти сравнима с O(n*2^(2*n-1)).


#strings #arrays #medium

2. Whiteboarding

Еще одним крайне странным подходом является witeboarding, то есть написание кода на доске, листке, или в блокноте. Каждый раз когда я сталкиваюсь с этим, я неистово удивляюсь и злюсь. Когда кто-то в последний раз писал код в блокноте, а не в IDE? А если писал, то для чего этот странный человек занимался такой чушью?

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

Я иногда могу забыть, как писать цикл for или объявить переменную, потому что пишу на разных языках и их синтаксис периодически смешивается в моей голове. Не думаю, что это является проблей и флагом к тому, что я плохой разработчик.

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

Собственно, whiteboarding — не более чем архаизм от дедушек, которые писали код на перфокартах (со всем уважанием к дедушкам).

3. Отсутствие связи с жизнью

Тут есть два аспекта.

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

Во-вторых, алгоритмические задачи почти всегда абстрактны и оторваны от реальности. Это неплохо тренирует соображалку, когда задачи решаются просто для общего развития, но это вызывает у меня дикое отторжение, когда на собеседорвании, например, на позицию frontend-инженера меня просят перелить воду из одного бассейна в другой ведром. Почему бы не привязывать задачи к той доменной области, в которой предпоалется работать? По карйней мере было бы понятно, что подобная задача может встретиться в реальной жизни и она будет решать конкретную проблему.

Вывод

В результате мы имеем секцию, эффективность которой стремится к нулю. Она почти ничего не проверяет и не дает каких-то объективных ответов о знаниях кандидатов. Есть даже специальный коэффициент, который показывает эффективность различных методов оценки кандидатов и вычисляется по результатам множественных исследований. Хоть убейте, не могу вспомнить как он называется. Если вы в курсе, то напишите в комментариях.

Так вот, результаты исследований говорят, что этот коэффициент примерно равен 0.5 для классической алгоритмической секции, то есть шанс правильного отбора кандидата через стандартную алгоритмическую секцию равен 50%. Это означает, что эффективность равна броску монетки. Можно вместо часа задач подбросить монетку и в случае выпадения решки пропустить кандидата дальше.

Как вы могли догадаться подходы с таким уровнем эффективности не должны применяться при отборе кандидатов. Однако, мы живем в мире, где это все еще является стандартом и нам приходится играть по правилам индустрии. А @tifongod уже писал, как готовиться к таким собеседованиям и как их проходить.

#собеседования

Из чего состоят собеседования. Алгоритмы

Давайте сразу выделим два вектора применения алгоритмов:
- алгоритмы для повседневной работы;
- алгоритмы для оценки навыков на собеседованиях.

👨‍💻 Алгоритмы для повседневной работы

Нет никаких сомнений в том, что знание алгоритмов и структур данных является очень полезным навыком для любого разработчика. Это фундаментальная область computer since, на которой держится вся разработка. Если вы будете практиковать навык разработки алгоритмов, то это поможет быстрее и эффективнее решать типовые задачи в повседневной работе. Грубо говоря, вы набиваете руку и тренируете насмотренность.

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

✔️ Алгоритмы для оценки навыков на собеседованиях

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

Большие и серьезные дядечки и тетечки из разных компаний упорно будут доказывать, что алгоритмы очень важны при оценке кандидатов и без них вообще никак нельзя определить его уровень. Однако, здесь есть ряд проблем и вот топ 3.

1. Алгоритмы не помогают оценить, как кандидат умеет писать код.

Во-первых, почему-то все забывает, что кандидат на собеседовании всегда находится в стрессе и никакие слова интервьера его не успокоят и не заставят полностью расслабиться. Да, можно чуть улучшить климат на час, но в любом случае по ту сторону монитора от кандидата сидит человек, который его оценивает и решает, на сколько он молодец и достоен ли тех денег, которые хочет. Это всегда негативно сказывается на результате, который кандидат сможет показать за час.

Во-вторых, в реальной жизни мы почти что никогда не работаем в такие сжатые сроки, где за час нужно написать супер-пупер эффективный обход дерева. В реальности у каждого человека свой темп разработки. Кому-то нужно 5 минут, чтобы вникнуть в суть и накидать прототип решения, а потом его дополнять. Некоторым же нужно все хорошенько обдумать, покрутить разные варианты в голове, попить чайку и написать один раз оптимальное решение за 5 минут.

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

И качество кода обычно обеспечивается тестами. Чтобы отыскать все баги в написанной функции, достаточно написать на нее исчерпывающий юнит-тест, а не пытаться в голове перебирать возможные варианты.

#собеседования

Из чего состоят собеседования. Платформа

Это, на самом деле, основная секция на собеседованиях. Она часто объединяется с алгоритмической для экономии времени. Давайте разберемся в целях, которые преследует секция платформы.

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

Если вы фронтенд-разработчик, то скорее всего вас обязательно попросят рассказать о замыканиях и дадут несколько задач, в которых хитро передаются параметры, и вам нужно будет ответить, что будет выведено в консоль. Помимо этого, почти гарантировано, что вы столкнетесь с вопросами о работе Event Loop, вам могут задать задачи с промисами и тому подобное. Еще одним классическим вопросом будет рассказать о том, как браузер обрабатывает ответы от сервера и отображает веб-страницы.

Если вы бэкенд-разработчик, то вас наверняка спросят, что такое Garbage Collector. А если вы работаете с языком программирования GO, то в списке обязательных вопросов появится объяснение того, что такое горутины и чем они отличаются от потоков. На бэке список вопросов может быть более вариативным, так как существует множество языков программирования со своими особенностями.

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

Интервьюеры очень ценят, когда вы можете отвечать на вопросы с точки зрения того, как работают процессы внутри. Если вы расскажете о том, как устроен планировщик в GO или как React Fiber рендерит веб-страницы, это покажет, что вы способны глубоко разбираться в деталях и знать технологии изнутри. Знание технологий изнутри почти всегда создает дополнительно положительное впечатление о вас, что может повлиять на решение о найме.

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

#собеседования

Из чего состоят собеседования. Скрининг

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

Этот этап более распространен в крупных компаниях, где большой объем заявок, и необходимо отсеивать несоответствующих претендентов.

Основная задача — сократить издержки, избегая затрат времени и ресурсов на кандидатов, которые, по всей видимости, не смогут пройти полноценные технические секции. Обычно это включает вопросы в формате теста, предназначенные для junior инженеров. Этот этап фактически является фильтром для кандидатов на уровне junior+.

Здесь обычно задаются самые фундаментальные вопросы, связанные с вашей областью. Например, ваши знания о типах данных в языке программирования или понимание понятия «замыкания». Вопросы часто имеют конкретные ответы и не содержат открытых формулировок.

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

#собеседования

Количество островов

Продолжаем работать с матрицами и сегодня мы будем играть в великих первооткрывателей.

Сложность: 🟠 Cредняя

ℹ️ Описание


Дана матрица размером m x n, которая представляет собой карту. Каждая ячейка матрицы может принимать следующие значения:

1 — суша
0 — вода

Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре края сетки окружены водой.

Напишите функцию, которая принимает на вход матрицу и возвращает количество островов в ней.

⚠️ Ограничения

🔹В матрице может быть от 1 до 300 столбцов и колонок
🔹Допустимые значения в матрице — 0 или 1

1️⃣ Пример

Входящие данные:
[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"],
]

Ответ: 1

2️⃣ Пример

Входящие данные:
[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"],
]

Ответ: 3

✅ Решение

Для того чтобы посчитать количество островов в матрице достаточно определить хотя бы по одной точке из каждого острова.

Первым делом создадим счетчик для подсчета количества островов, который будет иметь начальное значение равное 0. Далее для подсчета необходимо перебрать все элементы матрицы и выполнить следующие проверки:

🔘 если значение элемента равно 0, то мы просто его пропускаем;

🔘 если значение равно 1, то мы засчитываем попадание в остров, прибавляем единицу к счетчику и рекурсивно удаляем остров из матрицы.

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

Посмотреть решение в блоге

🅾️ Оценка сложности

По времени
Так как мы перебираем всю матрицу, то сложность перебора будет равна O(m*n). Также дополнительно может вызываться очистка острова, которая в худшем случае может занять O(m*n) операций (если вся матрица занята единицами.). Таким образом суммарная сложность O(2(m*n)), которая упрощается до O(m*n).

По памяти
O(1) — константная, так как мы выделяем дополнительную память только для хранения счетчиков.

#matrix #medium