Гранты на обучение в Центральном университете

Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета.

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

Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения.
Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие.
Для выпускников 10–11-х классов и СПО.

Участвуй в конкурсе уже сейчас!

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

В лимонадном киоске один стакан лимонада стоит 5 долларов. Покупатели стоят в очереди и приобретают лимонад в порядке, указанном в массиве bills. Каждый клиент покупает только один лимонад и платит одной из следующих купюр: 5, 10 или 20 долларов.
Вам необходимо дать правильную сдачу каждому клиенту, чтобы итоговая сумма, которую он заплатил, составила ровно 5 долларов. Имейте в виду, что вначале у вас нет денег для сдачи.

Задан целочисленный массив bills, где bills[i] - это купюра, которой расплачивается i-й любитель лимонада.
Верните true, если можете дать правильную сдачу каждому клиенту, или false в противном случае.

Пример 1:
Input: bills = [5,5,5,10,20]
Output: true

Пример 2:
Input: bills = [5,5,10,10,20]
Output: false

Чат алгоритмистов

Решение
Создаём переменные для хранения купюр, переменная twenty нам не нужна, потому что не будет использоваться в качестве сдачи.
Проходим по каждому элементу в массиве и обрабатываем платежи, увеличивая (принимая купюру) и/или уменьшая (при необходимости сдачи) счётчик переменной.
Проверяем возможность дать клиенту сдачу при каждом платеже, применяя жадный алгоритм. Ищем наиболее оптимальное решение на каждом шаге:
При оплате 10$ - выбора нет, отдаём купюру номиналом 5, и это наиболее оптимально в данном случае. Но если клиент платит 20$, предпочитаем дать сдачу с использованием купюры наибольшего номинала (10+5, а не 5+5+5), так как 5$ более универсальны и чаще могут понадобиться для размена.

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

Код

class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = 0
ten = 0

for b in bills:
if b == 5:
five += 1
elif b == 10:
if five < 1:
return False
else:
five -= 1
ten += 1
else:
if five >= 1 and ten >= 1:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True

@algoses

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

Дан массив интервалов, где intervals[i] = [starti, endi]. Необходимо объединить все пересекающиеся интервалы, а затем вернуть массив, состоящий из непересекающихся интервалов, которые покрывают все интервалы из входных данных.

Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Пример 2:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]

Чат алгоритмистов

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

2. Проходим по каждому отсортированному интервалу в массиве:

- добавляем новый интервал в список, если это первый интервал в списке ИЛИ если конец последнего интервала меньше начала текущего
(в merged лежит [1,6], а текущий интервал [8,10], 6 < 8 => интервалы не пересекаются => добавляем [8,10] как новый интервал).

- иначе объединяем его с последним интервалом и обновляем конец
(в merged лежит [1,3], текущий интервал = [2,6], они пересекающиеся, так как 3 ≥ 2. Обновляем конец объединённого интервала: max(3, 6) = 6, то есть [1,6]).

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

Код

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda interval: interval[0])
merged = []

for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])

return merged

@algoses

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

Даны три целых числа: x, y и z.
У вас есть x строк, равных "AA", y строк, равных "BB", и z строк, равных "AB". Вы хотите выбрать некоторое (возможно, все или ни одной) количество из этих строк и объединить их в некотором порядке, чтобы сформировать новую строку. Эта новая строка не должна содержать подстрок "AAA" или "BBB".
Известно, что подстрока - это непрерывная непустая последовательность символов внутри строки.
Верните максимально возможную длину новой строки.

Пример 1:
Input: x = 2, y = 5, z = 1
Output: 12
Объяснение: мы можем объединить строки "BB", "AA", "BB", "AA", "BB" и "AB" в таком порядке. Тогда наша новая строка будет "BBAABBAABBAB".
Длина этой строки равна 12, и мы можем показать, что невозможно сформировать строку большей длины.

