Не можешь победить - возглавь!

Всем привет!

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

Несмотря на то, что алгоритмические секции я не люблю всем сердцем, сам раздел computer science «Алгоритмы и структуры данных» считаю как минимум не лишним (а, на самом деле, очень полезным) для любого участника процесса разработки. Эти знания и навыки позволяют вам эффективнее решать рабочие задачи, лучше и глубже понимать как работают различные инструменты, в чем их слабые и сильные стороны.
Например, небольшая «насмотренность» алгоритмических задач помогла нам недавно «придумать» алгоритм быстрой фильтрации модификаций в каталоге (подробнее)

О чем этот канал?

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

Более «возвышенная» цель - через разбор подобных задач погрузиться в основы базовых алгоритмов и структур данных (да-да, канал не претендует на звание академического курса - во всяком случаем, на данный момент).

Кто участвует в ведении канала?

Сейчас каналом занимаются 2 человека:
- Денис Колпаков - go разработчик, 8 лет в IT. Последние 3 года работает в Авито (в юните Core Services). Занимается разработкой и поддержкой каталогов.
- Ивасюта Алексей - Team Lead (ex-frontend), 9 лет в IT. Последние 3 года работает в Авито. Недавно возглавил команду Bricks - конструктор разметки.

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

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

Как готовиться?

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

Что нужно, чтобы начать прорабатывать этот навык?

🔘 Базовое знание любого языка программирования

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

🔘 Минимальное количество теории

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

🔘 Много практики

Чем больше, тем лучше. Знатоки говорят, что вам в среднем потребуется прорешать 500-800 задач, чтобы окончательно перевести этот навык в разряд мастерски освоенных.

🔘 Читать наш канал 🙂

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

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

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

Как вести себя на интервью? 🤔

Давайте поговорим немного о самом процессе собеседования.

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

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

🔘 Уточните сколько времени отводится на решение задачи

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

🔘 Не бойтесь спрашивать у интервьюера вопросы

Если вам что-то непонятно в задаче — спросите. Или попросите интервьюера прокомментировать ваши идеи.

🔘 Не бегите сразу писать код

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

🔘 Подумайте о корнер кейсах

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

🔘 Не стоит сразу пытаться придумать оптимальное решение

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

🔘 Оцените асимптотическую сложность алгоритма и количество выделенной дополнительной памяти

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

🔘 Просите совета у интервьюера

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

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

Сумма двух чисел в массиве

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

ℹ️ Описание

Дан массив целых чисел nums.
Напишите функцию twoSum, которая будет находить в массиве два числа, сумма которых равна определенному целевому
числу target.

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

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

🔹 В массиве может быть от 2 до 10^4 уникальных значений
🔹В качестве значений могут быть числа в диапазоне от -10^9 до 10^9
🔹Значение target может быть в диапазоне от -10^9 до 10^9
🔹Для массива всегда есть только одно решение

1️⃣ Пример

Вход:
nums = [2, 7, 11, 15]
target = 9

Ответ: [0, 1] или [1, 0]

Сумма 2 и 7 равна 9. Следовательно, index1 = 0, index2 = 1.

Возвращаем [0, 1].

2️⃣ Пример

Вход:
nums = [-1, 0]
target = -1

Ответ: [0, 1] или [1, 0]

Сумма -1 и 0 равна -1. Следовательно, index1 = 0, index2 = 1.

Возвращаем [0, 1].

✅ Решение

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

В этом нам может помочь структура Map (или ее аналоги), которая позволяет получать значение по ключу за константное время.

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

Далее запускаем цикл по всем элементам массива, в котором выполняем следующие проверки на каждой итерации.

1. Высчитываем разницу между target и текущим числом из массива. Это второе искомое число, которое нам нужно.

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

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


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

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

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

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

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

#easy #arrays

Сумма двух чисел в отсортированном массиве

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

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

ℹ️ Описание

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

В качестве результата функция должна возвращать массив с индексами элементов, удовлетворяющих условию. Отсчет индексов начинается с единицы.

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

