Задача с собеседования в Zalando

Даны два целых числа a и b. Верните любую возможную строку s, такую, что:
- s имеет длину, равную a + b, и содержит ровно a букв "a" и ровно b букв "b",
- подстрока "aaa" не встречается в s,
- и подстрока "bbb" не содержится в s.

Пример 1:
Input: a = 1, b = 2
Output: "abb"
("abb", "bab" and "bba" - корректные варианты)

Пример 2:
Input: a = 4, b = 1
Output: "aabaa"

Ограничения:
0 <= a, b <= 100
Гарантируется, что существует строка s для данных a и b.

НАШ ЧАТ АЛГОРИТМИСТОВ

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

Сложность
O(a + b) - по времени
O(a + b) - по памяти

Код
class Solution:
def strWithout3a3b(self, a: int, b: int) -> str:
result = []
while a > 0 or b > 0:
if len(result) >=2 and result[-1] == result[-2]:
if result[-1] == "a":
result.append("b")
b -= 1
else:
result.append("a")
a -= 1
else:
if a >= b:
result.append("a")
a -= 1
else:
result.append("b")
b -= 1
return "".join(result)

@algoses

Задача с собеседования в Zenefits

Дан массив nums размером n, верните элемент большинства (гарантируется, что он всегда есть в массиве).
Элемент большинства (или мажоритарный) - это преобладающий элемент последовательности, который в данном случае должен встречаться более, чем n / 2 раз.
Решите задачу за линейное время и с O(1) по памяти.

Пример 1:
Input: nums = [3,2,3]
Output: 3

Пример 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Без дополнительного условия на асимптотику задачу можно было бы решить с использованием хэш-таблицы, где ключ - элемент массива, а значение - кол-во его вхождений в массив. Сложность при этом: O(n) - по времени и O(n) - по памяти.
С учётом условия улучшения пространственной сложности до O(1), оптимальным и стандартным будет использование алгоритма Бойера-Мура:
Создаём две переменные: result (содержит элемент, претендующий на то, чтобы оказаться мажоритарным) и count (счётчик "приоритета" элемента-кандидата на преобладание в последовательности). В начале цикла кандидатом окажется элемент, идущий первым в массиве, увеличиваем счётчик его "приоритета" на 1. Далее мы сравниваем каждый последующий элемент с текущим значением result, если они равны - увеличиваем счётчик, если нет - уменьшаем. Если в какой-то момент счётчик приоритета становится равным 0, выбираем нового кандидата и записываем в result. Так проходим по всем эл-там массива и в конце выводим result с последним вписанным в него значением.
Таким образом, суть алгоритма в симуляции попарного "обнуления" противоположных элементов путём уменьшения счётчика count. Так как преобладающий эл-т составляет больше половины всей последовательности, в процессе для него не останется противоположного элемента для попарного "удаления". Наличие мажоритарного эл-та гарантируется условием задачи, поэтому нам не нужна дополнительная проверка.

Сложность
O(n) - по времени
O(1) - по памяти

Код
class Solution:
def majorityElement(self, nums: List[int]) -> int:
result, count = 0, 0

for i in nums:
if count == 0:
result = i
count += 1
elif i == result:
count += 1
else:
count -= 1
return result

@algoses

Т-академия

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

Задача с собеседования в Zenefits

Дана двумерная бинарная матрица grid размером m x n, которая представляет карту из единиц (суша) и нулей (вода). Верните количество островов.
Остров окружён водой и сформирован путём соединения соседних участков суши (ячеек "1") по горизонтали или вертикали. Можете считать, что все четыре края сетки окружены водой.

Пример 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Пример 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Ограничения:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задачу можно решить рекурсивным обходом графа в глубину (dfs), так как ограничения размера 300×300 позволяют полагать, что опасности переполнения стека нет.
Вершины графа - ячейки с "1".
Рёбра - соседние ячейки по горизонтали и вертикали.
В цикле проходим по каждой ячейке матрицы, если ячейка содержит "1": увеличиваем количество островов и запускаем рекурсивную функцию dfs. В ней проверяем ячейку на соблюдение границ и помечаем этот участок суши, как пройденный (grid[i][j] = "0"). Следующими вызовами проверяем её соседей по горизонтали и вертикали.
На больших данных оптимальным будет решение через bfs или итеративный dfs, но без условия оптимизации рекурсивное dfs-решение стандартно для этой задачи.