Пример 2:
Input: x = 3, y = 2, z = 2
Output: 14
Объяснение: мы можем объединить строки "AB", "AB", "AA", "BB", "AA", "BB" и "AA" в таком порядке. Тогда наша новая строка будет "ABABAABBAABBAA".
Длина этой строки равна 14, и мы можем показать, что невозможно сформировать строку большей длины.

Ограничения:
1 <= x, y, z <= 50

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

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

Последовательности, которые мы можем соединять:
"AB" + "AA" = "ABAA"
"BB" + "AB" = "BBAB"
"AA" + "BB" = "AABB"

И те, которые НЕ можем:
"AA" + "AA" = "AAAA"
"BB" + "BB" = "BBBB"
"AA" + "AB" = "AAAB"

Строка "AB" самая безопасная и может использоваться для разбиения других последовательностей.
Если у нас равное количество строк "AA" и "BB" (x == y), то, чтобы высчитать максимальную длину строки нужно: сложить количество строк "AA", "BB" и "AB" и умножить сумму на 2 (по 2 символа в каждой строке).

Если же количество строк "AA" и "BB" различно, то: чередуем "AA" и "BB" столько раз, сколько можно. Далее, когда один из типов строк заканчивается, добавляем ещё одну строку противоположного типа. Так мы максимально продляем строку и не допускаем образования запрещённой подстроки.
Для наглядности:
Если x < y: ...AA + BB + AB - и дальше можем продолжать строку только типом "AB".
Если x > y: ...BB + AA или ...BB + AB + AA - и далее строку продолжать невозможно.

Определим, строк какого типа у нас меньше ("AA" или "BB"). Сформулируем формулу: мы используем все строки безопасного типа "AB" (по 2 символа в каждой: z * 2), также все строки того типа, которого у нас меньше (m * 2 символа), и строки противоположного типа в количестве, равном количеству строк менее частого типа + 1 ((m + 1)* 2 символа).

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

Код
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
m = min(x, y)
if x == y:
return 2 * (x + y + z)
else:
return 2 * m + (m + 1) * 2 + 2 * z

@algoses

В ИТМО открылся МЕГАКОВОРКИНГ Сбера 🔥

740 м² футуризма в историческом корпусе, очень большое студенческое пространство в университете с технологиями Умного дома Sber: умное освещение, климат-контроль, интеллектуальные колонки с ГигаЧат и интерактивные панели для командной работы. Пространство трансформируется под любые задачи — от тихих зон до переговорных и лектория.

На новоселье студенты протестировали все возможности: послушали воркшоп про карьеру в IT, пообщались с рекрутерами и зависали под живую музыку 💚

Подписывайся на СберСтудент!

Задача с собеседования в 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 января. Курсы для фаст трека на стажировку. Податься одновременно и на стажировку и на академию нельзя, только если с фейков. Задания уже выложены тут. Разбор алгоритмов для аналитиков и бэкендеров будет только на нашем курсе по алгоритмам, на который скидка заканчивается уже сегодня.

Как продакт-менеджеру выжить и вырасти в эпоху AI

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

Центральный университет запускает бесплатные открытые онлайн-уроки «Продуктовый менеджмент в эпоху AI».

Кто будет говорить:
— Ваня Замесин — автор AURA и Advanced JTBD, основатель курса «Как делать продукт»
— Глеб Кудрявцев — ex CPO Skyeng и автор курса «Вайб-кодинг на максималках»
— Илья Красинский — основатель & CEO Rick. ai и продуктового курса Product Heroes.
О чем пойдет речь:
— Какие навыки остаются базовыми для продакта в эпоху нейросетей.
— Что уже сегодня можно делать в 10 раз быстрее с AI.
— Как писать промпты, которые дают качественный результат.
— Почему понимание юнит-экономики остается важным навыком в любую эпоху.
— Зачем продакту вайб-кодинг и как меняется профессия.
Когда: уроки с 28 января по 2 февраля, в 19:00 мск.
Участие полностью бесплатное.

После уроков сможете попасть на интенсив для продакт-менеджеров с возможностью получить грант до 75% на обучение в магистратуре Центрального университета.

Регистрируйтесь уже сейчас!

Задача с собеседования в 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