🔹 В массиве может быть от 2 до 3 * 10^4 уникальных значений
🔹 В качестве значений могут быть числа в диапазоне от -1000 до 1000
🔹 Массив отсортирован в возрастающем порядке
🔹 Значение target может быть в диапазоне от -1000 до 1000
🔹 Для массива всегда есть только одно решение

1️⃣ Пример

Вход:

nums = [2, 5, 7, 15]
target = 9

Ответ:

[1, 3]

Сумма 2 и 7 равна 9. Следовательно, index1 = 1, index2 = 3.
Возвращаем [1, 3].

2️⃣ Пример

Вход:

nums = [-1, 0]
target = -1

Ответ:

[1, 2]

Сумма -1 и 0 равна -1. Следовательно, index1 = 1, index2 = 2.
Возвращаем [1, 2].

✅ Решение

Решение этой задачи сильно упрощается дополнительными условиями:

- массив отсортирован в возрастающем порядке;
- в массиве нет повторяющихся значений.

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

1. Заводим два указателя, которые будут хранить индексы. Значение left делаем равным 0, значение right равным индексу последнего элемента.

2. Запускаем цикл, который прервется, если left станет больше или равен right, то есть когда индексы сойдутся.

3. На каждой итерации высчитываем сумму элементов под индексами left и right и проверяем ее на равенство с target.

- Если сумма равна target, значит мы нашли искомые числа. В таком случаем возвращаем в ответе их индексы, добавив к ним единицу.

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

Так как массив отсортирован в возрастающем порядке и в нем нет дубликатов, мы точно знаем, что число левее right будет гарантировано меньше. Уменьшаем right на 1.

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

Так как массив отсортирован в возрастающем порядке и в нем нет дубликатов, мы точно знаем, что число правее left будет гарантировано больше. Увеличиваем left на 1.

Таким образом мы перебираем все возможные комбинации и находим конечный ответ.


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


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

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

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

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

#medium #arrays

Сумма трех чисел в массиве

Сегодня рассмотрим с вами задачу, которая является неким объединением подходов из предыдущих двух.

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


ℹ️ Описание

Дан массив целых чисел nums. Напишите функцию, чтобы найти в массиве все уникальные тройки чисел, сумма которых равна нулю. В одной тройке [nums[i], nums[j], nums[k]] один и тот же элемент не может повторяться дважды, то есть
i != j, i != k и j != k.

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


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

🔹В массиве может быть от 3 до 3000 значений
🔹В качестве значений могут быть числа в диапазоне от -10^5 до 10^5


1️⃣ Пример

Вход:

nums = [-1, 0, 1, 2, -1, -4]

Ответ:

[[-1, -1, 2], [-1, 0, 1]]

2️⃣ Пример

Вход:

nums = [0, 1, 1]

Ответ:

[]

3️⃣ Пример

Вход:

nums = [0, 0, 0]

Ответ:

[[0, 0, 0]]


✅ Решение

Эту задачу можно решить несколькими способами. Поэтому рассмотрим каждый из них по отдельности.

#medium #arrays

Сумма трех чисел в массиве. Решение через Hash Set

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

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

Посмотрим на такой пример ввода [-1, 0, 1, 2, -1, -4].
После сортировки мы получим следующий массив [-4, -1, -1, 0, 1, 2].

Теперь запускаем цикл по всем элементам массива.

Далее для каждого i-го элемента мы будем запускать отдельный цикл для поиска недостающей пары чисел из тройки. Так как мы всегда двигаемся слева направо, то мы можем запускать второй цикл начиная от i + 1 и до конца.

Первое, что нам нужно учесть — это то, что в наших ответах не должно быть одинаковых троек. Если мы посмотрим еще раз на пример входящих данных, то мы обнаружим что у нас есть два одинаковых возможных решения [-1, 0, 1].

В массиве есть две возможные тройки с такими значениями под индексами
1, 3, 4 и 2, 3, 4. Однако, это легко решить, так как у нас отсортированный массив. Это значит, что одинаковые значения идут подряд и мы просто можем проверять первое и пропускать все остальные.

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

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

- Если третье число есть в Hash Set, то мы добавляем в наш результат массив из всех трех полученных чисел.