Сложность
O(m*n) - по времени
O(m*n) - по памяти

Код
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
num_islands = 0

def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
return
else:
grid[i][j] = "0"
dfs(i, j+1)
dfs(i+1, j)
dfs(i, j-1)
dfs(i-1, j)

for i in range(m):
for j in range(n):
if grid[i][j] == "1":
num_islands += 1
dfs(i, j)

return num_islands

@algoses

Задача с собеседования в Zoox

Дан массив prices, где prices[i] - это цена акции в i-й день.
Вы хотите максимизировать прибыль, выбрав один день для покупки акции и другой день в будущем для её продажи.
Верните максимальную прибыль, которую вы можете получить с этой сделки. Если прибыль получить невозможно, верните 0.

Пример 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Объяснение: Покупаете акцию во 2-й день (цена = 1) и продаёте в 5-й (цена = 6). Прибыль: 6 - 1 = 5. Обратите внимание, что покупка во 2-й день и продажа в 1-й невозможна, так как вы должны сначала купить, а потом продать!

Пример 2:
Input: prices = [7,6,4,3,1]
Output: 0
Объяснение: В этом случае сделок не совершается (нет выгодных условий), и максимальная прибыль равно 0.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Для получения максимальной прибыли - покупаем на минимуме и продаём на максимуме. Заводим две переменные: min_price (находим самую выгодную цену) и max_profit (ищем наибольшую разницу между минимумом и текущей стоимостью акции).
Осуществляем проход по массиву и сравниваем минимальную цену (вначале она равняется первому эл-ту массива) с текущей. Если текущая меньше минимальной, обновляем значение минимума. Последний найденный минимум - цена, по которой мы купим акцию. Далее, в независимости от того, выполнилось ли условие для обновления минимума, проверяем: будет ли максимальной прибыль от продажи акции в текущий день. Сравниваем ранее найденное значение max_profit с прибылью, которую получим от продажи акции "сегодня". После окончания работы цикла выводим max_profit с последним вписанным в переменную значением.
Задача помечена тегом "Dynamic Programming", подход использован в решении: мы храним две переменные (min_price, max_profit) и используем их найденные значения для вычисления следующих.

Сложность
O(n) - по времени
O(1) - по памяти

Код
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0

min_price = prices[0]
max_profit = 0

for price in prices:
if price < min_price:
min_price = price

max_profit = max(max_profit, price - min_price)

return max_profit

@algoses

Разбор алгоритмов Т-банк (первая часть)

Разбор второй части и всех направлений выложен только на наших курсах. До конца дня действует льготная цена 13450 8950. Записываемся осталось 6 часов до конца экзамена!

@algoses

Задача с собеседования в eBay

Перед вами замок с 4 вращающимися дисками. Каждый диск имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Диски можно свободно вращать вперёд и назад: например, вы можете превратить '9' в '0' или '0' в '9'. Каждый ход - это поворот одного диска на одну позицию.
Замок начинает с комбинации '0000' (строка, представляющая состояние 4-х дисков).
Вам дан список тупиков - deadends: если на замке отображается какая-либо из запрещённых комбинаций, диски замка перестают вращаться, и вы не можете его открыть.
Вам также дана целевая комбинация target, представляющая значение дисков, при котором замок откроется. Верните минимальное возможное количество вращений, необходимое для открытия замка. Если это невозможно, верните -1.

Пример 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Объяснение: последовательность допустимых ходов может быть такой: "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Обратите внимание, что последовательность типа "0000" -> "0001" -> "0002" -> "0102" -> "0202" будет недопустимой, так как диски замка остановятся после запрещённой комбинации "0102".

Пример 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
Объяснение: мы можем повернуть последний диск в обратном направлении, чтобы перейти от "0000" к "0009".

Пример 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Объяснение: мы не можем достичь цели, не попав в тупик.

