Любые задачи на дерево решаются через BFS или DFS. Или обход в ширину, или в глубину. Тут, очевидно, в глубину. Такую задачу дают на собесах в Гугл и Амазон. Не знаю, кто начал раньше. Решение - отличное! Интересно было посмотреть, как оно на Scala реализуется. Спасибо за контент!
Лет пять назад собеседовался в яндекс, после созвона с HR было онлайн-интервью с разрабом и одной из задач он меня как раз просил посчитать максимальную сумму ветки) Ничего не меняется) забавно, но помню, как будто бы вчера было)
А кстати, это решение подразумевает упрощенное понимание - найти ветку с наибольшей суммой узлов. Ведь так сами узлы остаются не найдеными, а найдена только сумма. Просто пытаюсь модифицировать этот алгоритм на поиск самих значений узлов и пока не получается придумать как это сделать, хотя должно быть не сложно.. но из-за его рекурсивности, видимо, не получается
дак если дерево - это рекурсивная структура, то как тогда мы можем идти снизу вверх, если число конечных узлов не известно? почему нельзя идти сверху вниз, и если мы к примеру знаем максимальное число, которое способно содержать узел (видимо 9 в этой задаче), понимать, идти ли нам дальше вглубь, или нет
Не совсем понятно: в начале вы сказали что нужно найти ветку с максимальной суммой, а нашли сумму чисел в ветке с максимальной суммой. Если гооврить строго то ответ должен представлять собой перечисление идентификаторов узлов дерева по которым нашлась максимальная сумма, это потребует модификации метода MAX - но алгоритм по сути будет то же.
Очень точно подмечено)) Я и сам в начале хотел найти саму ветку, вернуть список узлов на ней. Но решил не переусложнять алгоритм, и уже на этапе монтажа понял что чутка по другому решил задачу Но думаю это не прям серьезно - как Вы правильно заметили, алгоритм довольно легко доработать чтобы он возвращал и саму ветку тоже
@@igorromanenko336 вообще, я бы перед решением уточнил, что в ответе нужно вернуть: просто сумму или прям саму ветку? Но поскольку мне не у кого спросить, я подумал, что наверное это усложнённая задача и имелась в виду сумма. Так что не душнила. Нормально подмечено.
Проходил собеседование в Microsoft. Спрашивали больше об абстрактном понимании рекурсии и многопоточности. Когда yandex в последний раз видел деревья на интерпрайзе?
Вот смотрю я на этот Scala, рассказываете про его фишечки типа параметры по умолчанию, sealed, object и понимаю, что эти штуки есть в Kotlin. Scala появился в 2003г., Kotlin - в 2011г. Похоже, что Kotlin у них позаимствовал некоторые вещи.
Решение будет некорректным в случае наличия отрицательных ключей в дереве. Тогда максимальное поддерево не обязано начинаться корнем. В случае неотрицательных ключей такая ветка всегда будет начинаться от корня
я бы решал от корня к листьям и потом взял бы максимум от всех листьев. Но так даже красивее) Хотел сказать я, но вспомнил про рекурсию. Я предпочитаю деревья упаковывать в массив, так можно обойтись без рекурсии. Достаточно понимать, что индекс корня = 1, а индекс потомков любой ноды = 2i и 2i+1.
А вот мое решение на VBA, тоже рекурсивное. Оно учитывает варианты когда веса заданы отрицательные. И собирает в один лист (коллекцию) все узлы максимальной ветки: Public Function FindMaxBranch(BinTree As BinTreeNode, _ Optional ByRef total As Long) As Collection Dim ListL As Collection, ListR As Collection Dim totalL As Long, totalR As Long If BinTree Is Nothing Then Exit Function Set ListL = FindMaxBranch(BinTree.Left, totalL) Set ListR = FindMaxBranch(BinTree.Right, totalR) total = totalL Select Case True Case ListL Is Nothing And ListR Is Nothing: Set FindMaxBranch = New Collection Case ListR Is Nothing: Set FindMaxBranch = ListL Case ListL Is Nothing Or totalR > totalL: Set FindMaxBranch = ListR: total = totalR Case Else: Set FindMaxBranch = ListL End Select FindMaxBranch.Add BinTree total = total + BinTree.Weight End Function
А нельзя было просто пройтись поиском в ширину, добавляя значения из родительских узлов в дочерние? Плюс две переменные, хранящие максимальную известную на данный момент сумму и индекс соответствующего узла.
А разве бинарное дерево со взвешенными узлами не означает, что есть узлы, и каждый узел нужно взвесить определённым числом. и получается суммировать не сами числа в узлах, а число, умноженное на его вес?
@@wolf_code Извиняюсь.. Это я ошибся.. Я думал, что есть просто дерево, и на каждом узле свой вес, отличный от значения этого узла должен быть.. а на самом деле значение узла и есть вес этого узла. А не взвешенное бинарное дерево, это когда веса каждого узла равны, и тогда поиск наибольшей суммы по ветке равен ветке с наибольшим количеством узлов.
Вы наверное имели ввиду что значения узлов в левом поддереве должно быть меньше чем в правом? Не совсем, то о чем вы говорите это бинарное дерево поиска, а на видео просто бинарное дерево
Вот такой вот фетиш в яндекс на алгоритмические задачи)
Очень помогло, спасибо за видео!!!
Выглядит очень красиво и лаконично
Любые задачи на дерево решаются через BFS или DFS. Или обход в ширину, или в глубину. Тут, очевидно, в глубину. Такую задачу дают на собесах в Гугл и Амазон. Не знаю, кто начал раньше. Решение - отличное! Интересно было посмотреть, как оно на Scala реализуется. Спасибо за контент!
Лет пять назад собеседовался в яндекс, после созвона с HR было онлайн-интервью с разрабом и одной из задач он меня как раз просил посчитать максимальную сумму ветки) Ничего не меняется) забавно, но помню, как будто бы вчера было)
привет с пикабу
Подписался, спасибо теперь буду смотреть
How interesting!
А кстати, это решение подразумевает упрощенное понимание - найти ветку с наибольшей суммой узлов. Ведь так сами узлы остаются не найдеными, а найдена только сумма. Просто пытаюсь модифицировать этот алгоритм на поиск самих значений узлов и пока не получается придумать как это сделать, хотя должно быть не сложно.. но из-за его рекурсивности, видимо, не получается
есть второе видео, где мы ломаем данное решение, там будет проще сделать то что Вы хотите
ruclips.net/video/0_4cgLGSmKA/видео.html
дак если дерево - это рекурсивная структура, то как тогда мы можем идти снизу вверх, если число конечных узлов не известно?
почему нельзя идти сверху вниз, и если мы к примеру знаем максимальное число, которое способно содержать узел (видимо 9 в этой задаче), понимать, идти ли нам дальше вглубь, или нет
Не совсем понятно: в начале вы сказали что нужно найти ветку с максимальной суммой, а нашли сумму чисел в ветке с максимальной суммой. Если гооврить строго то ответ должен представлять собой перечисление идентификаторов узлов дерева по которым нашлась максимальная сумма, это потребует модификации метода MAX - но алгоритм по сути будет то же.
Очень точно подмечено)) Я и сам в начале хотел найти саму ветку, вернуть список узлов на ней. Но решил не переусложнять алгоритм, и уже на этапе монтажа понял что чутка по другому решил задачу
Но думаю это не прям серьезно - как Вы правильно заметили, алгоритм довольно легко доработать чтобы он возвращал и саму ветку тоже
… душнила
@@igorromanenko336 вообще, я бы перед решением уточнил, что в ответе нужно вернуть: просто сумму или прям саму ветку? Но поскольку мне не у кого спросить, я подумал, что наверное это усложнённая задача и имелась в виду сумма. Так что не душнила. Нормально подмечено.
Проходил собеседование в Microsoft. Спрашивали больше об абстрактном понимании рекурсии и многопоточности. Когда yandex в последний раз видел деревья на интерпрайзе?
Не знаю, не работал в яндексе)
Эти вопросы оч мало связаны не энтерпрайзом если конечно не писать либы
Вот смотрю я на этот Scala, рассказываете про его фишечки типа параметры по умолчанию, sealed, object и понимаю, что эти штуки есть в Kotlin.
Scala появился в 2003г., Kotlin - в 2011г. Похоже, что Kotlin у них позаимствовал некоторые вещи.
В задаче сказано: найти ветку с максимальной суммой узлов. Алгоритм просто выводит эту сумму. Это разные вещи.
Да, это мой просчет, но алгоритм легко переделать чтобы возвращал ветку
@@wolf_code как?
@@zugzug90 при рекурсивном спуске храним еще и список узлов по которым спустились и возвращаем как значение из функции
Не знаю зачем это мне, но было интересно!
Решение будет некорректным в случае наличия отрицательных ключей в дереве. Тогда максимальное поддерево не обязано начинаться корнем. В случае неотрицательных ключей такая ветка всегда будет начинаться от корня
Подскажите, какими материалами пользовались для изучения алгоритмов? Хочу к ним на фронта попасть)
кормэн - алгоритмы построение и анализ
я бы решал от корня к листьям и потом взял бы максимум от всех листьев.
Но так даже красивее) Хотел сказать я, но вспомнил про рекурсию.
Я предпочитаю деревья упаковывать в массив, так можно обойтись без рекурсии. Достаточно понимать, что индекс корня = 1, а индекс потомков любой ноды = 2i и 2i+1.
А если дерево неполное?
А вот мое решение на VBA, тоже рекурсивное. Оно учитывает варианты когда веса заданы отрицательные. И собирает в один лист (коллекцию) все узлы максимальной ветки:
Public Function FindMaxBranch(BinTree As BinTreeNode, _
Optional ByRef total As Long) As Collection
Dim ListL As Collection, ListR As Collection
Dim totalL As Long, totalR As Long
If BinTree Is Nothing Then Exit Function
Set ListL = FindMaxBranch(BinTree.Left, totalL)
Set ListR = FindMaxBranch(BinTree.Right, totalR)
total = totalL
Select Case True
Case ListL Is Nothing And ListR Is Nothing: Set FindMaxBranch = New Collection
Case ListR Is Nothing: Set FindMaxBranch = ListL
Case ListL Is Nothing Or totalR > totalL: Set FindMaxBranch = ListR: total = totalR
Case Else: Set FindMaxBranch = ListL
End Select
FindMaxBranch.Add BinTree
total = total + BinTree.Weight
End Function
А за рекурсию в Яндексе ни кто не спросил? или данный подход вполне применим к данной задаче?
Есть еще одно видео на канале, где эту рекурсию я переделываю в хвостовую
ruclips.net/video/0_4cgLGSmKA/видео.html
Подбробил на 2 части, т к мою дикцию пока врядли можно больше 10 минут выдержать)))
А нельзя было просто пройтись поиском в ширину, добавляя значения из родительских узлов в дочерние? Плюс две переменные, хранящие максимальную известную на данный момент сумму и индекс соответствующего узла.
Можно было, второе видео почти про это, там поиск в глубину
А разве бинарное дерево со взвешенными узлами не означает, что есть узлы, и каждый узел нужно взвесить определённым числом. и получается суммировать не сами числа в узлах, а число, умноженное на его вес?
Не понял вопроса
@@wolf_code Извиняюсь.. Это я ошибся.. Я думал, что есть просто дерево, и на каждом узле свой вес, отличный от значения этого узла должен быть.. а на самом деле значение узла и есть вес этого узла. А не взвешенное бинарное дерево, это когда веса каждого узла равны, и тогда поиск наибольшей суммы по ветке равен ветке с наибольшим количеством узлов.
Как же в этом языке всё лаконично выглядит) Вы, я так понимаю, на нём работаете?
да
Что это у вас за IDE ?
Intellij Idea от Jet Brains
А задачки со всторого собеседования будут?
Второй раз не ходил
@@wolf_code не понравилось?
@@obukhoff в первый раз ходил чтобы устроиться к ним, ходить чисто ради спортивного интереса - неуважение чужого времени
Странное бинарное дерево, я думал что левая сторона должна всегда быть меньше правой или нет ?
Вы наверное имели ввиду что значения узлов в левом поддереве должно быть меньше чем в правом?
Не совсем, то о чем вы говорите это бинарное дерево поиска, а на видео просто бинарное дерево
@@wolf_code а по какому алгоритму в это дерево туда кладут элементы и как их находят, и какой смысл от такого бинарного дерева?
@@alexandrguravskiy9985 смысл какой от такого дерева это уже другой вопрос
искуственная задача по алгоритмам для проверки знаний
@@wolf_code Спасибо, пытаюсь найти практическое применение а его нет!🙃
@@alexandrguravskiy9985 по условию надо найти максимальную ветку, поиск практического применения это уже другая задача)
Решение с DFS проще, зачем так усложнять?
и какое оно будет?
@@wolf_code если я правильно понял, его вы разобрали в следующем видео
@@linuxeed уже и не помню
Это собеседование на кого, джуниор фронт энд?)
🤣🤣🤣
@@wolf_code да сегодня для джунов пол сотни библиотек требуют, пара деревьев там совсем не заметны.)
Я тоже подумал о обходе в глубину
Обычно на собесе приходят в голову не самые красивые решения)
Решение не будет работать если в дереве есть отрицательные числа
Почему?
Есть контртест?
@@wolf_code Да, правда мой косяк. Это следующая задача, найти максимальную сумму любого подбранча в дереве.
Это че на джуна задание ? Выглядит крайне просто
Наверное ты слишком скиловый)
@@wolf_code да нет, просто вполне ясная реализация
@@wolf_code так на какую позицию такой таск ?
@@KeizashiAcidRain я тогда на мидла шел, это был первый этап из 3х
@@wolf_code o_o спасибо за информацию