- Если третьего числа нет в Hash Se, то мы просто записываем в него второе число и идем дальше.

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

В результате мы получаем следующее решение задачи.

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


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

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

Сложность по времени O(n^2), так как мы запускаем цикл в цикле. Дополнительную сложность добавляет сортировка массива, она будет равна O(nlogn). Итоговая сложность равна O(nlogn + n^2), что асимптотически эквивалентно O(n^2).

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

#medium #arrays

Сумма трех чисел в массиве. Решение через два указателя

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

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

Теперь запускаем цикл по всем элементам массива.

Далее для каждого i-го элемента мы будем запускать отдельный цикл для поиска недостающей пары чисел из тройки. Так как мы всегда двигаемся слева направо, то мы можем запускать второй цикл начиная от i + 1 и до конца.

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

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

1. Заводим два указателя, которые будут хранить индексы. Значение left делаем равным i + 1, значение right равным индексу последнего элемента.

2. Запускаем цикл, который прервется, если left станет больше или равен right, то есть когда индексы сойдутся.

3. На каждой итерации высчитываем сумму элементов под индексами left, right и i-го элемента массива и проверяем ее на равенство нулю.

🔹 Если сумма больше нуля, значит мы сложили слишком большие числа и нам надо взять более маленькие. Уменьшить сумму мы можем взяв число, которое стоит левее от текущего под индексом right. Уменьшаем right на 1.

🔹 Если сумма меньше нуля, значит мы сложили слишком маленькие числа и нам надо взять более большие. Увеличить сумму мы можем взяв число, которое стоит правее от текущего под индексом left. Увеличиваем left на 1.

🔹 Если сумма равна нулю, значит мы нашли искомые числа. В таком случае добавляем найденную тройку nums[i], nums[left] и nums[right] в коллекцию ответов. Здесь же сразу уменьшаем right и увеличиваем left на единицу, чтобы найти следующую возможную комбинацию.

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

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


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

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

Сложность по времени O(n^2), так как мы запускаем цикл в цикле. Дополнительную сложность добавляет сортировка массива, ее сложность равна O(nlogn). Итоговая сложность равна O(nlogn + n^2), что асимптотически эквивалентно O(n^2).

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

#medium #arrays

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

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

Преобразование римских чисел в арабские

Давайте отдохнем от сложных задач и рассмотрим классическую легкую с собеседований.

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


ℹ️ Описание

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


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

🔹 Длина строки с римским числом может быть в диапазоне от 1 до 15
🔹Строка содержит только валидные римские цифры в верхнем регистре


1️⃣ Пример

Входящие данные: III
Ответ: 3
Объяснение: III = I + I + I = 1 + 1 + 1 = 3

2️⃣ Пример

Входящие данные: LVIII
Ответ: 58
Объяснение: LVIII = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58

3️⃣ Пример

Входящие данные: MCMXCIV
Ответ: 1994
Объяснение: MCMXCIV = M + (M - C) + (C - X) + (V - I) = 1000 + (1000 - 100) + (100 - 10) + (5-1) = 1994


📖 Правила формирования римских чисел

Римские цифры могут быть представлены семью разными символами: I, V, X, L, C, D и M.

I 1
V 5
X 10
L 50
C 100
D 500
M 1000

Например, 2 записывается как II римскими цифрами, состоящими из двух единиц.
12 записывается как XII, то есть просто X + II.
Число 27 записывается как XXVII, то есть XX + V + II.

Римские цифры обычно пишутся от большей к меньшей слева направо. Однако цифра 4 — это IIII. Вместо этого 4 записывается как IV. Поскольку единица стоит перед пятеркой, мы вычитаем ее, получая четыре. Тот же принцип применим и к числу 9, которое пишется как IX.

Есть шесть случаев, когда используется вычитание:

🔹 I можно поставить перед V и X, чтобы получилось 4 и 9.
🔹X можно поставить перед L и C, чтобы получилось 40 и 90.
🔹C можно поставить перед D и M, чтобы получилось 400 и 900.


✅ Решение

