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

Игра в Жизнь

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

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

ℹ️ Описание

Доска состоит из сетки ячеек размером m x n, где каждая ячейка имеет начальное состояние:

🔹живое — обозначается цифрой 1
🔹мертвое — обозначается цифрой 0.

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

🔹Любая живая клетка, имеющая менее двух живых соседей, умирает, из-за недостаточной численности населения.

🔹Любая живая клетка с двумя или тремя живыми соседями доживает до следующего поколения.

🔹Любая живая клетка, имеющая более трех живых соседей, погибает от перенаселения.

🔹Любая мертвая клетка, имеющая ровно три живых соседа, становится живой клеткой путем размножения.

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

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

Механика игры подробно описана в статье википедии.

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

🔹В матрице может быть от 1 до 25 столбцов и колонок
🔹В каждой ячейке может быть всего одно значение: 0 или 1

1️⃣ Пример

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

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

2️⃣ Пример

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

Ответ:
[
[1,1],
[1,1],
]

✅ Решение

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

Чтобы иметь оптимальное потребление памяти, нужно производить все изменения in-place. Если мы будем просто менять состояние в исходной матрице при проверке каждого элемента, то мы потеряем исходное состояние и не сможем корректно проверять необходимость мутации.

Для того чтобы это обойти введем два новых значения для матрицы.

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

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

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

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

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

По времени
O(m * n) так как мы обходим всю матрицу поэлементно.

По памяти
O(1) так как мы не выделяем дополнительную память.

#matrix #medium

Самый дешевый путь в матрице

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

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

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

ℹ️ Описание

Вам дана матрицы m * n. Значение каждой ячейки — стоимость перехода в эту ячейку из соседних. Переходить можно либо в ячейку справа, либо в ячейку снизу.

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

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

🔹Высота и ширина матрицы заданы в диапазоне от 1 до 200
🔹Значения ячеек матрицы заданы в диапазоне от 0 до 200


1️⃣ Пример

Входящие данные: [[1,3,1],[1,5,1],[4,2,1]]
Ответ: 7

Самый дешевый путь:
🔹Перемещаемся на 3 ячейки вправо (1+3+1)
🔹Спускаемся на две ячейки вниз (1+1)
Суммарный путь — 7.


2️⃣ Пример

Входящие данные: [[1,2,3],[4,5,6]]
Ответ: 12

Самый дешевый путь:
🔹Перемещаемся на 3 ячейки вправо (1+2+3)
🔹Спускаемся на одну ячейку вниз (6)
Суммарный путь — 12.

3️⃣ Пример

Входящие данные: [[1,12,1],[1,5,1],[1,9,1]]
Ответ: 9

Самый дешевый путь:
🔹Спускаемся на одну ячейку вниз (1+1)
🔹Перемещаемся на 2 ячейки вправо (5+1)
🔹Спускаемся на одну ячейку вниз (1)
Суммарный путь — 9.


✅ Решение

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

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

🔘 Запускаем стандартный обход матрицы по i, j

🔘 При i = 0 && j = 0 (левый верхний угол) стоимость пути равна исходному значению ячейки.

🔘 При i = 0 (элементы верхней строчки) стоимость пути равна сумме измененого значению слева (стоимость пути к левому элементу) с оригинальным значением текущего элемента. Помним, что перемещаться мы можем только вправо и вниз, так что попасть в элемент первой строчки матрицы мы можем только из соседнего элемента слева.

🔘 При j = 0 (элементы первой колонки) стоимость пути равна сумме измененого значению сверху (стоимость пути к верхнему элементу) с оригинальным значением текущего элемента. Так же как и в предыдущем условии, в элемент первой колонки матрицы мы можем попасть только из соседнего элемента сверху.

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

🔘 После того как мы полностью промутируем матрицу в правом нижнем элементе матрицы окажется искомое нами значение.

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

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

По времени

Для того, чтобы найти самый дешевый путь нам достаточно один раз пройтись по всем элементам матрицы. Сложность - O(m*n).

По памяти

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

#matrix #medium

Контейнер с наибольшим количеством воды

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

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

ℹ️ Описание

Вам дан целочисленный массив высот height длиною n.

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


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

🔹В массиве всегда есть минимум 2 элемента, но не больше 10 ^ 5
🔹В качестве значений могут быть числа в диапазоне от 0 до 10 ^ 4


1️⃣ Пример

Входящие данные: [1,8,6,2,5,4,8,3,7]
Ответ: 49

Прямоугольник с наибольшой площадью образуют второй и девятый (последний) элемент массива. В этом случае высота прямоугольника — 7 (минимальная высота из двух вариантов — 8 и 7). Длина прямоугольника (разность индексов этих высот) также равна 7.

2️⃣ Пример

Входящие данные: [1,1]
Ответ: 1

В данном случае возможно получить только один прямоугольник площадью 1.


✅ Решение

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

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

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

🔘 Вычислим размер получившегося прямоугольника.

🔘 «Сузим окно» — для этого выберем какую границу сдвигать. При уменьшении длины получить большую площадь мы можем только увеличив высоту:
⏺ если левая высота меньше чем правая, сдвигаем левый указатель на единицу вправо;
⏺ если правая высота меньше чем левая, сдвигаем правый указатель на единицу влево.

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

🔘 Продолжаем «сужать окно», пока правый и левый указатели не сойдутся.

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

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

По времени

На каждой итерации мы двигаем либо правую, либо левую границу окна. Таким образом, суммарно мы подвинем границу O(n - 1) раз. Это единственная переменная величина. Таким образом, алгоритм имеет линейный порядок роста O(n).

По памяти

Мы никак не преобразуем входящие данные и не храним промежуточные результаты (как в случае с брутфорсом). Сложность по памяти константная — O(1).

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

