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

Создал Telegram канал, в котором рассказываю о работе в Google, подготовке к собеседованиям и жизни в Лондоне. Подписывайтесь: t.me/saschalukin

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

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

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

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

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

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

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

На пробнике ЕГЭ подобная задача попадалась (24-е задание). Решил очень похожим способом Видео, как всегда, интересное. Благодарю за контент!

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

Было интересно изучить. Главное с апреля начать

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

Привет, пожалуста продолжай, очень полезно и информативно, сейчас активно пытаюсь прокачать алгоритмы и твои видосы прям то-что нужно!!!

Спасибо за классное объяснение, а то я когда на литкоде пыхтел над этими задачами с окном, чуть мозг не сломал, разбирая этот алгоритм

Спасибо, отличная подача. Без воды и смс. Успехов.

простой перебор можно сократить и до 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 Спасибо за видео

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

spasibo, Sasha za detalniy razbor.

Крутецки всё объяснил! Спасибо!

Отличное видео! Спасибо! Делай, пожалуйста, побольше такого контента на виды алгоритмов. И да, мы скучаем по Java)

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

Приятно осознавать, что я бы решил подобным образом.

Спасибо! Эффективность ваших видео O(n)!

Отличное видео! Спасибо!

Очень крутое объяснение, спасибо!

Буду благодарен, если сделаете ролик с roadmap по алгоритмам и то какие задачи решать

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

Спасибо за видео, всё понятно

Круто! Давно искал подобный канал с разборами задач, спасибо!

Подумав, решил методом похожим на скользящее окно, правда вместо указателей я бы воспользовался List(C#, System.Collections.Generic), но не уверен, что List подойдёт по оптимизации лучше и сопоставимо, чем указатели. Спасибо за видео.

Очень крутое видео, спасибо!

Хотелось бы больше примеров на Java ) спасибо 😊

Спасибо за видео! Какие еще задачи можно решать методом скользящего окна?

Я конечно дико извиняюсь, но это круто и изящно! Придумал на лету тоже вариант O(n), но он немного сложнее и кушает больше памяти - на каждый индекс массива создавать отдельный сет и добавлять в него пока "дубль" символа не встретится. Метод скользящего окна намного красивее!

Было бы интересно послушать про работу различных структур данных

Спасибо за видео! Сам около года назад сидел плотно в литкоде, задачи на скользящее окно были одними из любимых) Увидел условие, решил проверить сам себя, решу ли ее сейчас. Минут за 5 решил, не с первого раза, сначала подзабыл немного последовательность действий, пошел по неправильному пути. Оставлю тут свое решение (на js правда), оно немного отличается от решения в видео (вместо двух while у меня for и внутри него while, ну и без if/else, более линейно) function maxLen(str) { let maxLen = 0 let left = 0 const uniques = new Set() for (let right = 0; right < str.length; right++) { const current = str[right] while(uniques.has(current)) { uniques.delete(str[left]) left++ } uniques.add(current) maxLen = Math.max(maxLen, right - left + 1) } return maxLen } console.log(maxLen('axbxcxd')) // 3

Крутое видео! А если не секрет - то чем занимаешься в гугле? Что за стек?

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

Это отличное объяснение, я серьёзно

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

Без лишних слов, Превосходный контент и знания! СПАСИБО!!!! Вопрос: Английский вариант названия алгоритма "метод скользящего окна" ? The Sliding window ?

Спасибо за видео. Какой инструмент используется для демонстрации ? Очень удобно отображать скрытый код при нажатии. Сам часто делаю тех презентации и такой инструмент очень бы сильно помог, а то ливкодинг глючит )))

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

Отличное видео, спасибо

Спасибо за видео! А что это за софт со спойлерами и где можно рисовать?

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

спасибо интересный алгоритм!

Спасибо за видео! Можете пожалуйста посоветовать с чего начать изучение алгоритмов, если только только изучил основы python?