Для решения данной задачи нам достаточно будет посимвольно пройтись по строке, преобразовать римский цифры в арабские и суммировать их. Главная сложность — учесть правила декремента (IV = 4, а не 6, так как меньшая цифра I стоит перед большей V).

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

var runeToIntegerMap = map[rune]int{
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000,
}

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

var runeToIntegerDecrementsMap = map[rune]map[rune]int{
    'I': {
        'V': 4,
        'X': 9,
    },
    'X': {
        'L': 40,
        'C': 90,
    },
    'C': {
        'D': 400,
        'M': 900,
    },
}

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

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

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

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

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

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

#easy #strings

Как доказать интервьюеру, что твой алгоритм крут? Или «выбираем из тысячи и одного алгоритма».

Давайте разбавим практические задачи минуткой занудства теории.

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

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

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

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

Так, например, в сортировке пузырьком нам нужно сравнить все элементы попарно между собой (цикл в цикле). Это означает, что мы имеем дело со сложностью n^2. Представьте, что нам нужно сперва отсортировать массив, а потом вывести его значения в консоль. Тогда количество действий будет n^2 (сортировка пузырьком ) + n (последовательный вывод элементов в цикле). Так как нас интересует порядок роста, мы смело откидываем все, кроме самого большого члена формулы — n^2.

Если бы кол-во действий алгоритма можно было описать формулой 3*n^3*log(n) + n^2 + 5, то итоговой сложностью была бы n^3*log(n), потому что мы отбросили константный член 5, n^2 (так как он растет медленнее, чем n^3*log(n)) и константный множитель 3)

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

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

P.S. Хочу также рассказать о самой частой ошибке, которую я встречал на собеседованиях. Кандидаты часто забывают учитывать в оценке встроенные функции языка, считая только написанный руками код. Самый классический пример — использование встроенной функции сортировки. Если вы вызываете что-то вроде sort.Ints(nums), помните — это не константное действие, а, скорее всего, n*log(n).

#теория

Поиск самого длинного общего префикса в строках

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

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


ℹ️ Описание

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


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

🔹Длина массива от 1 до 200 элементов
🔹Длина строки в массиве от одного до 200 символов
🔹Строка состоит только из символов латинского алфавита


1️⃣ Пример

Входящие данные: ["flower","flow","flight"]
Ответ: "fl"
Объяснение: ["flower","flow","flight"]

2️⃣ Пример

Входящие данные: ["dog","racecar","car"]
Ответ: ""
Объяснение: У строк нет общего префикса


✅ Решение

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

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

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

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

По памяти
Сложность по памяти O(m), где m - длина самой короткой строки в массиве (максимально возможная длина префикса).

#strings #arrays #easy

Сумма трех чисел в массиве. Решение без предварительной сортировки

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

Необходимо также проитерироваться по всем элементам массива и на каждой итерации запустить отдельный цикл от i + 1. Для того чтобы не проверять повторяющиеся числа, мы будем записывать каждое в структуру Hash Set dups и в начале итерации проверять, если уже такой элемент. Если в Hash Set уже есть такое число, то мы просто пропускаем итерацию.

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

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

В таких языках, как Python и Java мы можем создать массив (лист) из трех элементов, отсортировать их в любом порядке и добавить в еще один Has Set uniq. Добавление отсортированных троек обеспечит автоматическое избавление от дублей благодаря механике Hash Set. В конце просто нужно конвертировать Hash Set в массив и вернуть в качестве ответа.

Однако, в таких языках как, например, Go, JavaScript и TypeScript провернуть такое не получится. В Go нельзя использовать слайсы в качестве ключей, потому что это не сравниваемые типы. В JavaScript и TypeScript массивы использовать можно, но они передаются по ссылке, поэтому в Hash Set можно спокойно добавить одинаковые массивы, так как у них разные ссылки.

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

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


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

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

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

O(n^2) так как мы запускаем цикл в цикле.

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

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

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

#medium #arrays

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

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

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

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

ℹ️ Описание

Дана строка, состоящий только из скобок «(», «)», «{», «}», «[» и «]». Напишите функцию, определяющую, является ли строка правильной скобочной последовательностью.

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

