В новом ролике обсудим изи темку, как получать офферы на 10 000$. Смотрим! Смотрим!
https://www.youtube.com/watch?v=ovYjaPpV6pw
https://www.youtube.com/watch?v=ovYjaPpV6pw
😁10❤1
Задача с собеседования в Zopsmart
Дана входная строка s. Переверните порядок слов в ней.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены хотя бы одним пробелом.
Верните строку, содержащую слова в обратном порядке, объединённые одним пробелом.
Обратите внимание, что строка s может содержать начальные или конечные пробелы, или несколько пробелов между двумя словами. В возвращаемой строке должен быть только один пробел между словами. Не включайте каких-либо лишних пробелов.
Follow-up: если строковый тип данных - изменяемый в вашем языке, можете ли вы решить задачу in-place c O(1) дополнительной памяти?
Пример 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Пример 2:
Input: s = " hello world "
Output: "world hello"
Пример 3:
Input: s = "a good example"
Output: "example good a"
Ограничения:
1 <= s.length <= 10⁴
s содержит буквы английского алфавита (в нижнем и верхнем регистре), цифры и пробелы ' '.
s состоит хотя бы из одного слова.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Так как в питоне строки неизменяемы, мы не можем реализовать решение in-place с O(1) дополнительной памяти.
Преобразуем строку в список строк методом split(), автоматически удаляя лишние пробелы - O(n).
Используем два указателя:
left - индекс первого слова в списке
right - индекс последнего слова
Пока left меньше right:
- меняем местами элементы под индексом left с элементами под индексом right;
- сдвигаем указатели навстречу друг другу.
В конце объединяем слова списка в строку через один пробел и возвращаем её.
Делитесь решением на вашем языке с O(1) дополнительной памяти в комментариях!
Сложность
O(n) - по времени (сплит и обход списка строк)
O(n) - по памяти (храним список строк)
Код
class Solution:
def reverseWords(self, s: str) -> str:
words = s.split()
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
return " ".join(words)
@algoses
Дана входная строка s. Переверните порядок слов в ней.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены хотя бы одним пробелом.
Верните строку, содержащую слова в обратном порядке, объединённые одним пробелом.
Обратите внимание, что строка s может содержать начальные или конечные пробелы, или несколько пробелов между двумя словами. В возвращаемой строке должен быть только один пробел между словами. Не включайте каких-либо лишних пробелов.
Follow-up: если строковый тип данных - изменяемый в вашем языке, можете ли вы решить задачу in-place c O(1) дополнительной памяти?
Пример 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Пример 2:
Input: s = " hello world "
Output: "world hello"
Пример 3:
Input: s = "a good example"
Output: "example good a"
Ограничения:
1 <= s.length <= 10⁴
s содержит буквы английского алфавита (в нижнем и верхнем регистре), цифры и пробелы ' '.
s состоит хотя бы из одного слова.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Преобразуем строку в список строк методом split(), автоматически удаляя лишние пробелы - O(n).
Используем два указателя:
left - индекс первого слова в списке
right - индекс последнего слова
Пока left меньше right:
- меняем местами элементы под индексом left с элементами под индексом right;
- сдвигаем указатели навстречу друг другу.
В конце объединяем слова списка в строку через один пробел и возвращаем её.
Делитесь решением на вашем языке с O(1) дополнительной памяти в комментариях!
Сложность
O(n) - по памяти (храним список строк)
Код
def reverseWords(self, s: str) -> str:
words = s.split()
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
return " ".join(words)
@algoses
❤5👍4🙏1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Завтра закончится отбора на стажировку в Т-банк
Если хотите летом выйти на стажировку с высокой зарплатой и опытом работы в bigteche, то подаваться нужно уже сейчас. На наших соответсвующих курсах уже выложен разбор математики и программирования, а на интенсиве по алгоритмам выложен разбор программирования.
📌 Специально к закрытию отбора
Скидка 35% на эти курсы с разборами до 28 апреля включительно.
Также на курсах будет доступно:
📌 Для записи на курс напишите менеджеру
Если хотите летом выйти на стажировку с высокой зарплатой и опытом работы в bigteche, то подаваться нужно уже сейчас. На наших соответсвующих курсах уже выложен разбор математики и программирования, а на интенсиве по алгоритмам выложен разбор программирования.
Скидка 35% на эти курсы с разборами до 28 апреля включительно.
Также на курсах будет доступно:
➡️ разборы контеста Яндекса, Летних школ Яндекса➡️ Сочные пет проекты в портфолио➡️ Огромный банк технических вопросов➡️ Записи реальных собесов и интервью➡️ Помощь с резюме и легендой
Please open Telegram to view this post
VIEW IN TELEGRAM
❤4
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
На наших соответсвующих курсах уже выложен разбор математики и программирования, а на интенсиве по алгоритмам выложен разбор программирования. На все последние 7 часов 35% скидки в честь конца отбора. Все подробности у администратора.
И не сомневаемся, это одна из лучших опций для получения первого опыта в индустрии: можно совмещать с учебой, загрузка от 20 часов в неделю, после нее легко залететь в штат и да, вам даже будут платить за нее! Для участия нужно просто заполнить анкету и решить отбор до 28 апреля. Задания на этот раз несложные (чекаем вот тут), но больше задач, где можно запросто ошибиться, специально сделали такие задачи, чтобы chatgpt путался с условиями и выдавал неправильные ответы и тех, кто спишет эти ответы, просто забанят в системе Т-банка. При этом из-за учебы подается меньше народу, все жесткие ботари заняты учебой, а значит у простых работяг куда больше шансов получить оффер! У топов собесы начнутся в мае, а у работяг в конце июня, когда сессия уже закончилась и есть силы и время, чтобы к ним подготовиться, еще не закончились.
Проходной на собес везде разный и зависит от популярности специальности и кол-во выделенных мест, региона. Где-то проход 350, а где-то 600 за контест. Далее отбор идет по анкете. Командам и HR очень важна ваша мотивация и погруженность в специальность. Будет обидно набрать полный балл за контест, но не заполнить анкету (подробный совет тоже даем участникам наших курсов). Общие советы такие: пишем про курсы, которые проходили и не проходили, фокусируем внимание на курсах от Т-банка. Только помните, что на собесе нужно будет не запутаться в этих выдумках. Обязательно пишем про олимпиадный опыт, даже школьный, от олимпиадников все просто сходят с ума. Пишем образование. Про свои стартапы и телеграмм каналы советую писать осторожно: это может отпугнуть. Подумают, что после года работы в штате вы уйдете строить свой мега успешный бизнес, а работодатель хочет, чтобы вы росли и развивались внутри компании и стали приносить пользу именной ей.
Сразу создаем второй телеграмм канал для работы и учебы с настоящим именем и фамилией, без тупых статусов и аниме на аватаре. Это серьезно очень раздражает рекрутеров. Также с этого аккаунта не пишем никому и некуда никакую неоднозначную ерунду, которая может стать народным достоянием и вас скомпрометировать. Работодателю важно, чтобы вы разделяли корпоративные ценности. Касаемо составления анкеты и резюме более подробно рассказывал в ролике, обязательно посмотрите.
Раньше большинство собесов было похоже на смотрины: команда рассказывала про себя, а вы про себя. Спрашивали мотивацию, бизнес кейс и может немного теории, задачи давали только на какого-нибудь риск аналитика. Сейчас все по-другому: контест не катает только ленивый, поэтому собесе почти всегда дают задачи. На аналитику и мл могут спросить матешу, скл, питон, а на разработчика и мл простенькие алгоритмы. Некоторые из этих заданий можно чекнуть тут, и тут, и тут, и тут, а если вы хотите разбор всех тасков с собесов - бегом на наши курсы.
Более подробно обо всем этом можно посмотреть в видео. Главное помните, что шанс выиграть в этой игре > 90% (по крайней мере, в прошлом году именно таким был процент взятых на стажировку среди наших учеников), если знать правила игры. Серьезно, прошлым летом выпускница нашего курса по аналитике прошла отбор и стала стажером-аналитиком едва закончив 11-ый класс.
@postypashki_old
Please open Telegram to view this post
VIEW IN TELEGRAM
😁3❤1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Товарищи, заполняем анкеты если ещё не сделали и приступаем к онлайн-тестированию. Время до 3 мая.
Если сомневаешься, стоит ли пробовать поступать в этом году, то пробуй сейчас. Те, кто откладывают поступление на следующий год, откладывают и дальше. Сейчас лучший момент, чтобы задуматься о своем будущем.
Специально в честь отбора открываем дополнительные места на интенсиве к ШАД с разбором первого этапа. Все участники получают:
Сегодня и завтра на интенсивы скидка 35%
Количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Задача с собеседования в Zopsmart
Даны строки s и t длиной m и n, соответственно. Верните минимальную подстроку (подстроку окна) строки s такую, что каждый символ из строки t (включая повторяющиеся) содержится в этом окне. Если такой подстроки не существует, верните пустую строку "".
Тестовые данные составлены таким образом, чтобы ответ был уникальным.
Follow up: можете ли вы найти алгоритм, работающий за O(m + n) по времени?
Пример 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Объяснение: Подстрока минимального окна "BANC" включает символы 'A', 'B' и 'C' из строки t.
Пример 2:
Input: s = "a", t = "a"
Output: "a"
Объяснение: Вся строка s является минимальным окном.
Пример 3:
Input: s = "a", t = "aa"
Output: ""
Объяснение: Обе 'a' из строки t должны быть включены в окно. Поскольку самое большое окно s имеет только одну 'a', возвращаем пустую строку.
Ограничения:
m == s.length
n == t.length
1 <= m, n <= 10⁵
s и t состоят из английских букв верхнего и нижнего регистра.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем алгоритм "скользящего окна" с двумя указателями и хэш-таблицу.
Расширяем окно правым указателем, пока не набираем все необходимые символы. Когда окно становится валидным, пробуем сжать его левым указателем, избавляясь от лишних символов, пока окно не перестанет удовлетворять условиям.
Создаём два словаря:
freqT - хранит частоту символов строки t, не изменяется;
freqWindow - хранит частоту символов текущего окна, изменяется при движении указателей.
Заполняем словарь freqT:
- С помощью метода get(ch, 0) возвращаем текущую частоту символа, либо 0, если символ ещё не встречался. Увеличиваем счётчик символа на 1.
Переменные:
need - кол-во уникальных символов в t, которые нужно набрать;
have - кол-во уникальных символов, которые уже есть в текущем окне.
res - индексы минимального найденного окна;
resLen - длина минимального окна (float("inf"), чтобы записать первое валидное окно в кач-ве минимального).
Расширяем окно, проходя по строке s указателем r:
- Добавляем каждый новый символ в словарь freqWindow и увеличиваем его частоту на 1;
- Если текущий символ находится в freqT и после добавления его частота в freqWindow равна требуемой в freqT: увеличиваем have.
Сжимаем окно, пока текущее окно содержит все необходимые символы:
- Сравниваем длину окна с длиной найденного ранее (resLen). Если текущее окно короче: сохраняем его индексы в res и обновляем resLen;
- Так как будем сдвигать левый указатель: текущий символ под его индексом покинет окно - уменьшаем счётчик этого символа в freqWindow на 1;
- Проверяем, осталось ли окно валидным:
если s[l] есть в freqT и кол-во символа в freqWindow меньше, чем необходимо (freqT), значит, мы потеряли один из требуемых уникальных символов - уменьшаем have на 1;
- Сдвигаем левый указатель вправо.
Если have становится меньше need, цикл завершается, мы возвращаемся к расширению окна правым указателем.
Возвращаем срез по сохранённым индексам минимального найденного окна.
Сложность
O(m + n) - по времени (l и r двигаются только вправо и ограничены длиной s - O(m), заполнение freqT по строке t - O(n))
O(1) - по памяти (фиксированное кол-во букв алфавита)
Код
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
freqT, freqWindow = {}, {}
for ch in t:
freqT[ch] = 1 + freqT.get(ch, 0)
need, have = len(freqT), 0
res, resLen = [-1, -1], float("inf")
l = 0
for r in range(len(s)):
ch = s[r]
freqWindow[ch] = 1 + freqWindow.get(ch, 0)
if ch in freqT and freqWindow[ch] == freqT[ch]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = (r - l + 1)
freqWindow[s[l]] -= 1
if s[l] in freqT and freqWindow[s[l]] < freqT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l:r+1] if resLen != float("inf") else ""
@algoses
Даны строки s и t длиной m и n, соответственно. Верните минимальную подстроку (подстроку окна) строки s такую, что каждый символ из строки t (включая повторяющиеся) содержится в этом окне. Если такой подстроки не существует, верните пустую строку "".
Тестовые данные составлены таким образом, чтобы ответ был уникальным.
Follow up: можете ли вы найти алгоритм, работающий за O(m + n) по времени?
Пример 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Объяснение: Подстрока минимального окна "BANC" включает символы 'A', 'B' и 'C' из строки t.
Пример 2:
Input: s = "a", t = "a"
Output: "a"
Объяснение: Вся строка s является минимальным окном.
Пример 3:
Input: s = "a", t = "aa"
Output: ""
Объяснение: Обе 'a' из строки t должны быть включены в окно. Поскольку самое большое окно s имеет только одну 'a', возвращаем пустую строку.
Ограничения:
m == s.length
n == t.length
1 <= m, n <= 10⁵
s и t состоят из английских букв верхнего и нижнего регистра.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Расширяем окно правым указателем, пока не набираем все необходимые символы. Когда окно становится валидным, пробуем сжать его левым указателем, избавляясь от лишних символов, пока окно не перестанет удовлетворять условиям.
Создаём два словаря:
freqT - хранит частоту символов строки t, не изменяется;
freqWindow - хранит частоту символов текущего окна, изменяется при движении указателей.
Заполняем словарь freqT:
- С помощью метода get(ch, 0) возвращаем текущую частоту символа, либо 0, если символ ещё не встречался. Увеличиваем счётчик символа на 1.
Переменные:
need - кол-во уникальных символов в t, которые нужно набрать;
have - кол-во уникальных символов, которые уже есть в текущем окне.
res - индексы минимального найденного окна;
resLen - длина минимального окна (float("inf"), чтобы записать первое валидное окно в кач-ве минимального).
Расширяем окно, проходя по строке s указателем r:
- Добавляем каждый новый символ в словарь freqWindow и увеличиваем его частоту на 1;
- Если текущий символ находится в freqT и после добавления его частота в freqWindow равна требуемой в freqT: увеличиваем have.
Сжимаем окно, пока текущее окно содержит все необходимые символы:
- Сравниваем длину окна с длиной найденного ранее (resLen). Если текущее окно короче: сохраняем его индексы в res и обновляем resLen;
- Так как будем сдвигать левый указатель: текущий символ под его индексом покинет окно - уменьшаем счётчик этого символа в freqWindow на 1;
- Проверяем, осталось ли окно валидным:
если s[l] есть в freqT и кол-во символа в freqWindow меньше, чем необходимо (freqT), значит, мы потеряли один из требуемых уникальных символов - уменьшаем have на 1;
- Сдвигаем левый указатель вправо.
Если have становится меньше need, цикл завершается, мы возвращаемся к расширению окна правым указателем.
Возвращаем срез по сохранённым индексам минимального найденного окна.
Сложность
O(1) - по памяти (фиксированное кол-во букв алфавита)
Код
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
freqT, freqWindow = {}, {}
for ch in t:
freqT[ch] = 1 + freqT.get(ch, 0)
need, have = len(freqT), 0
res, resLen = [-1, -1], float("inf")
l = 0
for r in range(len(s)):
ch = s[r]
freqWindow[ch] = 1 + freqWindow.get(ch, 0)
if ch in freqT and freqWindow[ch] == freqT[ch]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = (r - l + 1)
freqWindow[s[l]] -= 1
if s[l] in freqT and freqWindow[s[l]] < freqT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l:r+1] if resLen != float("inf") else ""
@algoses
❤8🔥1
Задача с собеседования в Zopsmart
Дана голова односвязного списка. Разверните список и верните его.
Follow-up: связный список можно развернуть как итеративно, так и рекурсивно. Могли бы вы реализовать оба способа?
Пример 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Пример 2:
Input: head = [1,2]
Output: [2,1]
Пример 3:
Input: head = []
Output: []
Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000].
-5000 <= Node.val <= 5000
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
В односвязном списке каждый узел хранит данные и ссылку на следующий элемент (или None, если узел последний).
Чтобы развернуть список, нужно изменить указатели всех узлов на противоположные.
Итеративно:
reversed_head - голова развёрнутого списка (сначала None, так как развёрнутый список пуст).
head - узел, с которым работаем (текущий обрабатываемый узел исходного списка).
head.next - указатель текущего узла, его направление будем менять.
Идём до конца исходного списка, на каждой итерации обрабатывая head:
- сохраняем узел, следующий за head, в переменную next_node, чтобы не потерять остаток списка после разрыва связи между узлами;
- операция разворота: указатель текущего узла теперь указывает на голову развёрнутой части;
- обновляем голову развёрнутой части: теперь она начинается с текущего узла;
- переходим к сохраненному остатку исходного списка.
В конце возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (проходим по списку один раз)
O(1) - по памяти (храним три указателя, разворачиваем ссылки на месте)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
reversed_head = None
while head:
next_node = head.next
head.next = reversed_head
reversed_head = head
head = next_node
return reversed_head
Рекурсивно:
Сначала уходим в конец списка, достигая базового случая, а потом идём в обратном порядке, переворачивая указатели.
Базовый случай:
если исходный список пуст или следующий узел отсутствует. Последний узел становится головой развёрнутого списка, рекурсия останавливается.
Рекурсивный случай:
вызываем функцию для остатка исходного списка и получаем reversed_head - последний узел исходного списка, ставший головой (ссылка на него не меняется во время работы алгоритма).
После достижения базового случая поднимаемся по стеку вызовов:
- меняем указатель у узла, следующего за head, на head. Теперь они ссылаются друг на друга;
- разрываем старую связь между узлами: head указывает на None и становится последним узлом в развёрнутой части;
- возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (кол-во вызовов равно длине списка)
O(n) - по памяти (рекурсия линейная)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next :
return head
reversed_head = self.reverseList( head.next )
head.next.next = head
head.next = None
return reversed_head
@algoses
Дана голова односвязного списка. Разверните список и верните его.
Follow-up: связный список можно развернуть как итеративно, так и рекурсивно. Могли бы вы реализовать оба способа?
Пример 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Пример 2:
Input: head = [1,2]
Output: [2,1]
Пример 3:
Input: head = []
Output: []
Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000].
-5000 <= Node.val <= 5000
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Чтобы развернуть список, нужно изменить указатели всех узлов на противоположные.
Итеративно:
head - узел, с которым работаем (текущий обрабатываемый узел исходного списка).
Идём до конца исходного списка, на каждой итерации обрабатывая head:
- сохраняем узел, следующий за head, в переменную next_node, чтобы не потерять остаток списка после разрыва связи между узлами;
- операция разворота: указатель текущего узла теперь указывает на голову развёрнутой части;
- обновляем голову развёрнутой части: теперь она начинается с текущего узла;
- переходим к сохраненному остатку исходного списка.
В конце возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (проходим по списку один раз)
O(1) - по памяти (храним три указателя, разворачиваем ссылки на месте)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
reversed_head = None
while head:
next_node =
reversed_head = head
head = next_node
return reversed_head
Рекурсивно:
Базовый случай:
если исходный список пуст или следующий узел отсутствует. Последний узел становится головой развёрнутого списка, рекурсия останавливается.
Рекурсивный случай:
вызываем функцию для остатка исходного списка и получаем reversed_head - последний узел исходного списка, ставший головой (ссылка на него не меняется во время работы алгоритма).
После достижения базового случая поднимаемся по стеку вызовов:
- меняем указатель у узла, следующего за head, на head. Теперь они ссылаются друг на друга;
- разрываем старую связь между узлами: head указывает на None и становится последним узлом в развёрнутой части;
- возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (кол-во вызовов равно длине списка)
O(n) - по памяти (рекурсия линейная)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not
return head
reversed_head = self.reverseList(
return reversed_head
@algoses
🔥8❤3
Последний шанс ворваться в Баттл вузов: турнир по программированию с призом в 1 млн рублей!
Первый тур закрывается уже 20 мая, но у вас еще есть возможность принять участие. Нужно решить 10 задач и набрать как можно больше баллов, чтобы попасть во второй тур.
Участвовать могут студенты, абитуриенты и выпускники вузов. Чем больше регистраций от вуза, тем больше шансов, что кубок Young&&Yandex попадет именно в ваш университет!
200 лучших кодеров попадут в финал на фестивале Young Con 2026. Все финалисты получат призы от Умного дома, а победитель турнира выиграет 1 млн рублей!
Не упусти возможность показать свои скиллы всей стране: регистрируйся на первый тур до 20 мая.
Первый тур закрывается уже 20 мая, но у вас еще есть возможность принять участие. Нужно решить 10 задач и набрать как можно больше баллов, чтобы попасть во второй тур.
Участвовать могут студенты, абитуриенты и выпускники вузов. Чем больше регистраций от вуза, тем больше шансов, что кубок Young&&Yandex попадет именно в ваш университет!
200 лучших кодеров попадут в финал на фестивале Young Con 2026. Все финалисты получат призы от Умного дома, а победитель турнира выиграет 1 млн рублей!
Не упусти возможность показать свои скиллы всей стране: регистрируйся на первый тур до 20 мая.
❤2🔥2
Поступить в вуз мечты и не платить за учёбу? Это реально!
Центральный университет — российский вуз нового типа, внедряющий STEM-подход в высшее образование. Университет создан в партнерстве с более чем 70 крупнейшими компаниями и организациями: Сбер, Авито, VK, Яндекс, Т-Банк и другие.
Здесь не просто дают знания, а формируют специалистов, которых ждут в индустрии.
Обучение ведется по программам:
— разработка;
— искусственный интеллект;
— бизнес и аналитика;
— дизайн;
— машинное обучение;
— продуктовый менеджмент;
— бэкенд разработка.
А еще каждый студент может получить грант до 100% на весь срок обучения.
Хочешь узнать подробнее? Приходи на МЕГАДОД 2026!
24 мая, с 12:00 до 15:30.
Очно в кампусе Центрального университета (Москва, м. Маяковская).
На мероприятии ты:
• узнаешь про программы бакалавриата и магистратуры, процесс обучения и карьерные перспективы;
• услышишь выступления академических руководителей и преподавателей;
• узнаешь про новые программы 2026;
• увидишь кампус изнутри, пообщаешься со студентами, посетишь мастер-классы и интерактивные станции.
Не упусти возможность учиться в одном из лучших вузов сферы!
Зарегистрироваться
Центральный университет — российский вуз нового типа, внедряющий STEM-подход в высшее образование. Университет создан в партнерстве с более чем 70 крупнейшими компаниями и организациями: Сбер, Авито, VK, Яндекс, Т-Банк и другие.
Здесь не просто дают знания, а формируют специалистов, которых ждут в индустрии.
Обучение ведется по программам:
— разработка;
— искусственный интеллект;
— бизнес и аналитика;
— дизайн;
— машинное обучение;
— продуктовый менеджмент;
— бэкенд разработка.
А еще каждый студент может получить грант до 100% на весь срок обучения.
Хочешь узнать подробнее? Приходи на МЕГАДОД 2026!
24 мая, с 12:00 до 15:30.
Очно в кампусе Центрального университета (Москва, м. Маяковская).
На мероприятии ты:
• узнаешь про программы бакалавриата и магистратуры, процесс обучения и карьерные перспективы;
• услышишь выступления академических руководителей и преподавателей;
• узнаешь про новые программы 2026;
• увидишь кампус изнутри, пообщаешься со студентами, посетишь мастер-классы и интерактивные станции.
Не упусти возможность учиться в одном из лучших вузов сферы!
Зарегистрироваться
😁3❤1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Набор на карьерные курсы продолжается!
Первые семинары по A/B-тестам, Data Science и Data Engineering стартуют уже в эти выходные. Успеете начать полноценную подготовку, чтобы летом уже получить оффер и выйти на работу!
Наши курсы единственные на рынке, которые заточены именно на получение оффера, где за 6 недель закрываем все темы, которые спрашивают на собесах, разбираем задачи из реальных отборов и готовим к каждому этапу - от резюме до финального интервью и испытательного срока.
Преподаватели - ведущие практики из Сбера, Wildberries, Ozon, МТС, которые сами проводят собесы.
Что доступно участникам курса:
➡️ закрытый банк собесов Яндекс, Т-Банк, Ozon, WB, Авито
➡️ пробное собеседование и разбор резюме
➡️ сдашь пет-проект - получишь рефералку в бигтех
Гарантия возврата: если выполнишь все рекомендации и не получишь оффер - вернём деньги.
До 21.05 можно записаться со скидкой 35% !
Цена за один курс — 6 950 ₽10 950
За два курса — 12 900 ₽21 900
За три курса — 17 850 ₽32 850
📌 Для вопросов и записи на интенсивы напиши менеджеру. Количество мест на каждый курс ограниченно.
Первые семинары по A/B-тестам, Data Science и Data Engineering стартуют уже в эти выходные. Успеете начать полноценную подготовку, чтобы летом уже получить оффер и выйти на работу!
Наши курсы единственные на рынке, которые заточены именно на получение оффера, где за 6 недель закрываем все темы, которые спрашивают на собесах, разбираем задачи из реальных отборов и готовим к каждому этапу - от резюме до финального интервью и испытательного срока.
Преподаватели - ведущие практики из Сбера, Wildberries, Ozon, МТС, которые сами проводят собесы.
Что доступно участникам курса:
Гарантия возврата: если выполнишь все рекомендации и не получишь оффер - вернём деньги.
До 21.05 можно записаться со скидкой 35% !
Цена за один курс — 6 950 ₽
За два курса — 12 900 ₽
За три курса — 17 850 ₽
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Задача с собеседования в eBay
Коко любит есть бананы. Имеется n куч бананов, где i-я куча содержит piles[i] бананов. Охранники ушли и вернутся через h часов.
Коко может выбрать скорость поедания бананов в час (равняется k). Каждый час она выбирает какую-либо кучу и съедает k бананов из неё. Если в выбранной куче меньше k бананов, она съедает их все и в течение этого часа больше не ест.
Коко любит есть медленно, но хочет успеть съесть все бананы до возвращения охранников.
Верните минимальное целое число k, при котором Коко сможет съесть все бананы в течение h часов.
Пример 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Пример 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Пример 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Ограничения:
1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем бинарный поиск, а точнее бинарный поиск по ответу: если Коко успеет съесть все бананы при некоторой скорости k, значит, она сможет их съесть и при любой скорости больше k (свойство монотонности). Таким образом, можно отбросить половину диапазона поиска.
В отличие от классического бинпоиска здесь не требуется сортировка входных данных, так как искать результат будем не в массиве piles, а в уже упорядоченном диапазоне скоростей (левую границу определим как 1, а правую - как max(piles)). Порядок самих куч не влияет на сумму часов.
- Определяем исходный диапазон поиска: l = 1 (минимальная возможная скорость), r = max(piles) (кол-во бананов в самой большой куче, так как в любом случае нельзя съесть кучу быстрее, чем за час);
- Задаём условие для перехода в левую или правую половину: в цикле бинарного поиска вычисляем среднюю скорость.
Проходим по всем кучам и считаем кол-во часов, за которые Коко съест все бананы при текущем гипотетическом значении k: hours += (p + k - 1) // k
Формула вычисления часов работает следующим образом:
к примеру, Коко успевает съесть за час все бананы из кучи, кроме 1. На этот 1 банан в любом случае нужен 1 дополнительный час, в течение которого Коко съест только его, не начиная новую кучу. То есть нам требуется округление вверх (целочисленное деление в питоне по умолчанию округляет вниз).
Нужно добавить такое кол-во бананов, чтобы и получить необходимый дополнительный час при наличии остатка, и корректно обработать числа без остатка. Значение, которое сработает в любом из двух случаев - это прибавка k - 1 (максимальное значение, не создающее дополнительные часы, когда у нас нет остатка).
Предположим, p = 11, а k = 5. При простом делении p // k получили бы 2, и один банан остался бы без учёта при подсчёте часов. Но если пользуемся формулой (11 + 5 -1) // 5, получаем 3 часа, которые потребуются, чтобы съесть 11 бананов со скоростью 5 бананов/час.
А если бы в другой куче было 15 бананов, которые делятся на 5 без остатка, формула тоже сработала бы: (15 + 5 - 1) // 5 = 3 (всё те же 3 часа, так как целочисленное деление просто отбросит остаток 4);
- Сдвигаем границы поиска:
Если Коко успевает съесть все бананы: запоминаем k как текущего кандидата, обновляя res, и сдвигаем правую границу поиска влево (пытаемся найти ещё меньшую скорость);
Если не успевает: сдвигаем левую границу вправо, так как нужно искать среди больших скоростей;
Возвращаем минимальную возможную скорость, при которой Коко сможет съесть все бананы, уложившись в h часов.
Сложность
O(n log m) - по времени (где n - кол-во куч бананов, а m - максимальное кол-во бананов в куче)
O(1) - по памяти (храним только переменные, не создавая дополнительных структур данных)
Код
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = r
while l <= r:
k = (l + r) // 2
hours = 0
for p in piles:
hours += (p + k - 1) // k
if hours <= h:
res = min(res, k)
r = k - 1
else:
l = k + 1
return res
@algoses
Коко любит есть бананы. Имеется n куч бананов, где i-я куча содержит piles[i] бананов. Охранники ушли и вернутся через h часов.
Коко может выбрать скорость поедания бананов в час (равняется k). Каждый час она выбирает какую-либо кучу и съедает k бананов из неё. Если в выбранной куче меньше k бананов, она съедает их все и в течение этого часа больше не ест.
Коко любит есть медленно, но хочет успеть съесть все бананы до возвращения охранников.
Верните минимальное целое число k, при котором Коко сможет съесть все бананы в течение h часов.
Пример 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Пример 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Пример 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Ограничения:
1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
В отличие от классического бинпоиска здесь не требуется сортировка входных данных, так как искать результат будем не в массиве piles, а в уже упорядоченном диапазоне скоростей (левую границу определим как 1, а правую - как max(piles)). Порядок самих куч не влияет на сумму часов.
- Определяем исходный диапазон поиска: l = 1 (минимальная возможная скорость), r = max(piles) (кол-во бананов в самой большой куче, так как в любом случае нельзя съесть кучу быстрее, чем за час);
- Задаём условие для перехода в левую или правую половину: в цикле бинарного поиска вычисляем среднюю скорость.
Проходим по всем кучам и считаем кол-во часов, за которые Коко съест все бананы при текущем гипотетическом значении k: hours += (p + k - 1) // k
Формула вычисления часов работает следующим образом:
к примеру, Коко успевает съесть за час все бананы из кучи, кроме 1. На этот 1 банан в любом случае нужен 1 дополнительный час, в течение которого Коко съест только его, не начиная новую кучу. То есть нам требуется округление вверх (целочисленное деление в питоне по умолчанию округляет вниз).
Нужно добавить такое кол-во бананов, чтобы и получить необходимый дополнительный час при наличии остатка, и корректно обработать числа без остатка. Значение, которое сработает в любом из двух случаев - это прибавка k - 1 (максимальное значение, не создающее дополнительные часы, когда у нас нет остатка).
Предположим, p = 11, а k = 5. При простом делении p // k получили бы 2, и один банан остался бы без учёта при подсчёте часов. Но если пользуемся формулой (11 + 5 -1) // 5, получаем 3 часа, которые потребуются, чтобы съесть 11 бананов со скоростью 5 бананов/час.
А если бы в другой куче было 15 бананов, которые делятся на 5 без остатка, формула тоже сработала бы: (15 + 5 - 1) // 5 = 3 (всё те же 3 часа, так как целочисленное деление просто отбросит остаток 4);
- Сдвигаем границы поиска:
Если Коко успевает съесть все бананы: запоминаем k как текущего кандидата, обновляя res, и сдвигаем правую границу поиска влево (пытаемся найти ещё меньшую скорость);
Если не успевает: сдвигаем левую границу вправо, так как нужно искать среди больших скоростей;
Возвращаем минимальную возможную скорость, при которой Коко сможет съесть все бананы, уложившись в h часов.
Сложность
O(1) - по памяти (храним только переменные, не создавая дополнительных структур данных)
Код
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = r
while l <= r:
k = (l + r) // 2
hours = 0
for p in piles:
hours += (p + k - 1) // k
if hours <= h:
res = min(res, k)
r = k - 1
else:
l = k + 1
return res
@algoses
❤6
2 недели бесплатного обучения и возможность получить оффер на оплачиваемую стажировку 🧑💻
Почему стоит попробовать:
🤩 возможность получить оффер
🤩 новые скиллы для резюме
🤩 закрытие практики для вуза
🤩 стильный мерч
🤩 погружение в культуру (и вкусные обеды каждый день)
Узнать больше можно по ссылке!
🎁 🎁 p.s. а еще можно рекомендовать друзей через реферальную программу и получить за это подарок !
Компания КРОК открыла регистрацию на Летнюю ИТ-школу 2026 для студентов и недавних выпускников. Открытые треки:🤩 Телекоммуникации – для тех, кому интересны сетевые технологии🤩 ИТ-аналитика – для тех, кому интересны автоматизация бизнес-процессов, ведение ИТ-проектов и анализ данных
Почему стоит попробовать:
Узнать больше можно по ссылке!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Финальные скидки на карьерные курсы!
Товарищи, специально для вас открываем доступ на линейку карьерных курсов по A/B-тестам, Data Science и Data Engineering со скидкой 40%!
Курсы подойдут всем, кто хочет прокачаться уверенно проходить интервью в топовые компании, решать реальные рабочие задачи.
Вы научитесь решать задачи с реальных отборочных, поймете, как уверенно отвечать на вопросы интервьюера, сделаете пет-проект и пройдёте mock интервью, а также получите помощь с оставлением резюме, с испытательным сроком.
Что входит в каждый курс:
📌 Распродажа 40% действует только до 4 июня включительно
Цена за 1 курс -10 950 6 950 ₽
При покупке от 2-х курсов -9 650 6 450 ₽ за курс
При покупке от 3-х и более -9 150 5 950 ₽ за курс
Гарантия возврата: если выполнишь все рекомендации и не получишь оффер - вернём деньги.
Отзывы доступны здесь
➡️ Советуем не затягивать. Для вопросов и записи на курсы напишите менеджеру
Товарищи, специально для вас открываем доступ на линейку карьерных курсов по A/B-тестам, Data Science и Data Engineering со скидкой 40%!
Курсы подойдут всем, кто хочет прокачаться уверенно проходить интервью в топовые компании, решать реальные рабочие задачи.
Вы научитесь решать задачи с реальных отборочных, поймете, как уверенно отвечать на вопросы интервьюера, сделаете пет-проект и пройдёте mock интервью, а также получите помощь с оставлением резюме, с испытательным сроком.
Что входит в каждый курс:
🔵 Разбор контеста стажировки в Яндекс🔵 ДЗ и пет-проект с обратной связью от преподавателя🔵 Банк заданий и вопросов с собеседований в BigTech🔵 Пробный тех.собес с обратной связью от эксперта🔵 Поддержку на всех этапах отбора: от составления резюме до испытательного срока
Цена за 1 курс -
При покупке от 2-х курсов -
При покупке от 3-х и более -
Гарантия возврата: если выполнишь все рекомендации и не получишь оффер - вернём деньги.
Отзывы доступны здесь
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Задача с собеседования в Zynga
Дан массив целых чисел asteroids, представляющий астероиды, расположенные в ряд. Индексы элементов массива соответствуют их относительному положению в пространстве.
Для каждого астероида абсолютное значение (модуль) определяет его размер, а знак - направление движения (положительный означает движение вправо, отрицательный - влево). Все астероиды движутся с одинаковой скоростью.
Определите состояние астероидов после всех столкновений. Если два астероида встречаются, взрывается меньший из них. Если их размеры равны, взрываются оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Объяснение: 10 и -5 сталкиваются, в результате остаётся 10. 5 и 10 никогда не столкнутся.
Пример 2:
Input: asteroids = [8,-8]
Output: []
Объяснение: 8 и -8 сталкиваются, взрывая друг друга.
Пример 3:
Input: asteroids = [10,2,-5]
Output: [10]
Объяснение: 2 и -5 сталкиваются, в результате остаётся -5. 10 и -5 сталкиваются, остаётся 10.
Пример 4:
Input: asteroids = [3,5,-6,2,-1,4]
Output: [-6,2,4]
Объяснение: Астероид -6 взрывает астероиды 5 и 3, затем продолжает двигаться влево. С другой стороны, астероид 2 взрывает астероид -1 и продолжает двигаться вправо, не сталкиваясь с астероидом 4.
Ограничения:
2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Столкновение происходит между соседними астероидами (они могут не быть соседями в изначальном массиве, а стать ими после взрывов), летящими в разные стороны (с противоположными знаками). И только в том случае, когда астероид, летящий вправо, находится левее астероида, летящего влево. Иначе астероиды просто разлетятся в разные стороны и никогда не столкнутся. Так произойдёт, например, при asteroids = [-1, -2, 1, 2]. Однако при [1, -1, 2, -2], они взорвут друг друга, и стек окажется пуст.
- Используем стек для хранения астероидов, которые ещё не столкнулись или пережили столкновение. Стек удобен тем, что позволяет проверять верхний астероид (последний добавленный) на столкновение с левым. Верхний - ближайший справа к левому, при его взрыве левый продолжит движение и проверит следующий (добавленный раньше) астероид в стеке, который автоматически станет новым ближайшим.
- Симулируем движение:
В цикле while (while позволяет проверять левый астероид на столкновение с несколькими правыми подряд) имитируем столкновение: стек должен быть не пуст, текущий астероид должен лететь влево, а верхний астероид в стеке - лететь вправо:
Чтобы определить, какой взорвётся, высчитываем разницу между их размерами посредством суммирования. Так как мы зашли в цикл while, текущий a всегда отрицательный, а stack[-1] - положительный, знак diff покажет, какой астероид больше:
- если diff отрицательный - левый больше => правый взрывается => удаляем его из стека => левый остаётся и продолжает цикл while, проверяя следующий астероид в стеке;
- если diff положительный - правый больше => левый взрывается, правый остаётся в стеке => обнуляем значение левого, цикл while завершается, так как условие a < 0 больше не выполняется;
- если значение diff равно нулю - размеры равны => оба взрываются => обнуляем левый и удаляем правый из стека, цикл завершается.
- Если после столкновений текущий астероид не равен 0, значит, он выжил. Добавляем его в стек.
Сложность
O(n) - по времени (проходим по массиву 1 раз, каждый астероид может быть добавлен в стек или удалён из него не более 1 раза)
O(n) - по памяти (в худшем случае храним в стеке все элементы массива)
Код
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and a < 0 < stack[-1]:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
a = 0
stack.pop()
if a:
stack.append(a)
return stack
@algoses
Дан массив целых чисел asteroids, представляющий астероиды, расположенные в ряд. Индексы элементов массива соответствуют их относительному положению в пространстве.
Для каждого астероида абсолютное значение (модуль) определяет его размер, а знак - направление движения (положительный означает движение вправо, отрицательный - влево). Все астероиды движутся с одинаковой скоростью.
Определите состояние астероидов после всех столкновений. Если два астероида встречаются, взрывается меньший из них. Если их размеры равны, взрываются оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Объяснение: 10 и -5 сталкиваются, в результате остаётся 10. 5 и 10 никогда не столкнутся.
Пример 2:
Input: asteroids = [8,-8]
Output: []
Объяснение: 8 и -8 сталкиваются, взрывая друг друга.
Пример 3:
Input: asteroids = [10,2,-5]
Output: [10]
Объяснение: 2 и -5 сталкиваются, в результате остаётся -5. 10 и -5 сталкиваются, остаётся 10.
Пример 4:
Input: asteroids = [3,5,-6,2,-1,4]
Output: [-6,2,4]
Объяснение: Астероид -6 взрывает астероиды 5 и 3, затем продолжает двигаться влево. С другой стороны, астероид 2 взрывает астероид -1 и продолжает двигаться вправо, не сталкиваясь с астероидом 4.
Ограничения:
2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
- Используем стек для хранения астероидов, которые ещё не столкнулись или пережили столкновение. Стек удобен тем, что позволяет проверять верхний астероид (последний добавленный) на столкновение с левым. Верхний - ближайший справа к левому, при его взрыве левый продолжит движение и проверит следующий (добавленный раньше) астероид в стеке, который автоматически станет новым ближайшим.
- Симулируем движение:
В цикле while (while позволяет проверять левый астероид на столкновение с несколькими правыми подряд) имитируем столкновение: стек должен быть не пуст, текущий астероид должен лететь влево, а верхний астероид в стеке - лететь вправо:
Чтобы определить, какой взорвётся, высчитываем разницу между их размерами посредством суммирования. Так как мы зашли в цикл while, текущий a всегда отрицательный, а stack[-1] - положительный, знак diff покажет, какой астероид больше:
- если diff отрицательный - левый больше => правый взрывается => удаляем его из стека => левый остаётся и продолжает цикл while, проверяя следующий астероид в стеке;
- если diff положительный - правый больше => левый взрывается, правый остаётся в стеке => обнуляем значение левого, цикл while завершается, так как условие a < 0 больше не выполняется;
- если значение diff равно нулю - размеры равны => оба взрываются => обнуляем левый и удаляем правый из стека, цикл завершается.
- Если после столкновений текущий астероид не равен 0, значит, он выжил. Добавляем его в стек.
Сложность
O(n) - по памяти (в худшем случае храним в стеке все элементы массива)
Код
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and a < 0 < stack[-1]:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
a = 0
stack.pop()
if a:
stack.append(a)
return stack
@algoses
🔥4❤3
Задача с собеседования в eBay
Даны строка s и словарь из строк wordDict.
Верните true, если s можно разбить на последовательность из одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание: одно и то же слово в словаре может использоваться при разбиении многократно.
Пример 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Вернётся true, так как строку "leetcode" можно разбить как "leet code".
Пример 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Вернётся true, так как строку "applepenapple" можно разбить как "apple pen apple" (слово из словаря может использоваться повторно).
Пример 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Ограничения:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s и wordDict[i] состоят только из строчных английских букв.
Все строки в wordDict уникальные.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Задача помечена тегом "Dynamic Programming": есть оптимальная подструктура и перекрывающиеся подзадачи. Если знаем, что хвост строки после некоторой позиции можно разбить на слова из словаря, то, чтобы расширить это разбиение влево, достаточно найти слово, заканчивающееся на этой позиции. Один и тот же срез строки может проверяться несколько раз - кэшируя ответ для каждой позиции, избежим повторных вычислений.
Используем итеративный dp:
Превращаем список wordDict во множество wordSet для ускорения поиска за O(L), где L - длина слова.
Создаём таблицу, где dp[i] = True, если суффикс s[i:] можно разбить. Размер: (n+1), где n - длина s (+1, чтобы учесть позицию после последнего символа и убедиться, что строка разбита полностью). По умолчанию заполняем False, так как ещё ничего не нашли.
Базовый случай: dp[n] = True. Пустой остаток корректен, цепочка слов доходит до конца s.
Суть алгоритма: перебираем позиции в s, проверяя срезы на присутствие в wordSet и возможность их "стыковки" с уже разобранными срезами в правой части.
Заполняем таблицу:
i - позиция начала потенциального слова; идёт по s справа налево.
j - конец потенциального слова, которое начинается в i; идёт вправо от i.
s[i:j+1] - текущий проверяемый срез.
В начале внутреннего цикла: i = j, с каждой следующей итерацией j увеличивается на 1, а длина подстроки растёт, пока не достигнет maxLength (длина самого длинного слова в словаре) или конца строки.
За проверку валидности среза отвечают два условия:
if dp[j+1] - разбивается ли остаток строки справа от текущего среза. Движемся справа налево, поэтому это значение уже вычислено.
Это условие не позволяет попасть в тупик, если слово есть в словаре, но не стыкуется корректно с хвостом (например, в строке "catsandog" на какой-то итерации найдём срез "and", но он не будет стыковаться с остатком строки, так как в словаре нет слова "og");
if s[i:j+1] in wordSet - наличие слова в словаре.
Порядок условий важен за счёт оптимизации "коротким замыканием": если остаток строки справа не разбивается корректно - новый срез не создаётся, а хэш не вычисляется.
Если оба условия удовлетворяются: dp[i] = True, цикл прерывается, так как нам достаточно найти один подходящий путь.
Возвращаем dp[0] - ответ для всей строки s[0:].
Сложность
O(N * L^2 + M * L) - время:
M * L - создание wordSet;
N * L^2 - N итераций во внешнем цикле (N - длина s) и до L итераций (ограничен maxLength) во внутреннем цикле:
внутри: создание среза s[i:j+1] за O(L) и вычисление хэша для поиска в wordSet за O(L) => O(L^2).
O(N + M * L) - память (дп массив и хэш-множество M слов длиной до L)
Код
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict)
n = len(s)
maxLength = max(len(w) for w in wordDict)
dp = [False] * (n+1)
dp[n] = True
for i in range(n-1, -1, -1):
for j in range(i, min(i+maxLength, n)):
if dp[j+1] and s[i:j+1] in wordSet:
dp[i] = True
break
return dp[0]
@algoses
Даны строка s и словарь из строк wordDict.
Верните true, если s можно разбить на последовательность из одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание: одно и то же слово в словаре может использоваться при разбиении многократно.
Пример 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Вернётся true, так как строку "leetcode" можно разбить как "leet code".
Пример 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Вернётся true, так как строку "applepenapple" можно разбить как "apple pen apple" (слово из словаря может использоваться повторно).
Пример 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Ограничения:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s и wordDict[i] состоят только из строчных английских букв.
Все строки в wordDict уникальные.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем итеративный dp:
Превращаем список wordDict во множество wordSet для ускорения поиска за O(L), где L - длина слова.
Создаём таблицу, где dp[i] = True, если суффикс s[i:] можно разбить. Размер: (n+1), где n - длина s (+1, чтобы учесть позицию после последнего символа и убедиться, что строка разбита полностью). По умолчанию заполняем False, так как ещё ничего не нашли.
Базовый случай: dp[n] = True. Пустой остаток корректен, цепочка слов доходит до конца s.
Суть алгоритма: перебираем позиции в s, проверяя срезы на присутствие в wordSet и возможность их "стыковки" с уже разобранными срезами в правой части.
Заполняем таблицу:
i - позиция начала потенциального слова; идёт по s справа налево.
j - конец потенциального слова, которое начинается в i; идёт вправо от i.
s[i:j+1] - текущий проверяемый срез.
В начале внутреннего цикла: i = j, с каждой следующей итерацией j увеличивается на 1, а длина подстроки растёт, пока не достигнет maxLength (длина самого длинного слова в словаре) или конца строки.
За проверку валидности среза отвечают два условия:
if dp[j+1] - разбивается ли остаток строки справа от текущего среза. Движемся справа налево, поэтому это значение уже вычислено.
Это условие не позволяет попасть в тупик, если слово есть в словаре, но не стыкуется корректно с хвостом (например, в строке "catsandog" на какой-то итерации найдём срез "and", но он не будет стыковаться с остатком строки, так как в словаре нет слова "og");
if s[i:j+1] in wordSet - наличие слова в словаре.
Порядок условий важен за счёт оптимизации "коротким замыканием": если остаток строки справа не разбивается корректно - новый срез не создаётся, а хэш не вычисляется.
Если оба условия удовлетворяются: dp[i] = True, цикл прерывается, так как нам достаточно найти один подходящий путь.
Возвращаем dp[0] - ответ для всей строки s[0:].
Сложность
M * L - создание wordSet;
N * L^2 - N итераций во внешнем цикле (N - длина s) и до L итераций (ограничен maxLength) во внутреннем цикле:
внутри: создание среза s[i:j+1] за O(L) и вычисление хэша для поиска в wordSet за O(L) => O(L^2).
O(N + M * L) - память (дп массив и хэш-множество M слов длиной до L)
Код
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict)
n = len(s)
maxLength = max(len(w) for w in wordDict)
dp = [False] * (n+1)
dp[n] = True
for i in range(n-1, -1, -1):
for j in range(i, min(i+maxLength, n)):
if dp[j+1] and s[i:j+1] in wordSet:
dp[i] = True
break
return dp[0]
@algoses
❤3🔥2