Клевый способ. А можно подгонкой размеров окна подобным способом находить всякие локальные максимумы, точки перегиба и прочее на каком ть временном ряде? По скольку они там формируются в вообще произвольной периодичностью.. ))) Было бы как раз...

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

реализация "простого" решения убила... я даже и не подумал что так можно XD

Спасибо за видео! Немного запутанное объяснение либо такое ощущение, что какие-то кадры ошибочно вырезаны с видео. Либо плохо разобрался)

Прикольно. Лайк. Я только погружаюсь в программирование. Будет ли полезно в первом цикле (где увеличиваем подстроку) не прогонять её по минимальным значениям а сразу увеличить на Макс. Длинну, уже записанную в сет? Так мы пропустим (в данном примере) проверку сетов cb и db.

Кайф! Спасибо!

3:30 можно обойтись без флага используя такой синтаксис: for bla bla bla: print('Стоп') break else: print('Цикл завершен без остановки')

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

спасибо за видео

Я бы построчным вводом добавлял , сортировал массив и сравнивал первую и вторую позиции и как только они равны записал бы размер массива-1, а потом начинал бы со второго символа.

Привет! Было бы круто, если бы разобрал задачу Medium from two sorted arrays. Нигде не могу найти хорошого объяснения

О да, это очень классный алгоритм. Его еще называют методом двух указателей. Все, кто к ЕГЭ по информатике готовится, учат его, довольно эффективный и гибкий алгоритм

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

Нормально, 24 задание ЕГЭ, поехали

Классное видео! А какой шрифт используется для кода?

Неплохое решение, но вот другое - за один проход, запоминая последний индекс символа. Swift: func lengthOfLongestSubstring(_ s: String) -> Int { var map: [Character: Int] = [:] var result = 0 var left = 0 for (i, c) in s.enumerated() { if let j = map[c] { left = max(left, j + 1) } result = max(result, i - left + 1) map[c] = i } return result }

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

Интересно, конечно :)

Цифры Пифагора. Если у треугольника длины сторон 3, 4 и 5 метров, то он -- прямоугольный. Или 6, 8 и 10 метров. И т. д. Эти волшебные цифры позволяют на местности рисовать прямые углы. Размечать местность под фундамент, например.

А проверка того что буква уже в сете за проверку не считается и проходит мгновенно?

Я думал что stack использовать нужно. 👍

Этот алгоритм напомнил мне метод указателей можно ли в данном случае его использовать?

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

что-то я не понял, на 5:13 мы проверяем и удаляем символы, на которые указывает left, но в алгоритме на java на 7:53 мы проверяем в while символ, на который указывает right, а не left. почему так? объясните, пожалуйста

Неплохое объяснение, но не оценивается вставка и поиск в Set, интервьювер разве не укажет на этот момент?

Вы могли записать видео про метод двух указателей?

Операции над set'ом же за ln(n) выполняются. Поэтому сложность с sliding window O(n*ln(n)), а без O(n^3 * ln(n))

Cпасибо большое, но в медленном алгоритме благодаря break внутренний цикл выполняется не более 26 раз, поэтому решение всё-таки за квадрат.

🔥

Насколько я понимаю, удаление с начала масива очень долгое, потому что нужно создать другой масив и перекопировать все значения в него. Поэтому, когда у нас будет очень длинная подстрока, придётся много раз пересоздавать масив внутри сета. Лучше уж после каждой итерации поставить проверку (result < right - left + 1). Но может сет в Java работает не так как я думаю, надеюсь на отзыв.

не понял на 5:16 говорится "удаляем пока в подстроке нету повторяющихся символов", хотя указатель на left - С и в подстроке остается С, тоесть они указывают на одинаковый символ , почему его он не удаляется как все предыдущие?

Хочу поделиться своим решением, на момент ответа видео не досмотрел. Сравниваем элементы с помощью бинарного дерева. В цикле начинаем сравнивать , если элемент меньше идём в лево, если равно continue. Если след узел null то тогда записываем в дерево элемент и увеличиваем count ++. После цикла выводим count. У нас получится уникальное бинарное дерево, с счётчиком count.