Ограничения:
1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target не может присутствовать в списке deadends
target и deadends[i] состоят только из цифр

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Рассмотрим задачу как поиск кратчайшего пути в графе.
Вершины графа - комбинации цифр на 4 дисках, каждый диск - одна позиция в комбинации. Некоторые вершины (deadends) заблокированы, мы не можем посещать их на пути к целевой вершине (target). Граф - невзвешенный, так как все рёбра имеют одинаковый вес (один поворот диска) => используем алгоритм поиска в ширину (BFS).

Начинаем обход с начального состояния '0000' (если оно в списке deadends - до target мы не дойдём, возвращаем -1), добавляем в очередь в виде кортежа (комбинация цифр и количество вращений). Все запрещённые комбинации сразу добавляем во множество visited, чтобы избежать попадания в тупик.

Пока очередь не пуста: извлекаем текущую комбинацию и количество вращений. Если комбинация соответствует target - возвращаем число вращений. Иначе: генерируем 8 следующих комбинаций, увеличивая и уменьшая каждую из 4 цифр (2 направления: 1 поворот диска вперёд и назад). Чтобы реализовать закольцованность дисков: деление по модулю (%10), "9" -> "0" при вращении диска вперёд ((9 + 1) % 10 = 0) и "0" -> "9" при вращении назад ((0 - 1) % 10 = 9).
Проверяем комбинацию: если ещё не посещена - добавляем в visited и помещаем в очередь, увеличивая количество вращений на 1.
Если очередь опустела, а target не достигнута - пути не существует, возвращаем -1.

Сложность
O(V + E) - по времени
O(V) - по памяти

Код
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if "0000" in deadends:
return -1

def new_combinations(node):
result = []
for i in range(4):
next_digit = (int(node[i]) + 1) % 10
result.append(node[:i] + str(next_digit) + node[i + 1:])

prev_digit = (int(node[i]) - 1) % 10
result.append(node[:i] + str(prev_digit) + node[i + 1:])
return result

q = deque([("0000", 0)])
visited = set(deadends)
visited.add("0000")

while q:
node, turns = q.popleft()
if node == target:
return turns
for combination in new_combinations(node):
if combination not in visited:
visited.add(combination)
q.append((combination, turns + 1))
return -1

@algoses

Задача с собеседования в eBay

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

Пример 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Пример 2:
Input: n = 1
Output: ["()"]

Ограничения:
1 <= n <= 8

НАШ ЧАТ АЛГОРИТМИСТОВ

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

Создаём два списка:
result - для хранения найденных правильных комбинаций;
combination - временный список для "собирания" текущей комбинации.
Запускаем рекурсивную функцию backtrack(open_count, close_count) для генерации комбинаций, отслеживая кол-во открывающих и закрывающих скобок.
Базовый случай: если длина текущей комбинации достигла n * 2 - добавляем готовую комбинацию в result и возвращаемся.
Рекурсивное ветвление: можем добавить открывающую, если ещё не использованы все n открывающих скобок. Можем добавить закрывающую, если кол-во открывающих скобок больше кол-ва закрывающих, это условие гарантирует, что у нас есть незакрытая открывающая скобка, которую можно закрыть.
Для каждого допустимого выбора:
- добавляем скобку в combination
- вызываем рекурсию с обновленными параметрами
- удаляем последнюю добавленную скобку для возврата к развилке и исследованию других путей построения последовательности.
Функция завершается, когда полностью исследовано дерево возможных комбинаций. Для начального вызова backtrack(0, 0) это означает, что исследованы все пути первого if, а путь второго if невозможен, так как последовательность не может начаться с закрывающей скобки.

Сложность
Экспоненциальная: O(4ⁿ/√n) - по времени (определяется n-ым числом Каталана Cₙ, равным кол-ву правильных скобочных последовательностей для n пар скобок); в кач-ве упрощения иногда говорят о сложности O(2**n)
O(n) - по памяти

Код
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
combination = []

def backtrack(open_count, close_count):
if len(combination) == 2 * n:
result.append("".join(combination))
return
if open_count < n:
combination.append("(")
backtrack(open_count + 1, close_count)
combination.pop()
if open_count > close_count:
combination.append(")")
backtrack(open_count, close_count + 1)
combination.pop()

backtrack(0, 0)
return result

@algoses

Задача с собеседования в eBay

Дана закодированная строка. Верните её в раскодированном виде.
Правило кодирования: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Гарантируется, что k - целое положительное число.