🔹Длина строки от 1 до 10000 символов
🔹Строка состоит только из символов «(», «)», «{», «}», «[» и «]».


1️⃣ Пример

Входящие данные: "()"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.

2️⃣ Пример

Входящие данные: "()[]{}"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.

3️⃣ Пример

Входящие данные: "(]"
Ответ: false
Объяснение: открывающая и закрывающая скобки относятся к разным типам скобок


✅ Решение

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

🔘 Если символ — одна из открывающих скобок, кладем ее в стек.

🔘 Если символ — одна из закрывающих скобок, пытаемся извлечь верхний элемент из стека:
⏺ если в стеке нет эементов, значит последовательность невалидна и мы столкнулись с закрывающей скобкой для которой нет открывающей;
⏺ если верхний элемент — это открывающая скобка другого типа, значит последовательность невалидна и мы столкнулись с кейсом неверной пары (например "(]");
⏺ если верхний элемент — это открывающая скобка нужного типа, то просто идем дальше.

🔘 Если после итерации по всем симолам строки в стеке остались какие-либо элементы, значит последовательность невалидна (есть открывающие скобки, для которых нет открывающей пары). В противном случае — последовательность валидна.

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

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

По времени
Чтобы провалидировать строку, нам достаточно один раз проитерироваться по всем символам, то есть сложность равна O(n),
где n — длина строки.

По памяти
Нам понадобится промежуточный стек, в который в худшем случае мы поместим все символы строки (например, для строки "((((("). То есть сложность по памяти также равна O(n), где n — длина строки.

#strings #stack #easy

Возведение числа в степень. Имплементация функции pow(x, n)

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

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

ℹ️ Описание

Имплементируйте функцию возведения числа x в степень n — pow(x, n).

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

🔹Число x в диапазоне [-100.0, 100.0]
🔹Степень n в диапазоне [-2^31, (2^31) - 1]
🔹n - целое число
🔹Если x == 0, то n > 0
🔹Итоговый результат в диапазоне [-10000, 10000]


1️⃣ Пример

Входящие данные: x=2.00, n=10
Ответ: 1024

2️⃣ Пример

Входящие данные: x=2.10, n=3
Ответ: 9.261

3️⃣ Пример

Входящие данные: x=2.00, n=-2
Ответ: 0.25


✅ Решение

Для того, чтобы получить опимальное решение нужно:

- Вспомнить что такое рекурсивные функции и как с ними работать
- Свойство степеней: x^n = (x*x)^(n/2)
- Свойство степеней: x^(-n) = 1/ x^n

Алгоритм рекурсивной функции powAbsN(x, |n|).
|n| - модуль числа, то есть без учета знака.

Кейсы с отрицательной степенью обработаем отдельно, поделив 1 на pow(x, |n|):

🔘 Если n == 0, возвращаем 1 (x^0 всегда равен 1)

🔘 Если n == 1, возвращаем x

🔘 Если n четное число, возвращаем результат рекурсивного вызова функции, передав в качестве аргумента x квадрат от текущего значения x (x*x), а в качестве n - результат деления без остатка текущего значения n (n/2) - 2^4 = (2*2)^(4/2) = 4^2

🔘 Если n нечетное число, возвращаем результат рекурсивного вызова функции (также передав в качестве аргумента x квадрат от текущего значения x (x*x), а в качестве n - результат деления без остатка текущего значения n (n/2)) умноженый на текущее значение x - 2^5 = (2^4)*2 = (4^2)*2


Алгоритм основной функции myPow(x, n):

🔘 Если x == 1, возвращаем 1 (1 в любой степени равна 1)

🔘 Если x == -1, возвращаем -1 при нечетном n и 1 при четном n

🔘 Если n >= 0, возвращаем результат функции powAbsN(x, |n|)

🔘 Если n < 0, возвращаем 1/powAbsN(x, |n|)

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

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

По времени
Благодаря свойству степеней: x^n = (x*x)^(n/2), вместо n умножений числа x, на каждой итерации рекурсии мы сокращаем количество умножений в два раза. То есть сложность — O(log(n))


По памяти
Доп память константна — O(1)

#float #medium