Как насчёт хэш-сета + рекурсия или это тоже будет давать O(n^2) или O(n^3)?

Интересно, что этот алгоритм начали спрашивать сейчас. Решал его еще года 3-4 на леткоде тогда он мне попался где-то 5 по счету. То что додумался до решения сам конечно тешет мое самолюбие. Но вот то что часа полтора два у меня ушло чтобы выдать рабочий код на go нет).

О а не подскажите через что вы делаете скрытие контента а потом его появление, по клику ?

как все красиво и понятно, спасибо, Александр! Кстати, а где рисуется такая "интерактивная" анимация?

Заметил Университет Иннополис на превью) Это просто случайность или ты как-то с ним связан?) я там первачок если что)

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

Сначала, решил, потом глянул первое "решение перебором". Какое же оно сложное... Чёт мне кажется что до такого тяжёлого и медленного решения просто никто специально не дойдёт и использовать не будет) Гораздо же легче и понятнее добавлять в новый список по букве если она не встречается в списке, иначе срезать часть списка по символ который снова встретился(включительно), и сохранять дубликат самого длинного списка. "Правильного решения" ещё не смарел

Мне кажется что первый алгоритм выполняет не n в кубе операций , а (n+n*n) /2 так как right пробегает от i до n символа, где i - положение left; у второго алгоритма максимальная скорость O(n) , а минимальная O(n*n) потому что right точно пробежит один раз строку, а left может остаться в начале (если все символы разные) или пробежать все символы (если все символы одинаковы) P. S. Укажите если не прав

Мне еще в голову пришло решение за O(nlogn) с помощью метода фиксированного скользящего окна и бинарного поиска)

А если в начале строки будет самая длинная строка, а потом она измениться, то что тогда?

остановил на 2:07 и мне показалось что первое очевидное решение на самом деле сложное и неочевдиным, очевидным решением для меня пробежаться по всем символам с хэшсетом накапливая его и фиксируя максимальный результат при наличии символа уже в нём, при этом сбрасывая его и возвращаясь назад на величину r-1, сча посмотри какое решение предложит автор

Ребят решил вот таким способом, что думаете ? Про память да, переборщил наверное: int testAlg(String value) { int maxLength = 0; Map map = {}; for (int i = 0; i < value.length; i++) { map[value[i]] = value[i]; for (int j = i + 1; j < value.length; j++) { if (map.containsKey(value[j])) { maxLength = maxLength >= map.length ? maxLength : map.length; map.clear(); break; } else { map[value[j]] = value[j]; } } } return maxLength; } PS: мог бы использовать Set вместо Map

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

Элегантное решение на Python, max_length = 0 left = 0 seen = {} for right, char in enumerate(s): if char in seen: left = max(left, seen[char] + 1) seen[char] = right max_length = max(max_length, right - left + 1) return max_length

а можно вместо set завести массив длинной в алфавит и держать в нем последний индекс, содержащий данную букву. Двигаем правый указатель, смотрим, была ли текущая буква в окне, если нет - запоминаем, идем дальше. Если буква была - стоп, проверяем, не больше ли текущее окно лучшего, если нашли лучшее - запоминаем окно и переставляем левый указатель сразу после буквы, которая повторилась. по сути - то же, но не надо двигать левый указатель по одному шагу, ну и обратиться к массиву - быстрее, чем добавлять-убирать из сета.

красавчик

Я сразу додумался до решения

Это Иннополис на фоне на превью?)

Поставил на паузу и попробовал такое решение со скоростью алгоритма O(n): def get_the_longest_substring(string): length = 0 left = 0 seen = {} for i in range(len(string)): char = string[i] if char in seen and seen[char] >= left: diff = i - left left = seen[char] + 1 if diff > length: length = diff seen[char] = i if left == 0: return len(string) return length

А при помощи чего ты делаешь такие презентации? Ну когда кликаешь мышкой на квадрат и там открываются значения.