Считайте, что входная строка всегда корректна: нет лишних пробелов, квадратные скобки сформированы правильно и т.д.. Кроме того, можно считать, что исходные данные не содержат цифр, а цифры используются только для указания числа повторов k. Например, не будет таких входных данных, как 3a или 2[4].
Тестовые примеры сгенерированы так, что длина выходной строки никогда не превысит 10⁵.

Пример 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Пример 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"

Пример 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Ограничения:
1 <= s.length <= 30;
s состоит из строчных английских букв, цифр и квадратных скобок "[]";
s гарантированно является корректным входом;
Все целые числа в s находятся в диапазоне [1, 300].

НАШ ЧАТ АЛГОРИТМИСТОВ

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

Итерируемся по строке s:
Добавляем символ в стек, если он не является закрывающей скобкой.
Если же встречаем закрывающую скобку, начинаем собирать подстроку:
Пока верхний эл-т стека не является открывающей скобкой: извлекаем символы из стека и добавляем в начало substring.
Далее открывающую скобку из стека удаляем: мы обработали содержимое внутри скобок, теперь нужно получить число его повторов, находящееся перед открывающей скобкой.
Так как число k может быть многозначным, необходимо извлекать символы до тех пор, пока стек не пуст и верхний эл-т является цифрой.
Преобразовываем k в целое число и умножаем подстроку на него, добавляем результат в стек.
После того, как строка s будет полностью обработана, возвращаем итоговую строку, содержащую объединённые эл-ты стека.

Сложность
O(maxK^countK * n) - по времени (где maxK - максимальное значение k, countK - количество вложенных k значений (уровень вложенности), а n - максимальная длина закодированной строки)
O(n) - по памяти

Код
class Solution:
def decodeString(self, s: str) -> str:
stack = []

for char in s:
if char != "]":
stack.append(char)
else:
substring = ""
while stack[-1] != "[":
substring = stack.pop() + substring
stack.pop()

k = ""
while stack and stack[-1].isdigit():
k = stack.pop() + k
stack.append(int(k) * substring)

return "".join(stack)

@algoses

Задача с собеседования в Zendesk

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

Вы должны распределить деньги в соответствии со следующими правилами:
- Все деньги должны быть распределены;
- Каждый получает хотя бы 1 доллар;
- Никто не получает 4 доллара.

Верните максимальное количество детей, которые могут получить ровно 8 долларов, если вы распределите деньги согласно вышеуказанным правилам. Если распределить деньги невозможно, верните -1.

Пример 1:
Input: money = 20, children = 3
Output: 1
Explanation: Максимальное количество детей, которые получат 8 долларов, будет равно 1. Один из способов распределить деньги:
- 8 долларов первому ребёнку;
- 9 долларов второму ребёнку;
- 3 доллара третьему ребёнку.
Можно доказать, что не существует такого распределения, при котором количество детей, получающих 8 долларов, будет больше 1.

Пример 2:
Input: money = 16, children = 2
Output: 2
Explanation: Каждому ребёнку можно дать по 8 долларов.

Ограничения:
1 <= money <= 200
2 <= children <= 30

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Итак, нам нужно определить максимальное кол-во детей, которые могут получить ровно 8 долларов.
Сначала раздадим каждому по 1 обязательному доллару, чтобы гарантировать соблюдение правила. Оставшаяся после распределения сумма не должна быть отрицательной, иначе это означает, что детей было больше, чем долларов, и мы не смогли бы дать каждому даже по 1 доллару.
Оставшиеся деньги мы можем распределить дополнительно и раздать максимально возможному кол-ву детей ещё по 7 долларов => кол-во детей, которые могут получить ровно 8 долларов равно: remaining_money // 7.

Рассмотрим три случая:
1. Все дети получат по 8 долларов, если результат целочисленного деления будет равен количеству детей с остатком равным 0.

2. Если можем дать дополнительные 7 долларов всем, кроме одного, и при этом остаток денег равняется 3: мы вынуждены забрать доллар у ребёнка с 8 долларами и отдать его ребёнку с 4 долларами. Таким образом, у нас гарантированно будет 2 ребёнка, которые не смогут получить 8 долларов, не нарушая правила (значит, кол-во тех, кто сможет: children - 2).