Сегодня мы поговорим о том, из чего вообще состоят современные собеседования на инженерные позиции в IT компании.

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

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

1️⃣ Великий рандом

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

После опционально может проходить встреча на час с HR, CEO или другими людьми для оценки ваших софт скилов.

Я также не раз был на таких собеседованиях, где все вопросы просто сводились к болтовне за жизнь.

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

2️⃣ Стандарт Кандидат

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

Такие собесы состоят из пяти секций. Некоторые секции убираются или объединяются в разных компаниях.

🔹Скрининг

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

🔹Платформа

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

🔹Алгоритмы

Всеми нелюбимая и самая спорная секция. Решаем алгоритмические задачи и проверяем знания алгоритмов.

🔹Архитектура или System Design.

Тут проверяются навыки проектирования систем и рассматриваются задачи по типу спроектирую «Твиттер».

🔹Оценка софт скилов или Culture Fit.

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

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

Позже я расскажу вам про каждую секцию подробно. Stay tuned.

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

Лучшее время для покупки и продажи акций. Решение через восходящие тренды

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

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

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

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

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

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

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

#arrays #medium

Лучшее время для покупки и продажи акций. Решение через локальные минимумы и максимумы

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

Возьмем для примера следующий массив цен в долларах [20, 10, 15, 5, 10, 20, 10] и представим его в виде графика.

Теперь на графике хорошо видно, что нам нужно сделать две покупки и две продажи:

- купить акцию на второй день за 10 и продать на третий день за 15
- купить акцию на четвертый день за 5 и продать на шестой день за 20

В итоге мы сможем получить максимальную прибыль и заработать $20.

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

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


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

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

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

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

#arrays #medium

Лучшее время для покупки и продажи акций

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

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

ℹ️ Описание

Вам дан целочисленный массив цен prices, где prices[i] — цена акции на i-й день.

Каждый день вы можете принять решение о покупке и/или продаже акции. Вы можете одновременно владеть только одной акцией.

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

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

🔹В массиве может быть от 1 до 3 * 10^4 элементов
🔹В качестве значений могут быть числа в диапазоне от 0 до 10 ^ 4


1️⃣ Пример

Входящие данные: [7,1,5,3,6,4]
Ответ: 7

Покупайте в день 2 (цена = 1) и продавайте в день 3 (цена = 5), прибыль = 5-1 = 4. Затем купите в день 4 (цена = 3) и продайте в день 5 (цена = 6), прибыль = 6-3 = 3.

Общая прибыль равна 4 + 3 = 7.

2️⃣ Пример

Входящие данные: [1,2,3,4,5]
Ответ: 4

Покупайте в день 1 (цена = 1) и продавайте в день 5 (цена = 5)

Прибыль = 5-1 = 4.

3️⃣ Пример

Входящие данные: [7,6,4,3,1]
Ответ: 0

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

Прибыль = 0.


✅ Решение

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

#arrays #medium

Я обещал вернуться и начать что-нибудь рассказывать, возвращаюсь, начинаю :)

Сегодня расскажу про то, как мы искали стажера в Авито :)

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

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

Что удивительно, мы получили много заявок, но тестовые выполнили буквально человек 10. Вот кстати тестовое стажера, которого мы наняли. В нем нет никакого rocket-science, оно просто аккуратно сделано, хорошо оформлено и обработана большая часть corner-case. Кажется, что любой начинающий спец, мог заморочиться и сделать аналогичное.

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

Дальше была серия собесов с кандидатами, у которых были относительно хорошие тестовые и люди отсеялись на них. Что сделать чтобы повысить свои шансы на этих этапах?

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

Секция платформы. Существует мнение, что сейчас стажеров гоняют так же, как синьоров лет 5 назад. Оно отчасти верно, но 5 лет назад не было такого количества обучающих материалов. Раньше, чтобы получить тот же объем знаний нужно было вдоль и поперек перекопать документацию по Андроиду, в которой была только сухая документация, в которую нужно было прям погружаться, чтобы понять. Сейчас же, есть академия, канал Розова, Гладкова, где все объясняется на пальцах. Разобраться в базовом наборе технологий намного проще. На худой конец, есть куча мок собесов, если для тебя что-то осталось непонятным — всегда можно зазубрить

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

На этом заканчиваю свой небольшой спич :)

А с какими проблемами при поиске своей первой работы сталкиваетесь вы?

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

Обычно еще проверяются знания языков программирования по вашей специализации (Go, JavaScript, php и т.д.) и навыки проектирования.

Ну и не забывайте про culture fit. На самом деле эта оценка зачастую куда важнее технической.

Мой коллега рассказывает про найм стажеров, но процесс примерно такой же для всех инженеров.

Возведение числа в степень. Имплементация функции 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

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

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

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

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

ℹ️ Описание

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

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

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


1️⃣ Пример

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

2️⃣ Пример

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

3️⃣ Пример

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


✅ Решение

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

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

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

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

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

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

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

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

#strings #stack #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

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

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

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


ℹ️ Описание

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


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

🔹Длина массива от 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

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

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

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

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

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

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

Так, например, в сортировке пузырьком нам нужно сравнить все элементы попарно между собой (цикл в цикле). Это означает, что мы имеем дело со сложностью 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).

#теория

Привет, друзья!

А ведь сегодня день программиста. Как-никак, наш профеcсиональный праздник.

Мы от души поздравляем вас и желаем уметь решать самые крутые и сложные задачи самыми оптимальными способами!

🎉🎉🥳

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

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

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


ℹ️ Описание

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


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

🔹 Длина строки с римским числом может быть в диапазоне от 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

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

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

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

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

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

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

Далее для каждого 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