Первый Алгоритм Для Изучения в 2024

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

00:00 Вступление
00:23 Условие
01:20 Решение перебором
03:59 Быстрое решение
06:37 Код

[sobirabdulxair]

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

[Eldertri]

Саша, привет!
Спасибо за интересное видео. Единственное, ты слегка меня запутал когда сказал, что "удаляем, пока в сете есть повторяющиеся символы" - по факту, в сете они не повторяются. Наверное, лучше было бы сказать что удаляем, пока не удалим ПОВТОРИВШИЙСЯ символ)

[mndevitmndevit]

Как же я долго ждал нового видео, спасибо тебе огромное! Вот бы они выходили чаще)

[MrKryuk]

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

[kirillschcerbinin]

spasibo, Sasha za detalniy razbor. Видосы становятся все лучше и лучше по качеству, харош

[cablook_egja]

простой перебор можно сократить и до n^2, если просто обновлять сет после первого цикла а is_acceptable = True оставить на своём месте. ну и третий цикл можно будет убрать. На лит коде даже заработало.
Для скользящего окна вот ещё альтернатива, с помощью словаря на python:
def longest_substr(s):
answer = 0
left = 0
hash_set = {}
for right in range(len(s)):
char = s[right]
if char in hash_set and hash_set[char] >= left:
left = hash_set[char] + 1
else:
answer = max(answer, right - left + 1)
hash_set[char] = right
return answer
Спасибо за видео

[kalts_daniil]

Я только что решал задачу: Longest Substring Without Repeating Characters, и вуаля, тут видео на sliding window подъехало 🔥 Спасибо!

[heybeachMIN]

Спасибо ОГРОМНОЕ за такой подробное объяснение, всё понятно теперь) Было бы круто увидеть подобное объяснение но про деревья))

[badishow]

На пробнике ЕГЭ подобная задача попадалась (24-е задание).
Решил очень похожим способом

Видео, как всегда, интересное. Благодарю за контент!

[kuroiumi]

Ура ура! С возвращением, Сань :)
Круто что ты стал записывать видео чаще))

[borys]

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

[joyniferzagher]

Это кстати носит более распространенное название -- "метод двух указателей"

[user-se]

Привет, хотел выразить тебе огромное спасибо. Посмле просмотра видео про гугл и инжерена. Мне вернулся дух программиста. Начал вести фриланс и параллельно изучаю собесы

[flake]

За Иннополис за заднем фоне превью лайк)

[suuron]

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

[panfilovandrey]

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

[Победа-шз]

Изначально пришёл 2 вариант на ум, до первого даже догадаться не смог.
По времени заняло минуты 2-3.

[АндрейАртамонов-ъщ]

Первый раз за 10 лет в айти нашел нормально объясняющего на русском человека. Мне это конечно не пригодится, но было интересно 👍

[pxtr]

Спасибо за видео! У меня появился вопрос касательно быстрого решения. В видео говорится, что скорость O(n), но ведь по сути мы используем два цикла, один из которых вложен. представим, что в функцию отдается строка из одинаковых символов и тогда во все итерации кроме первой будет падать во вложенный цикл. а на сколько я помню скорость считается исходя из худшего случая. Почему в этом случае скорость O(n)? буду очень благодарен за ответ!

[artemkashipov]

по моему алгоритм можно улучшить используя bitset для хранения мапы элементов и то сколько раз они встретились