3. Базовый случай: у нас есть два ограничения - кол-во денег (remaining_money // 7) и кол-во детей, которые могут получить 8 долларов с учётом того, что необходимо отдать остаток после распределения одному ребёнку (children - 1).
Ограничения должны быть соблюдены одновременно, поэтому мы выбираем самое строгое из них. То есть берём минимум, который и будет нашим максимально возможным кол-вом детей.

Сложность
O(1) - по времени
O(1) - по памяти

Код
class Solution:
def distMoney(self, money: int, children: int) -> int:
remaining_money = money - children

if remaining_money < 0:
return -1

if (remaining_money // 7 == children and remaining_money % 7 == 0):
return children

if (remaining_money // 7 == children - 1 and remaining_money % 7 == 3):
return children - 2

return min(children - 1, remaining_money // 7)

@algoses

Задача с собеседования в Zoho

Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно сделать n шагов.
Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки.
Сколькими различными способами вы можете подняться на вершину?

Пример 1:
Input: n = 2
Output: 2
Explanation: Существует два способа подняться на вершину:
1. 1 шаг + 1 шаг
2. 2 шага

Пример 2:
Input: n = 3
Output: 3
Explanation: Существует три способа подняться на вершину:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг

Ограничения:
1 <= n <= 45

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача помечена тегом "Dynamic Programming", оптимальным вариантом решения будет использование восходящего подхода с табуляцией, так мы избавимся от риска переполнения стека при глубокой рекурсии. Для оптимизации памяти до O(1) храним только две переменные (cur_step и prev_step) вместо dp массива.
Начинаем с базовых случаев (ступеньки 0 и 1), при которых ответ будет равен 1 способу => инициализируем наши две переменные значениями 1.
Запускаем цикл и поднимаемся вверх по лестнице со второй ступеньки, обновляя значения кол-ва способов подняться на предыдущую и текущую ступеньки, с каждой итерацией:
- текущая ступенька становится предыдущей;
- новая текущая ступенька равняется сумме способов подняться на две предыдущие ступеньки (по сути, классическая формула из задач о числах Фибоначчи: f(n) = f(n-1) + f(n-2)).
После окончания работы цикла выводим cur_step с последним вписанным в переменную значением.

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

Код
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1

cur_step, prev_step = 1, 1

for _ in range(2, n + 1):
prev_step, cur_step = cur_step, prev_step + cur_step

return cur_step

@algoses

Задача с собеседования в Zoho

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

Пример 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (заменить 'h' на 'r')
rorse -> rose (удалить 'r')
rose -> ros (удалить 'e')

Пример 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (удалить 't')
inention -> enention (заменить 'i' на 'e')
enention -> exention (заменить 'n' на 'x')
exention -> exection (заменить 'n' на 'c')
exection -> execution (вставить 'u')

Ограничения:
0 <= word1.length, word2.length <= 500
word1 и word2 состоят из строчных английских букв

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача помечена тегом "Dynamic Programming" и является классическим примером задачи на вычисление "расстояния Левенштейна". Используем восходящее dp с табуляцией.

Сначала разберём базовое решение, а потом оптимизируем:
Заполняем таблицу размером (len(word1) + 1) × (len(word2) + 1), где dp[i][j] - минимальное кол-во операций, необходимое для превращения первых i символов word1 в первые j символов word2.

i и j - это кол-во символов, поэтому dp[0][j] соответствует пустой word1, dp[i][0] - пустой word2.
Базовый случай, когда одна из строк пустая:
word1 пустая: нужно вставить все символы word2 (j вставок);
word2 пустая: нужно удалить все символы word1 (i удалений).

Остальные ячейки заполняем, смотря на последние символы текущих префиксов (word1[i-1] и word2[j-1]):
Если символы совпадают, нам не нужно ничего с ними делать, копируем значение из левой верхней ячейки;
Если символы не совпадают, есть три варианта действий, выбираем минимальный по кол-ву операций:
1. Замена: dp[i-1][j-1] + 1 - заменяем последний символ word1 на последний символ word2;
2. Удаление: dp[i-1][j] + 1 - удаляем последний символ из word1;
3. Вставка: dp[i][j-1] + 1 - вставляем последний символ word2 в word1.

Оптимизируем:
Храним не всю таблицу, а две переменные: prev (предыдущая строка, на первом шаге - первая строка таблицы) и cur (текущая строка, вначале заполнена нулями).
Если длина word1 меньше длины word2, меняем строки местами: более короткая строка становится word2, внутренний цикл идёт по ней, оптимизируя память до O(min(m, n)).

Во внешнем цикле: проходим по всем символам word1:
- в начале каждой итерации устанавливаем первый эл-т текущей строки: cur[0] = i. Это соответствует случаю, когда word2 пустая, поэтому нужно удалить все i символов из word1.
Во внутреннем: проходим по word2:
- символы совпадают: копируем значение из левой верхней ячейки (prev[j-1]);
- не совпадают: берём минимум из трёх значений:
prev[j-1] - замена символа word1[i-1] на word2[j-1]; обе строки становятся короче на 1, в таблице dp это диагональ.
prev[j] - удаление символа word1[i-1]; word1 становится короче, word2 - той же длины, в таблице это верх.
cur[j-1] - вставка символа word2[j-1] в word1; word2 - короче, word1 - той же длины, в таблице это значение слева.
+ 1, так как любая операция требует одного действия.

После заполнения строки меняем местами prev и cur, текущая строка становится предыдущей для следующей итерации.
После завершения циклов prev содержит последнюю заполненную строку, а её последний эл-т является ответом.

Сложность
O(mn) - по времени (проходим по всем парам символов)
O(min(m, n)) - по памяти

Код
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if len(word1) < len(word2):
word1, word2 = word2, word1

prev = list(range(len(word2) + 1))
cur = [0] * (len(word2) + 1)

for i in range(1, len(word1) + 1):
cur[0] = i
for j in range(1, len(word2) + 1):
if word1[i-1] == word2[j-1]:
cur[j] = prev[j-1]
else:
cur[j] = min(prev[j-1], prev[j], cur[j-1]) + 1

prev, cur = cur, prev

return prev[-1]

@algoses

Задача с собеседования в Zoho

Дана строка s, разверните (изменив порядок на обратный) только все гласные в строке и верните полученную строку.
Гласными являются буквы 'a', 'e', 'i', 'o', и 'u'. Они могут быть как в нижнем, так и в верхнем регистре, а также встречаться более одного раза.

Пример 1:
Input: "IceCreAm"
Output: "AceCreIm"
Explanation:
Гласные в s: ['I', 'e', 'e', 'A']. После разворота гласных s превращается в "AceCreIm".

Пример 2:
Input: s = "leetcode"
Output: "leotcede"

Ограничения:
1 <= s.length <= 3 * 105
s состоит из печатных символов ASCII.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Будем использовать метод двух указателей:
left - индекс первого элемента в списке (после преобразования строки в список)
right - индекс последнего элемента
Гласные храним во множестве для быстрой проверки за O(1).

Пока left меньше right: идём по строке в двух направлениях, проверяя символы, на которые указывают left и right.
Если символ слева - не гласная: сдвигаем левый указатель;
Если символ справа - не гласная: сдвигаем правый указатель;
Если оба символа - гласные: меняем их местами и двигаем оба указателя.

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

Сложность
O(n) - по времени (так как проходим по списку один раз)
O(n) - по памяти (так как создаём список из символов строки)

Код
class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
vowels = set("aeiouAEIOU")
left, right = 0, len(s) - 1

while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1

return "".join(s)

@algoses

Хэнбук по алгоритмам ШАД

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

@postypashki_old

Задача с собеседования в eBay

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

Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Пример 2:
Input: nums = [0]
Output: [0]

Ограничения:
1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Используем метод двух указателей, идём по массиву в одном направлении слева направо:
l - позиция, куда нужно поставить следующее ненулевое число
r - проходит по всем элементам массива

Проходим по массиву указателем r:
если r указывает на ненулевой элемент, меняем его местами с элементом на позиции l и двигаем левый указатель.

После завершения итерации с индексом r:
- все элементы до l будут ненулевыми;
- все элементы от l до r включительно - нули.

Вывод результата не требуется. Решение соблюдает принцип in-place (работаем с исходным массивом) и сохраняет порядок ненулевых элементов.

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

Код
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1

@algoses