9:28 "не понятно с сходу как ее решать" Это же вроде классический обход в глубину с закрашиванием вершин в черный и серый По сравнении с методом на видео, требует конечно больше памяти
@@AndyPronin лукинг форвард ту зис премьер! Пользуясь случаем, хотел бы уточнить, насколько глубоко надо копать джуну в плане асинхронки, конкурентности и многопоточности? Просто на словах рассказать о понятиях или показать, что умеешь в асинке кодить, например?
Классный видос! Слышу такой: "обратный связный список" - поставил видос на паузу, пошел и решил. "Матрица по спирали" - поставил видос на паузу, пошел и решил. Увидел список задач на вебинар - поставил видос на паузу, пошел и решил. Все, можно в Яндекс или Гугол собираться? :D А по задачам: 1. Первая задач - очень прикольная на самом деле. Суть в том, что второй указатель бежит в 2 раза быстрее. И он либо найдет None, либо по циклу вернется и совпадет с первым указательно. Однако, сдается мне, тут могут задать 2 вопроса: оценить сложность такого алгоритма и доказать, что второй указатель гарантировано совпадет с первым при любом N. А это уже тяжкая задача. 2. Блин, всегда решал такую задачу задачу - просто преобразовывая в строку и тд. И я всегда считал, что это просто О(n). А О(n * log(log(n))) там будет, я полагаю, из-за случаев, когда у нас будет больше одной итерации при такой сумме? Любопытно. Всегда думал над тем, что в такой задаче стоит поискать какой-то алгоритм за О(1), но чет никогда руки не доходили. Ну, человек, который не варится в математических кругах, ни за что не выведет % 9. Банально я - недоматематик - даже не подумал об этом и решал "влоб". Такие приколюхи нужно "знать". Хотя, может я и ошибаюсь, и нематематики спокойно такое выводят. :D Прикольно, кароче. 3. Задачу про get_min() из Стэка - это вообще топ идея. Я все ломал голову - как ее решить за О(1). Ибо после того, как будет методом pop() мы удалим минимум, то придется искать минимум за О(n). А вот использовать еще один стэк - это круто. Хотя я не думал, что это разрешено. :D 4. Задача на пересечение списков. Как по мне, его решение не совсем удачное, сложность получится О(n + m + n + m) или же О(2(n + m)). Да, 2 уйдет и асимптотика останется "хорошей", но по факту - можно и быстрее. К примеру, я тупо сохранял айдишники всех нод из первого списка, затем итерировался по второму и смотрел, есть ли такой айдишник в сохраненном. Это решение за О(n + m), однако у меня и память тратится О(n). А у него память, все же, О(1). В общем, извечный вопрос: память или скорость? :D А вот за рассказ про то, как проходят собесы и особенно про то, могут помочь на собесах - за это прям отдельное спасибо. P.S. За весь сегодняшний день все, что я сделал - посмотрел этот видос длиною в 47 минут. Все остальное время я потратил на задачи из видоса и еще на какие-то связанные с ними. Забавно получилось, конечно
можно без второго стэка просто в стэке хранить тьюпл (текущий элемент, текущий минимум) и текущий минимум подгружать итеративно на основе нового элемента и прошлого минимума
Последняя задача (Medium 334) осталась неразобранной, но её можно решить за O(N) времени и O(1) вспомогательной памяти, идя по массиву и на каждой итерации храня самое маленькое встреченное число, а так же наименьшее число (Х), которое на своей итерации оказалось больше самого маленького. Как только натыкаемся на a[i] > X, то сразу ответ true. Сие обобщается на 4 числа, 5, и т.д.
@@arthorias06 конечно. Когда придем к 5, наименьшее число из ранее пройденных будет 2, потому запомним Х=5. Придя к 8, выясняем что 8 > Х и возвращаем true
@@arthorias06 перезапишет. Но теперь это неважно. Нам не требуется, чтобы в искомой тройке чисел a[i] было самым маленьким числом в массиве. Важно что где-то перед числом Х (которое a[j]) есть число, которое меньше Х.
Странное ощущение парень оставил. То ли проблемы со софт скилами и поэтому плохо или вообще ничего не объясняет, то ли типичный дампер без понимания чего он делает.
По задаче, где остаток деления на 9, непонятно, почему он говорит про сложность N log N ? Если за N брать количество разрядов в числе, то количество операций сложения почти всегда будет равно ему. Допустим для 999 будет 9+9+9 (две операции), а потом 2+7 - третья, и т.д. Вроде голимый О(N) выходит?
Про два стека тоже не до конца вкурил - если там речь просто про минимальное число. так почему его нельзя хранить в обычной переменной? Зачем заводить второй стек?
Допустим, стек имеет вид (3,2,1), очевидно, что наименьшее равно 1, но если убрать его из стека, то будет уже 2. Такое отследить с помощью переменной не получится, нужен дополнительный стек, который хранит минимальное на каждом уровне
видно что математик но не программист. ему надо на олимпиады, там его ниша. для программиста придется сломать все привычки и учиться писать код по другому. я про это очень часто слышал но ни разу не видел на примере. теперь увидел, прикольно, реально они пишут вообще не так.🤣это не значит что он пишет плохо! просто он пишет как пишут на олимпиадах по программированию. для программирования в компании, это плохо! для участия в олимпиадах, он крут. у каждого есть свое задачи и предназначения. то есть ему надо переучиваться стилю написания чтоб быть сильно востребованным в компаниях. и по софтам слабоват, объясняет очень плохо опять же как на олимпиаде. опять же это хорошо если ты участник олимпиад, и плохо если кодер в офисе.😁
Вторую с делением на 9 догадаться невозможно, надо знать. Задача на знание этой херни. Это знание никак с разработкой не связано, даже на пытайтесь доказать обратное. Задача - говно
Я так же подумал вначале. Не смотрел пока не решил часов 5, наверное. Но допереть логичесски можно. Там если часы круглые представить, немного понятнее становится. Иногда медиум задачи, проще чем изи.
@@AndyPronin спасибо за ответ! Может быть у вас будет совет, где помимо литкод можно данную практику получить? Может быть литература какая нибудь, или обучающий ресурс 🙂
@@IT_psychopathтак исправь их. Сам алгоритм по коду можно понять и не важно что за код там, ассемблер или ещё какой другой. На свой любимый язык можно легко его переписать
Божечки, спасибо вам большое за такой ценный контент!
Не переключайтесь. Скоро будет ещё интересней.) Буду благодарен за репосты в ваших соцсетях
Спасибо за полезное видео. Очень интересно
выкладывайте в 1080 плиз, 720 маловато
9:28 "не понятно с сходу как ее решать"
Это же вроде классический обход в глубину с закрашиванием вершин в черный и серый
По сравнении с методом на видео, требует конечно больше памяти
Рубрика с Русланом - отдельный лайк!
скоро еще запишем. Он вернулся в РФ
@@AndyPronin лукинг форвард ту зис премьер! Пользуясь случаем, хотел бы уточнить, насколько глубоко надо копать джуну в плане асинхронки, конкурентности и многопоточности? Просто на словах рассказать о понятиях или показать, что умеешь в асинке кодить, например?
Классный видос!
Слышу такой: "обратный связный список" - поставил видос на паузу, пошел и решил.
"Матрица по спирали" - поставил видос на паузу, пошел и решил.
Увидел список задач на вебинар - поставил видос на паузу, пошел и решил.
Все, можно в Яндекс или Гугол собираться? :D
А по задачам:
1. Первая задач - очень прикольная на самом деле. Суть в том, что второй указатель бежит в 2 раза быстрее. И он либо найдет None, либо по циклу вернется и совпадет с первым указательно. Однако, сдается мне, тут могут задать 2 вопроса: оценить сложность такого алгоритма и доказать, что второй указатель гарантировано совпадет с первым при любом N. А это уже тяжкая задача.
2. Блин, всегда решал такую задачу задачу - просто преобразовывая в строку и тд. И я всегда считал, что это просто О(n). А О(n * log(log(n))) там будет, я полагаю, из-за случаев, когда у нас будет больше одной итерации при такой сумме? Любопытно.
Всегда думал над тем, что в такой задаче стоит поискать какой-то алгоритм за О(1), но чет никогда руки не доходили. Ну, человек, который не варится в математических кругах, ни за что не выведет % 9. Банально я - недоматематик - даже не подумал об этом и решал "влоб". Такие приколюхи нужно "знать".
Хотя, может я и ошибаюсь, и нематематики спокойно такое выводят. :D
Прикольно, кароче.
3. Задачу про get_min() из Стэка - это вообще топ идея. Я все ломал голову - как ее решить за О(1). Ибо после того, как будет методом pop() мы удалим минимум, то придется искать минимум за О(n). А вот использовать еще один стэк - это круто. Хотя я не думал, что это разрешено. :D
4. Задача на пересечение списков. Как по мне, его решение не совсем удачное, сложность получится О(n + m + n + m) или же О(2(n + m)). Да, 2 уйдет и асимптотика останется "хорошей", но по факту - можно и быстрее. К примеру, я тупо сохранял айдишники всех нод из первого списка, затем итерировался по второму и смотрел, есть ли такой айдишник в сохраненном. Это решение за О(n + m), однако у меня и память тратится О(n). А у него память, все же, О(1). В общем, извечный вопрос: память или скорость? :D
А вот за рассказ про то, как проходят собесы и особенно про то, могут помочь на собесах - за это прям отдельное спасибо.
P.S. За весь сегодняшний день все, что я сделал - посмотрел этот видос длиною в 47 минут. Все остальное время я потратил на задачи из видоса и еще на какие-то связанные с ними. Забавно получилось, конечно
Не забываем оплачивать лайками и репостами
@@AndyPronin, ну, лайки ставлю, комменты оставляю, а вот репостов не будет - увы, я не любитель этой штуки.
1. по этой задаче правда не понятна ни сложность ни то что алгоритм реально рабочий
3. А зачем второй стек если можно просто переменную?
можно без второго стэка просто в стэке хранить тьюпл (текущий элемент, текущий минимум)
и текущий минимум подгружать итеративно на основе нового элемента и прошлого минимума
Спасибо, очень интересно
Спасибо, было полезно!
крутое видео
Последняя задача (Medium 334) осталась неразобранной, но её можно решить за O(N) времени и O(1) вспомогательной памяти, идя по массиву и на каждой итерации храня самое маленькое встреченное число, а так же наименьшее число (Х), которое на своей итерации оказалось больше самого маленького. Как только натыкаемся на a[i] > X, то сразу ответ true.
Сие обобщается на 4 числа, 5, и т.д.
@@alexandroppolus сработает для [2, 5, 1, 8] ?
@@arthorias06 конечно. Когда придем к 5, наименьшее число из ранее пройденных будет 2, потому запомним Х=5. Придя к 8, выясняем что 8 > Х и возвращаем true
@@alexandroppolus если мы на каждой итерации храним самое маленькое встречное число, как вы предлагаете, то не перезапишет ли 1 наше наименьшее?
@@arthorias06 перезапишет. Но теперь это неважно. Нам не требуется, чтобы в искомой тройке чисел a[i] было самым маленьким числом в массиве. Важно что где-то перед числом Х (которое a[j]) есть число, которое меньше Х.
@@alexandroppolus Я кажется понял идею, спасибо за объяснение)
Очень хочу устроиться в яндекс. И Я СЕЙЧАС НЕ ПРО ЯНДЕКС ЕДУ И НЕ ПРО ЯНДЕКС ТАКСИ, а программистом
посл задача крутая, смотрел разбор у индусов
супер)
Странное ощущение парень оставил. То ли проблемы со софт скилами и поэтому плохо или вообще ничего не объясняет, то ли типичный дампер без понимания чего он делает.
Если он принимал участие в международной олимпиаде по математике, то он все понимает х 10
Супер, ничего не видно:)
Не очень хорошо видно. И хорошо бы увеличить.
Решение с возвратом минимума в стеке не будет работать, если в стек будет помещëн и потом удалëн ещё один элемент, равный текущему минимуму.
почемуто про графы никто не знает что такое число эйлера, по которому можно узнать циклы
По задаче, где остаток деления на 9, непонятно, почему он говорит про сложность N log N ? Если за N брать количество разрядов в числе, то количество операций сложения почти всегда будет равно ему. Допустим для 999 будет 9+9+9 (две операции), а потом 2+7 - третья, и т.д. Вроде голимый О(N) выходит?
а в чем решение у него заключается? судя по коду это остаток от деления на 9, но это ведь неверно
Про два стека тоже не до конца вкурил - если там речь просто про минимальное число. так почему его нельзя хранить в обычной переменной? Зачем заводить второй стек?
Допустим, стек имеет вид (3,2,1), очевидно, что наименьшее равно 1, но если убрать его из стека, то будет уже 2. Такое отследить с помощью переменной не получится, нужен дополнительный стек, который хранит минимальное на каждом уровне
Это случайно не тот легендарный студент практикума который все спринты кроме алгоритмов проходил за 1 день? 😄
думаю нет) 11 когорта. он еще не все спринты загрокал
видно что математик но не программист. ему надо на олимпиады, там его ниша. для программиста придется сломать все привычки и учиться писать код по другому. я про это очень часто слышал но ни разу не видел на примере. теперь увидел, прикольно, реально они пишут вообще не так.🤣это не значит что он пишет плохо! просто он пишет как пишут на олимпиадах по программированию. для программирования в компании, это плохо! для участия в олимпиадах, он крут. у каждого есть свое задачи и предназначения. то есть ему надо переучиваться стилю написания чтоб быть сильно востребованным в компаниях. и по софтам слабоват, объясняет очень плохо опять же как на олимпиаде. опять же это хорошо если ты участник олимпиад, и плохо если кодер в офисе.😁
Итого он поработал и Яндексе и в Мета. Мож, не так и плохо всё
вообще не понятно чем конкретно он плох. что не так?
проще олимпиадника научить писать нормальный код, чем гуманитария алгоритм придумать)))
Че не так с кодом? Все же нормально
Вторую с делением на 9 догадаться невозможно, надо знать. Задача на знание этой херни. Это знание никак с разработкой не связано, даже на пытайтесь доказать обратное. Задача - говно
так и есть и математика тут особо не причем
Я так же подумал вначале. Не смотрел пока не решил часов 5, наверное. Но допереть логичесски можно. Там если часы круглые представить, немного понятнее становится.
Иногда медиум задачи, проще чем изи.
Простите, меня чет порвало, это че каждый таксист в яндексе шарит в алгосы?
Они таксерят для души. То всём известно
Я учусь сам около 3 месяцев, что то пока алгоритмы никак.... Это норма? Или я совсем глупый? Просто дальше разбираться?
Норма. Что бы вкатиться в алгоритмы нужно много практики. За 3 месяца врятли
@@AndyPronin спасибо за ответ! Может быть у вас будет совет, где помимо литкод можно данную практику получить? Может быть литература какая нибудь, или обучающий ресурс 🙂
@@tenelokis грокаем алгоритмы. Но там не про код, а про понимание логики
@@AndyPronin там еще есть ошибки и можно хорошо по тренироваться не понимая - "я скопировал а оно не работает.. почему?".🤣
@@IT_psychopathтак исправь их. Сам алгоритм по коду можно понять и не важно что за код там, ассемблер или ещё какой другой. На свой любимый язык можно легко его переписать
чувака с мфти, который на межнаре на олимпиаде по МАТЕМАТИКЕ побывал на стажера берут, что вы там хотите мля?)
не ной
@@АльбусДамблодр так я не ною, я рофлю с наивных хомячков, которым бин поиск сложна
учил пузырек бедный( зачем скуфы с гаражей перебрались на ютуб, еще и в it