@@victorprohorov6201 рекурсивно, начиная с корня, до всех листов. Стрелки только немного сбивают - реально граф неориентированный, раз путь может идти от левого поддерева через вершину в правое поддерево.
Александр, Спасибо! . У тебя талант объяснять сложные вещи, не останавливайся! Не оторваться - очень понятно и легко усваивается. Затягивает - утром вместо того, чтобы кофе налить - пошел смотреть другие ролики.
После обнаружения таких замечательных пояснений, начинаешь очаровываться алгоритмами! Спасибо за вашу работу. Нереально приятно изучать тему, с таким обучающим контентом❤
POV устраиваешься в среднестатистический проект: просят на собеседовании решить задачу на алгоритмы и математические знания а после офера отправляют таски по верстке 🤯
Перешёл по рекам ютюба, подготовился, чаёк заварил. Накануне изучал видео о парадоксах математики и нобелевских лауреатах, доказавших ту или иную теорему. Так сказать был готов к удивляться, и что в итоге??? Теперь я понимаю из за каих специалистов у меня винда лагает)
Объяснение просто огонь. Сейчас как раз прохожу тему алгоритмов и структур данных, а ютуб подсунул видео. Несложные алгоритмы и сам нормально решаю, а вот структуры данных начали вызывать какой-то необъяснимый страх. Не думал, что весь алгоритм настолько прост. Спасибо!
Спасибо за видео. В случае с деревьями желательно еще уметь решать dfs, bfs итерационно, а не только с помощью рекурсии. Если дерево будет выражено в список, то рекурсия уже не очень хороший вариант решения. Ну и не редко на собесах просят решить итерационно после решения с рекурсией
Дружище, спасибо тебе большое, пока твой разбор лучшее, что я видел в Ютубе для начинающих, разборы очень качественные, может сделаешь чек лист для джунов, что учить и как, спасибо!
Привет! Саш, спасибо за разборы. У тебя очень хорошо получается. Рассказываешь сложные вещи доступным языком. Во второй задачке ошибка при инициализации поля answer. Изначально оно должно быть минус бесконечность. Так как если подать на вход функции дерево с одной вершиной, значение которой равно отрицательному числу. В версии на видео в качестве ответа мы получим 0, а не отрицательное число ps. Может быть кто-то уже писал об ошибке, но я не нашел в комментах
И не только инициализация, там вообще с нулем нельзя сравнивать. Надо с минимально отрицательным. С чего автор решил, что понятие максимум это только для положительных чисел. А если там во всех узлах отрицательные value? Уже не будет правильного ответа? Ну а по сути, логика в целом верная. А рекурсия - это все равно зло :)
лучшие разборы задач. у меня с литкодом разговор короткий, я его решать не умею, но приходится. а эти разборы вносят хоть какую-то светлую мысль в беспросветное.
@@ilya9261 задачи по дп слишком разные. книги раскрывают или совсем базовые задачи, которые не попадутся на собеседовании, или книги написаны исключительно для олимпиадников. потому что как раз из олимпиад эти задачи и вышли. я решил 60(возможно не показатель) задач по дп на литкоде. с барского плеча 10 максимум повторились. но в основном это довольно уникальные задачи, которые чаще всего решаются как по учебнику(рекурсия с мемоизацией, bottom up и может оптимизированное решение) но дойти к рекуррентому соотношению, я считаю, вообще не просто. ну или все вокруг меня слишком умные и им проще решать)
@@НикитаКривицкий-щ5ы а стоп, ну раз ты нарешал 60 задач по дп без подглядываний, то с чего бы ты тупил то на подобных задачах как в видео? она решается проще простого. Либо не интуитивно понимаешь свои же решения, либо хз в чем проблема. 60 не показатель, но уже что-то, не 0 (у меня сейчас меньше и я трудоустроен), продолжай в том же духе)
@@НикитаКривицкий-щ5ы > но дойти к рекуррентому соотношению, я считаю, вообще не просто. ну или все вокруг меня слишком умные и им проще решать) Это фигня и в жизни редко пригождается, поэтому примеры довольно вымученные. Я программирую 22 года, 10 в качестве хобби и 12 профессионально. Подобные задачи пригодились 3 раза - 2 в качестве хобби (игровой проект) и 1 на работе - тоже игровой, совершенно не типичный проект. Мой совет - требуют leetcode? пожелайте счастливого пути и ищите руководителя, который понимает, какие задачи Вы будете писать на работе. Если Вы не пишете AI для игр, то с подобными задачи будете иметь дело раз в пятилетку. Сядете, спокойно продумаете алгоритм (да, вместо 20 минут возможно целый день потратите) - но я Вас уверяю, отлаживать алгоритм и писать подходящие структуры для быстрой его работы (чтобы оно занимало вменяемое время и при этом можно было сохранить вне 1 Гигабайта) - Вы будете писать гораздо дольше.
Есть у меня смутное предположение что если все значения в дереве будут отрицательными, то maxpathsum выдаст 0, а не мах отрицательный ответ, для этого наверное answer должен быть равен по умолчанию значению самой верхней вершины.
0 означает, что мы не берем левого\правого ребенка. Но после этого ответ для нашей вершины становится max(left, right) + val. Так что ошибки нет, и ответ может быть отрицательным, если положительных вершин вовсе нет
@@Богдан-з5з7пэто возвращает функция helper, параллельно она записывает в переменную класса answer (максимум среди answer=0 и тем что вернул helper на данном шаге) А далее цель maxpathsum просто вывести эту переменную, соответственно если все отрицательно то answer так и останется 0. Выше написали что это вроде как правильно если ничего не брать, но в таких случаях наверное лучше уточнять данный кейс.
Вторая задача - все же answer = Integer.MIN_VALUE; Так как в случае с деревом состоящим всего из одного отрицательного желемента - ответ будет 0, а должен быть - само это отрицательное число.
Просто решение у автора некорректное. Либо задача поставлена криво. Автор декларирует "дальше не пойдём" но по факту это работает только если отрицательный узел один и сравнивается с мнимым узлом, чьё значение 0. Если у 5 будет не один ребёнок -2, а ещё один, скажем -5 - решение будет несоответствовать задаче.
@@tsv83 работать будет и с вашим примером, поскольку с нулём сравнивается и helper(node.left) и helper(node.right), который, в свою очередь содержит максимальную сумму дальнейшего пути, то есть, в момент сравнивания уже учитывается, есть ли там что-то дальше, как то с "-3", у которой ребёнок "5"
Классные задачи, спасибо автору. P. s. Не описать ту радость, когда сначала пытаешься решить задачу, а потом смотришь ролик, где твоё решение совпадает с решением автора. p.p.s Только сделать Answer и проверять на max в helper-e, я не догодался, а просто запихивал возможные пути в лист, а потом из него макс брал.
@@КириллЧе-я5ы да, так-то все понятно )) просто когда данные в стеке и тебе надо о них помнить это другое нежели тарелки представить )) это тарелки с данными ))
Ха-ха. Сегодня защищал лабораторную в универе, плохо сдал, а вот сейчас захожу в ютуб, чтобы найти, под какой видосик покушать, и вижу это! 🤩🤩🤩 Леди Фортуна, интернет и ютуб, спасибо вам! 😅
Спасибо за видео. Единственное, хотелось бы уточнить во второй задаче. Наверное в требования входило условие, что результат должен быть положительным. В противном случае мы не покрыл кейс когда все ноды содержат отрицательные значения. Наибольший среди отрицательных тоже можно найти
Я конечно может чего не понимаю, но разве отрицательные значения не меньше положительных ПО УМОЛЧАНИЮ. Если все вершины отр. то максимальное будет самое меньшее отрицательное.
Каждый раз, когда собираюсь менять компанию, готовлюсь к таким задачам как в первый раз, затем на несколько лет забываю, и далее по кругу. Может быть лет 20 назад эти ОСНОВЫ ИЗ ЧЕГО ВСЕ СТРОИТСЯ и нужны были кому-то, сейчас для большиства разработки это вообще мимо. Впервые я изучил это все для собеседования, наверное, после 2х лет работы программистом, и никакого всевидящего ока в мир разработки мне не открылось, прошел собес и забыл, как всегда. С тем пор я поменял 4 компании и 3 страны, и заметил что зачастую на собесах попадаются консерваторы, которые считают, раз им это интересно, и раз они это заботанили, все вокруг должны это знать, и не важно что для проекта это нафиг не нужно, как будто это какие-то невероятные знания, смешно) Знание архитектурного дизайна намного важнее как по мне, потому что ты приходишь в компанию, и твой онбординг сокращается в разы, потому что ты уже скорее всего понимаешь как работает система. А эти стуктуры, достаточно знать что это такое, что такое бывает, и какая структура для чего работает, и для этого не обязательно решать какие-то сложные задачи и разбираться в них до транзиторов. Первая задача еще адекватная, но вторая это по-моему уже перебор, я бы наверное и решать ее не стал, потому что мне это тупо не интересно)
Если занимаешься простейшим формашлёпством или CRUDошлёпством, где нет ни хайлоада ни интересных задач, то да, это не пригодится. Но как только захочешь отойти от чужих либ и написать своё (более подходящее и масштабируемое решение), то упрёшься в узкость своих знаний, да даже тупо не зная как работает структура данных не сможешь оценить и быть уверенным, что нагруженное место не взорвётся в рантайме.
@@MrOldschoolrocknroll оо подъехали спецы нефармашлепы! 1) Я написал "А эти стуктуры, достаточно знать что это такое, что такое бывает, и какая структура для чего работает, и для этого не обязательно решать какие-то сложные задачи и разбираться в них до транзиторов. ", с чего ты взял что я "даже тупо не знаю как работает структура данных" и призываю вообще на них забить? 2) Я написал это в контексте собеседований, что зачастую их спрашивают когда они на проекте вообще не нужны. Если ты курнул и решил "написать своё (более подходящее и масштабируемое решение)", то флаг тебе в руки, никто не скажет тебе что структуры и алгоритмы для них не нужны. 3) И если ты "не зная как работает структура данных не сможешь оценить и быть уверенным, что нагруженное место не взорвётся в рантайме", то у меня для тебя плохие новости.
@@HarryKastuchsky Как же у тебя бомбануло то господи. Я же не конкретно про тебя писал а об индустрии в целом. Но раз ты воспринял всё на свой счёт, то у тебя с этим похоже какие-то проблемы))
может тут и не в самой задаче дело? эти корпорации, они что-то про нас знают )) есть же реальные кейсы тестов на вакансии (не айти), где тебя не возьмут, если слишком хорошо выполнить )
спасибо за разбор. Помню как на собеседовании на Unity dev решал задачу через алгоритм Дэйкстры (вглубь и вширь), а оказывается есть более простой способ.
Я смотрел твои видео чуть больше года назад, получил оффер с релокацией в европу) Теперь смотрю твои видео перед собеседованием в яндекс, но в этот раз решил подписаться)
@@melheor4909 я если что не писал, что я только после его видосов получил оффер, я в процессе подготовки натыкался на его видео, и объяснения мне понравились, даже е смотря на то, что тогда я собесился на позицию мидла в ts, а теперь на позицию синьора в go)
Я что-то про путь «9-> -10 -> 20..» не дополнял. У нас же дерево, а не двунаправленный ориентированный граф. И все пути идут только от корня вниз.. к листьям Из определения же видно, что из узла нельзя попасть назад.. потому что туда нет ссылки. Нельзя вернуться..
напоминает обучение в автошколе - я купил тонюсенькую книжку с ПДД и учу правила, а остальные накупили разборы билетов и усиленно штудируют их. Но да - я потом сел и поехал на своем Заз-968М, а девочки расселись по новым Кайенам. Так что может вы и правы XD
Когда ты сказал, что нужно "найти путь", а потом продолжил говорить именно про сумму ветки, меня это смутило. Изначально из твоих слов верно было подумать, что требуется найти путь, то есть последовательность нод, список, так скажем, состоящих в ветке с наибольшей суммой. Как говорится, без внятного тз результат будет "хз" :)
Я как-то раз был на собеседовании Майкрософт) Тётенька такая вредная попалась. Села прямо передо мной и уставилась в мой лист что я пишу. Я тогда мало умел справляться с такими ситуациями, от напряжения все забыл 😂 Просто попрощался и ушел 😂 А когда только вышел из здания, решение мне в голову пришло 😂
@@sashalukin Я работаю как Android-разработчик (Java/Kotlin) и хочу изучать Golang для бэкенда. Но я не уверен, является ли это хорошим выбором. Что бы ты посоветовал? Я хочу работать в крупных компаниях и люблю решать алгоритмические задачи.
Конкретный язык программирования не имеет значения на собесах в американские айти компании. Надо уметь решать литкод (любой язык программирования на твой выбор) + System Design, если идешь на middle и выше (3+ года опыта работы). Поэтому я бы сфокусировался на этом. Ну и самое главное - начать как можно раньше и как можно чаще проходить собесы. Конкретно сейчас с этим проблема, но из тех что я знаю - booking и uber продолжают нанимать. Напиши 10-20 рекрутерам каждой компании в Linkedin что хочешь устроиться работать к ним, и попробуй получить инвайты на собесы.
Спасибо, просто и понятно. Только я не понял одно, почему во второй задаче мы не идем ниже по дереву если у ноды оба отрицательных ребенка? А если за одним из них стоит +40? Или это имелось в виду уже результат суммы всех детей ниже?
Слово лист прозвучало, но без определения) Ну и казалось бы очевидный факт «почему дерево», ведь графически мы рисуем скорее густые корни?) Ну просто наши деревья растут вниз)
Чудесная подача теории! И код на джаве действительно понятен, хоть я и по питону больше! У меня вопрос по первой задаче: почему при вычислении space comlexity худший вариан - это дерево, которое идет только на лево или только на право?
20:59 позволю себе ремарку: `answer = Math.max(answer, maxLeftPath + maxRightPath + node.val);` ☝тут в `answer` будет записан 0 если на входе корень без детей, но с отрицательным значением или если в дереве только отрицательные значения ; мне кажется, нужно перед вызовом `helper()` инициализировать `answer = root.val`
А почему суммируем корень + лево + право, когда по условиям второй задачи надо найти самое большое значение по пути, при этом по вершине можно пройти один раз?
Суммирование левого, правого и корня это есть сумма пути, если бы путь шёл от левого поддерева через корень в правое. Эта сумма идёт в ответ, но не в возвращаемое значение. То есть возвращаемое значение не включает эту сумму, поэтому изменение ноды -4 (например на 5) не поменяет значение, которое получает нода 20 (2), но если вместо 20 будет, скажем число -10, то в ответ пойдёт 5+(-3)+5 как лучшее из возможных
вы сказали, что сто если на пути будет отрицательное то можно не идти, а что если после отрицательног оузла будет идти дочернее со значением 100, то есть тогла нам стоит пойти вниз
В T-SQL такие штуки, как практические алгоритмы решения прикладных задач прохождения по Parent-Child иерархиям - реализуется при помощи рекурсивных CTE. Используется, например, для обработки и поддержания товарных справочников в ритейле. Ну а сама суть так же ложится в основу b-tree индексов, которые стараются на уровне их ядра поддерживать баланс «веса» значений детей
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Объяснение - просто 🔥. Это тот случай, когда у автора есть реальная способность доходчиво и лаконично объяснить алгоритмы и структуры данных
а я не особо понял. лучше было бы если бы автор показал как это работает на примере
@@victorprohorov6201 а чем этот пример, был не примером?
@@yaroslavandreyev4246 я не понял как мы переходим по вершинам.
@@victorprohorov6201 рекурсивно, начиная с корня, до всех листов. Стрелки только немного сбивают - реально граф неориентированный, раз путь может идти от левого поддерева через вершину в правое поддерево.
Александр, Спасибо! . У тебя талант объяснять сложные вещи, не останавливайся! Не оторваться - очень понятно и легко усваивается. Затягивает - утром вместо того, чтобы кофе налить - пошел смотреть другие ролики.
После обнаружения таких замечательных пояснений, начинаешь очаровываться алгоритмами! Спасибо за вашу работу. Нереально приятно изучать тему, с таким обучающим контентом❤
Я считаю, что это один из лучших каналов на ютубе по подготовке к алгоритмической секции!
Спасибо огромное!!!
POV устраиваешься в среднестатистический проект: просят на собеседовании решить задачу на алгоритмы и математические знания а после офера отправляют таски по верстке 🤯
Ну так радоваться надо) изи мани)))
Да, но это не плохо
Задачи могут быть разные, зависит от потребностей бизнеса))
Лишь бы платили как за алгиритмические задачи с вышматом под капотом =))
@@DevBer было б так, не было б пределу счастья :)
Саня, классный парень без понтов и умный. Так держать! Еще и спортивный.
Перешёл по рекам ютюба, подготовился, чаёк заварил. Накануне изучал видео о парадоксах математики и нобелевских лауреатах, доказавших ту или иную теорему. Так сказать был готов к удивляться, и что в итоге??? Теперь я понимаю из за каих специалистов у меня винда лагает)
Даже ударение в слове «красивее» стоит правильно. 👏🏻💐
Объяснение просто огонь. Сейчас как раз прохожу тему алгоритмов и структур данных, а ютуб подсунул видео. Несложные алгоритмы и сам нормально решаю, а вот структуры данных начали вызывать какой-то необъяснимый страх. Не думал, что весь алгоритм настолько прост. Спасибо!
Спасибо за видео. В случае с деревьями желательно еще уметь решать dfs, bfs итерационно, а не только с помощью рекурсии. Если дерево будет выражено в список, то рекурсия уже не очень хороший вариант решения. Ну и не редко на собесах просят решить итерационно после решения с рекурсией
Очень круто, спасибо. Давно хотел разобраться с деревьями
Отличный разбор и отличная подача! Ждем следующей задачи)
Спасибо!
Oh man, it's totally awesome! I checked out a ton of videos, and this one is pure magic. Everything is crystal clear! Thanks a million, bro!
шикарно, спасибо за разбор, с первой легко было, а вторая заставила подольше посидеть)
Дружище, спасибо тебе большое, пока твой разбор лучшее, что я видел в Ютубе для начинающих, разборы очень качественные, может сделаешь чек лист для джунов, что учить и как, спасибо!
Шикарная подача!
Всё доступно и понятно, особенно с учетом того, что я далек от программирования:)
Привет! Саш, спасибо за разборы. У тебя очень хорошо получается. Рассказываешь сложные вещи доступным языком.
Во второй задачке ошибка при инициализации поля answer. Изначально оно должно быть минус бесконечность. Так как если подать на вход функции дерево с одной вершиной, значение которой равно отрицательному числу. В версии на видео в качестве ответа мы получим 0, а не отрицательное число
ps. Может быть кто-то уже писал об ошибке, но я не нашел в комментах
И не только инициализация, там вообще с нулем нельзя сравнивать. Надо с минимально отрицательным. С чего автор решил, что понятие максимум это только для положительных чисел. А если там во всех узлах отрицательные value? Уже не будет правильного ответа? Ну а по сути, логика в целом верная. А рекурсия - это все равно зло :)
а кем работаешь? просто интересн окакая зарплата@@alexyevdokimov642
Ого, поначалу зафтыкал, думал че за сложное объяснение, а на деле несколько строк кода емае. Мужик! Спасибо!
Послушал с удовольствием. :)
Удачи!
Блестящий разбор! Ждём продолжения
Про Space: O(n) для первой задачи не сразу догадался. Видео хорошее.
Очень понравился формат. Сразу оформил подписку. Делай больше таких разборов, и добавляй их в отдельный плейлист на канале =)
Лучший! Приятно смотреть) Продолжай записывать видео и не забрасывай)
Хорошая подача и подробное объяснение. Буду заглядывать 😊
лучшие разборы задач. у меня с литкодом разговор короткий, я его решать не умею, но приходится. а эти разборы вносят хоть какую-то светлую мысль в беспросветное.
@@ilya9261 задачи по дп слишком разные. книги раскрывают или совсем базовые задачи, которые не попадутся на собеседовании, или книги написаны исключительно для олимпиадников. потому что как раз из олимпиад эти задачи и вышли. я решил 60(возможно не показатель) задач по дп на литкоде. с барского плеча 10 максимум повторились. но в основном это довольно уникальные задачи, которые чаще всего решаются как по учебнику(рекурсия с мемоизацией, bottom up и может оптимизированное решение) но дойти к рекуррентому соотношению, я считаю, вообще не просто. ну или все вокруг меня слишком умные и им проще решать)
@@НикитаКривицкий-щ5ы а стоп, ну раз ты нарешал 60 задач по дп без подглядываний, то с чего бы ты тупил то на подобных задачах как в видео? она решается проще простого. Либо не интуитивно понимаешь свои же решения, либо хз в чем проблема. 60 не показатель, но уже что-то, не 0 (у меня сейчас меньше и я трудоустроен), продолжай в том же духе)
@@ilya9261 я перечитал свой коммент и понял, что забыл написать, что я так и не научился решать дп задачи)
@@НикитаКривицкий-щ5ы дак ты же 60 штук решил. Как решал?
@@НикитаКривицкий-щ5ы
> но дойти к рекуррентому соотношению, я считаю, вообще не просто. ну или все вокруг меня слишком умные и им проще решать)
Это фигня и в жизни редко пригождается, поэтому примеры довольно вымученные.
Я программирую 22 года, 10 в качестве хобби и 12 профессионально. Подобные задачи пригодились 3 раза - 2 в качестве хобби (игровой проект) и 1 на работе - тоже игровой, совершенно не типичный проект.
Мой совет - требуют leetcode? пожелайте счастливого пути и ищите руководителя, который понимает, какие задачи Вы будете писать на работе. Если Вы не пишете AI для игр, то с подобными задачи будете иметь дело раз в пятилетку. Сядете, спокойно продумаете алгоритм (да, вместо 20 минут возможно целый день потратите) - но я Вас уверяю, отлаживать алгоритм и писать подходящие структуры для быстрой его работы (чтобы оно занимало вменяемое время и при этом можно было сохранить вне 1 Гигабайта) - Вы будете писать гораздо дольше.
Есть у меня смутное предположение что если все значения в дереве будут отрицательными, то maxpathsum выдаст 0, а не мах отрицательный ответ, для этого наверное answer должен быть равен по умолчанию значению самой верхней вершины.
Нет, по условию, мы имеем право взять 0 вершин, так что наш минимум - 0
Тож так думаю. Что если стоит отрицательное значение, а ниже много положительных
0 означает, что мы не берем левого\правого ребенка. Но после этого ответ для нашей вершины становится max(left, right) + val. Так что ошибки нет, и ответ может быть отрицательным, если положительных вершин вовсе нет
@@Богдан-з5з7пэто возвращает функция helper, параллельно она записывает в переменную класса answer (максимум среди answer=0 и тем что вернул helper на данном шаге)
А далее цель maxpathsum просто вывести эту переменную, соответственно если все отрицательно то answer так и останется 0.
Выше написали что это вроде как правильно если ничего не брать, но в таких случаях наверное лучше уточнять данный кейс.
@@gheoblink8862 разве условие задачи не найти максимальный путь? Если два значения отрицательны не значит что одно из них не может быть максимальным?
даже я понял после такого понятного объяснения! Супер!
Разбор задачи хорошо подан. Классный контент. Буду ждать еще разборы алгоритмов
Вторая задача - все же answer = Integer.MIN_VALUE; Так как в случае с деревом состоящим всего из одного отрицательного желемента - ответ будет 0, а должен быть - само это отрицательное число.
Правильное замечание, но этого не достаточно. В коде, там где max, тоже нужно логику поменять.
@@slavakonashkov нет, в остальном все правильно.
Просто решение у автора некорректное. Либо задача поставлена криво. Автор декларирует "дальше не пойдём" но по факту это работает только если отрицательный узел один и сравнивается с мнимым узлом, чьё значение 0. Если у 5 будет не один ребёнок -2, а ещё один, скажем -5 - решение будет несоответствовать задаче.
@@tsv83 работать будет и с вашим примером, поскольку с нулём сравнивается и helper(node.left) и helper(node.right), который, в свою очередь содержит максимальную сумму дальнейшего пути, то есть, в момент сравнивания уже учитывается, есть ли там что-то дальше, как то с "-3", у которой ребёнок "5"
@@МихаилПершин-х3и нет, не будет
Классные задачи, спасибо автору.
P. s. Не описать ту радость, когда сначала пытаешься решить задачу, а потом смотришь ролик, где твоё решение совпадает с решением автора.
p.p.s Только сделать Answer и проверять на max в helper-e, я не догодался, а просто запихивал возможные пути в лист, а потом из него макс брал.
Отличный разбор. Буду давать эту задачу на собеседованиях :)
Если хотите понять деревья, посмотрите это видео 👌 идеально, большое спасибо за столь подробное объяснение 🔥🔥🔥
Продолжай, брат )
У меня ничего не получается на литкоде ))
Хотя принцип обхода знаю, но сложно уложить стэк в голове ))
Стек на самом деле самая простая структура после массива… можно представить себе тарелку с блинами - ты ж с низу блин не вытащишь и вниз не положишь🥴
@@КириллЧе-я5ы да, так-то все понятно ))
просто когда данные в стеке и тебе надо о них помнить это другое нежели тарелки представить )) это тарелки с данными ))
Ха-ха. Сегодня защищал лабораторную в универе, плохо сдал, а вот сейчас захожу в ютуб, чтобы найти, под какой видосик покушать, и вижу это! 🤩🤩🤩
Леди Фортуна, интернет и ютуб, спасибо вам! 😅
Круто! Спс! С первого раза непонятно, пересмотрю на досуге еще несколько раз)
хоспади как комфортно и понятно, подписалась)
Приятно смотреть и слушать. Очень понятное и детальное объяснение. Большое спасибо!
7:17 Пустого дерева не бывает по определению: дерево это граф, а граф имеет хотя бы одну вершину.
Интересная задача. Объяснено довольно доходчиво! Спасибо
Когда сидел и не понимал, как решать, а потом сразу понял🙏🏾
Just do it!
Спасибо за видео.
Единственное, хотелось бы уточнить во второй задаче. Наверное в требования входило условие, что результат должен быть положительным.
В противном случае мы не покрыл кейс когда все ноды содержат отрицательные значения. Наибольший среди отрицательных тоже можно найти
Я конечно может чего не понимаю, но разве отрицательные значения не меньше положительных ПО УМОЛЧАНИЮ. Если все вершины отр. то максимальное будет самое меньшее отрицательное.
@@Jimoshi1 в этом то и прикол, что такое решение не рассмотрено
Каждый раз, когда собираюсь менять компанию, готовлюсь к таким задачам как в первый раз, затем на несколько лет забываю, и далее по кругу. Может быть лет 20 назад эти ОСНОВЫ ИЗ ЧЕГО ВСЕ СТРОИТСЯ и нужны были кому-то, сейчас для большиства разработки это вообще мимо. Впервые я изучил это все для собеседования, наверное, после 2х лет работы программистом, и никакого всевидящего ока в мир разработки мне не открылось, прошел собес и забыл, как всегда. С тем пор я поменял 4 компании и 3 страны, и заметил что зачастую на собесах попадаются консерваторы, которые считают, раз им это интересно, и раз они это заботанили, все вокруг должны это знать, и не важно что для проекта это нафиг не нужно, как будто это какие-то невероятные знания, смешно) Знание архитектурного дизайна намного важнее как по мне, потому что ты приходишь в компанию, и твой онбординг сокращается в разы, потому что ты уже скорее всего понимаешь как работает система. А эти стуктуры, достаточно знать что это такое, что такое бывает, и какая структура для чего работает, и для этого не обязательно решать какие-то сложные задачи и разбираться в них до транзиторов. Первая задача еще адекватная, но вторая это по-моему уже перебор, я бы наверное и решать ее не стал, потому что мне это тупо не интересно)
Если занимаешься простейшим формашлёпством или CRUDошлёпством, где нет ни хайлоада ни интересных задач, то да, это не пригодится. Но как только захочешь отойти от чужих либ и написать своё (более подходящее и масштабируемое решение), то упрёшься в узкость своих знаний, да даже тупо не зная как работает структура данных не сможешь оценить и быть уверенным, что нагруженное место не взорвётся в рантайме.
@@MrOldschoolrocknroll оо подъехали спецы нефармашлепы!
1) Я написал "А эти стуктуры, достаточно знать что это такое, что такое бывает, и какая структура для чего работает, и для этого не обязательно решать какие-то сложные задачи и разбираться в них до транзиторов. ", с чего ты взял что я "даже тупо не знаю как работает структура данных" и призываю вообще на них забить?
2) Я написал это в контексте собеседований, что зачастую их спрашивают когда они на проекте вообще не нужны. Если ты курнул и решил "написать своё (более подходящее и масштабируемое решение)", то флаг тебе в руки, никто не скажет тебе что структуры и алгоритмы для них не нужны.
3) И если ты "не зная как работает структура данных не сможешь оценить и быть уверенным, что нагруженное место не взорвётся в рантайме", то у меня для тебя плохие новости.
@@HarryKastuchsky Как же у тебя бомбануло то господи. Я же не конкретно про тебя писал а об индустрии в целом. Но раз ты воспринял всё на свой счёт, то у тебя с этим похоже какие-то проблемы))
может тут и не в самой задаче дело? эти корпорации, они что-то про нас знают )) есть же реальные кейсы тестов на вакансии (не айти), где тебя не возьмут, если слишком хорошо выполнить )
Топ, спасибо большое за такое объяснение, жду новых задач!
Ура! Ты вернулся! Спасибо тебе за разбор
спасибо за разбор. Помню как на собеседовании на Unity dev решал задачу через алгоритм Дэйкстры (вглубь и вширь), а оказывается есть более простой способ.
От души братишка, под пиво вечерком посмотреть самое оно!
Я смотрел твои видео чуть больше года назад, получил оффер с релокацией в европу)
Теперь смотрю твои видео перед собеседованием в яндекс, но в этот раз решил подписаться)
В Европе не сложилось?
@@Gr-wv9rb сложилось, просто яндекс предлагает больше денег, при этом ехать не далеко
Я после его видосов получил офферы на альфа центавру, а второй на Ксандар. Вот думаю куда лететь
@@melheor4909 я если что не писал, что я только после его видосов получил оффер, я в процессе подготовки натыкался на его видео, и объяснения мне понравились, даже е смотря на то, что тогда я собесился на позицию мидла в ts, а теперь на позицию синьора в go)
@@eugenefedoryachenko8793 да я понял))
Я что-то про путь «9-> -10 -> 20..» не дополнял. У нас же дерево, а не двунаправленный ориентированный граф. И все пути идут только от корня вниз.. к листьям
Из определения же видно, что из узла нельзя попасть назад.. потому что туда нет ссылки. Нельзя вернуться..
Спасибо за разбор. Хотелось бы почаще.
Одна из лучших подач материала!
ты классный парень, спасибо за такие ролики С:
Как раз вчера в университете начали проходить эти деревья)
Спасибо. Часть задач на бинарные деревья на лилкоде сделал, а часть отложил. Хотя для макс.пути понимал, что нужна рекурсия.
Дуже корисний канал. Дякую за Вашу роботу.
Спасибо! посмотрел несколько роликов - очень доходчиво
напоминает обучение в автошколе - я купил тонюсенькую книжку с ПДД и учу правила, а остальные накупили разборы билетов и усиленно штудируют их.
Но да - я потом сел и поехал на своем Заз-968М, а девочки расселись по новым Кайенам. Так что может вы и правы XD
Круто! Прям все по полочкам, реально класс! Спасибо👍🙏
Спасибо за разбор, деревья моя ахилесова пята
Спасибо за классные видео. Продолжай выпускать задачки по faang
17:28 разве у вершины 20 вычисленное значение не должно быть 30? Это ведь сумма max(0, левой дочки), max(0, правой дочки), и собственного значения
Отличное объяснение! Just keep going! )
Когда ты сказал, что нужно "найти путь", а потом продолжил говорить именно про сумму ветки, меня это смутило. Изначально из твоих слов верно было подумать, что требуется найти путь, то есть последовательность нод, список, так скажем, состоящих в ветке с наибольшей суммой. Как говорится, без внятного тз результат будет "хз" :)
Путь - это список нод (ну или список направлений). Так что задача не решена, автор собеседование не прошел :)
Думаю, что Вы хороший человек. Спасибо за видео
Классный канал, автор приятный парень и никакого высокомерия
Просто супер, все просто и понятно!
Да . столько раз ты это объяснял в элементарном введении в К.М. а они всё равно не понимают и спорят. Пасибо за ролик
17:22 это верно только для дерева без нод, если у нас есть хотя бы одна нода (-10) мы не можем её отбросить.
Я как-то раз был на собеседовании Майкрософт)
Тётенька такая вредная попалась. Села прямо передо мной и уставилась в мой лист что я пишу. Я тогда мало умел справляться с такими ситуациями, от напряжения все забыл 😂
Просто попрощался и ушел 😂
А когда только вышел из здания, решение мне в голову пришло 😂
Хорошо объясняешь, я джаваскриптизер на собесе при задаче на рекурсию не будут ли меня душить за хип оверфлоу?
Тады используй стек и цикл, они завсегда заменяют рекурсию. Там ты явно сможешь время выполнения и память контролировать. Кода конечно больше будет
Спасибо тебе, Саша. На твоем канале очень полезный контент. Хотел бы узнать, ты работаешь как бэкенд Java-разработчик?
Рад стараться!
Всегда работал как Java backend, но сейчас работаю над операционкой Android, делаю фичи для новых версий. Тоже Java/C++.
@@sashalukin Я работаю как Android-разработчик (Java/Kotlin) и хочу изучать Golang для бэкенда. Но я не уверен, является ли это хорошим выбором. Что бы ты посоветовал? Я хочу работать в крупных компаниях и люблю решать алгоритмические задачи.
Конкретный язык программирования не имеет значения на собесах в американские айти компании. Надо уметь решать литкод (любой язык программирования на твой выбор) + System Design, если идешь на middle и выше (3+ года опыта работы). Поэтому я бы сфокусировался на этом. Ну и самое главное - начать как можно раньше и как можно чаще проходить собесы. Конкретно сейчас с этим проблема, но из тех что я знаю - booking и uber продолжают нанимать. Напиши 10-20 рекрутерам каждой компании в Linkedin что хочешь устроиться работать к ним, и попробуй получить инвайты на собесы.
Спасибо, просто и понятно.
Только я не понял одно, почему во второй задаче мы не идем ниже по дереву если у ноды оба отрицательных ребенка? А если за одним из них стоит +40? Или это имелось в виду уже результат суммы всех детей ниже?
результат суммы предварительно считали всем (макс из нижележащих)
Слово лист прозвучало, но без определения)
Ну и казалось бы очевидный факт «почему дерево», ведь графически мы рисуем скорее густые корни?)
Ну просто наши деревья растут вниз)
Спасибо за интересный ролик. Удивительно, что решение с рекурсией "проходит".
Спасибо за понятное объяснение.
Спасибо за разбор задачи!
Чудесная подача теории! И код на джаве действительно понятен, хоть я и по питону больше!
У меня вопрос по первой задаче: почему при вычислении space comlexity худший вариан - это дерево, которое идет только на лево или только на право?
20:59 позволю себе ремарку:
`answer = Math.max(answer, maxLeftPath + maxRightPath + node.val);`
☝тут в `answer` будет записан 0 если на входе корень без детей, но с отрицательным значением или если в дереве только отрицательные значения ; мне кажется, нужно перед вызовом `helper()` инициализировать `answer = root.val`
0:40 если для кого-то это звучит сложно, то о каком собеседовании в Гугл может идти речь?
Динамическое программирование на деревьях! Крутизна!
13:38 почему не имеет смысла включать две вершины с отрицательными значениями?
Ведь одно уменьшит ответ меньше, чем другое
А почему суммируем корень + лево + право, когда по условиям второй задачи надо найти самое большое значение по пути, при этом по вершине можно пройти один раз?
Суммирование левого, правого и корня это есть сумма пути, если бы путь шёл от левого поддерева через корень в правое. Эта сумма идёт в ответ, но не в возвращаемое значение. То есть возвращаемое значение не включает эту сумму, поэтому изменение ноды -4 (например на 5) не поменяет значение, которое получает нода 20 (2), но если вместо 20 будет, скажем число -10, то в ответ пойдёт 5+(-3)+5 как лучшее из возможных
Хорош, отличное объяснение !
Спасибо за ролик! С удовольствием посмотрел
Спасибо, довольно понятно и очень полезно.
Классный урок, очень доходчиво, пасибо))
Я с похмелья...чуть с ума не сошел вникая в это...
Неверно задано начальное значение переменной answer. По условиям задачи у нас может дерево с ТОЛЬКО отрицательными значениями
Супер! Красавчик!
В условиях второй задачи не сказано, что есть хоть одно не отрицательное число. Так что все числа могут быть отрицательными.
На этот случай есть пустой путь с суммой 0.
@@Suselz Тогда должно быть условие что путь должен быть больше нуля, и должен содержать хотя бы один узел. Иначе задача математически некорректна
Максимально понятно все стало, спасибо!
вы сказали, что сто если на пути будет отрицательное то можно не идти, а что если после отрицательног оузла будет идти дочернее со значением 100, то есть тогла нам стоит пойти вниз
Ооооочень подробно объясняешь))
Прям для младших классов как будто бы
А какая пара годных уберкнижек есть по данным темам (алгосы и все такое)? Чтобы всю библиотеку не лопатить ...
17:54 почему ты сказал что в сумме будет 30, если взял не -3 с 8, а 2 и 8. Тогда получилось бы что мы плюсуем 2,8,28
В T-SQL такие штуки, как практические алгоритмы решения прикладных задач прохождения по Parent-Child иерархиям - реализуется при помощи рекурсивных CTE. Используется, например, для обработки и поддержания товарных справочников в ритейле. Ну а сама суть так же ложится в основу b-tree индексов, которые стараются на уровне их ядра поддерживать баланс «веса» значений детей
Great. Thank you for the explanation. Now trees seems not so terrible...
Большое спасибо за урок!
Гарний опис та рішення! Тільки я не зрозуміла останню задачу і тепер є думки на ніч 😅
Дякую за розбір, дуже класно
Радий що сподобалось!
Супер объяснение!