Вторая задача с первого собеседования в Яндекс

#Программирование #Яндекс #Деревья #Алгоритмы

[@wolf_code]

Вот такой вот фетиш в яндекс на алгоритмические задачи)

[@user-xr7ou1xf9x]

Любые задачи на дерево решаются через BFS или DFS. Или обход в ширину, или в глубину. Тут, очевидно, в глубину. Такую задачу дают на собесах в Гугл и Амазон. Не знаю, кто начал раньше. Решение - отличное! Интересно было посмотреть, как оно на Scala реализуется. Спасибо за контент!

[@a.khakimov]

Выглядит очень красиво и лаконично

[@abdelk.2060]

Очень помогло, спасибо за видео!!!

[@TheSanSanch]

Лет пять назад собеседовался в яндекс, после созвона с HR было онлайн-интервью с разрабом и одной из задач он меня как раз просил посчитать максимальную сумму ветки) Ничего не меняется) забавно, но помню, как будто бы вчера было)

[@alexb1708]

привет с пикабу Подписался, спасибо теперь буду смотреть

[@ahmedrapira7610]

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

[@Khashimova_wellness]

How interesting!

[@maxds]

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

[@wolf_code]

есть второе видео, где мы ломаем данное решение, там будет проще сделать то что Вы хотите kzbin.info/www/bejne/ZpCXlJqCfLiggaM

[@user-eg6yg7xt9b]

Проходил собеседование в Microsoft. Спрашивали больше об абстрактном понимании рекурсии и многопоточности. Когда yandex в последний раз видел деревья на интерпрайзе?

[@wolf_code]

Не знаю, не работал в яндексе) Эти вопросы оч мало связаны не энтерпрайзом если конечно не писать либы

[@user-zp7ey1sl5b]

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

[@user-bu5hg5ru3d]

Не совсем понятно: в начале вы сказали что нужно найти ветку с максимальной суммой, а нашли сумму чисел в ветке с максимальной суммой. Если гооврить строго то ответ должен представлять собой перечисление идентификаторов узлов дерева по которым нашлась максимальная сумма, это потребует модификации метода MAX - но алгоритм по сути будет то же.

[@wolf_code]

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

[@igorromanenko336]

… душнила

[@Disorrder]

@@igorromanenko336 вообще, я бы перед решением уточнил, что в ответе нужно вернуть: просто сумму или прям саму ветку? Но поскольку мне не у кого спросить, я подумал, что наверное это усложнённая задача и имелась в виду сумма. Так что не душнила. Нормально подмечено.

[@kirillsushilnikov9614]

Вот смотрю я на этот Scala, рассказываете про его фишечки типа параметры по умолчанию, sealed, object и понимаю, что эти штуки есть в Kotlin. Scala появился в 2003г., Kotlin - в 2011г. Похоже, что Kotlin у них позаимствовал некоторые вещи.

[@7Denial7]

А вот мое решение на 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

[@pavuk7086]

Подскажите, какими материалами пользовались для изучения алгоритмов? Хочу к ним на фронта попасть)

[@wolf_code]

кормэн - алгоритмы построение и анализ

[@alexrassvet6204]

В задаче сказано: найти ветку с максимальной суммой узлов. Алгоритм просто выводит эту сумму. Это разные вещи.

[@wolf_code]

Да, это мой просчет, но алгоритм легко переделать чтобы возвращал ветку

[@zugzug90]

@@wolf_code как?

[@wolf_code]

@@zugzug90 при рекурсивном спуске храним еще и список узлов по которым спустились и возвращаем как значение из функции

[@Disorrder]

я бы решал от корня к листьям и потом взял бы максимум от всех листьев. Но так даже красивее) Хотел сказать я, но вспомнил про рекурсию. Я предпочитаю деревья упаковывать в массив, так можно обойтись без рекурсии. Достаточно понимать, что индекс корня = 1, а индекс потомков любой ноды = 2i и 2i+1.

[@wolf_code]

А если дерево неполное?

[@maxds]

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

[@wolf_code]

Не понял вопроса

[@maxds]

​@@wolf_code Извиняюсь.. Это я ошибся.. Я думал, что есть просто дерево, и на каждом узле свой вес, отличный от значения этого узла должен быть.. а на самом деле значение узла и есть вес этого узла. А не взвешенное бинарное дерево, это когда веса каждого узла равны, и тогда поиск наибольшей суммы по ветке равен ветке с наибольшим количеством узлов.

[@caftanfire7597]

Не знаю зачем это мне, но было интересно!

[@prost1qq]

А за рекурсию в Яндексе ни кто не спросил? или данный подход вполне применим к данной задаче?

[@wolf_code]

Есть еще одно видео на канале, где эту рекурсию я переделываю в хвостовую

[@wolf_code]

kzbin.info/www/bejne/ZpCXlJqCfLiggaM Подбробил на 2 части, т к мою дикцию пока врядли можно больше 10 минут выдержать)))

[@kimitsudesu]

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

[@wolf_code]

Можно было, второе видео почти про это, там поиск в глубину

[@TGrod]

Как же в этом языке всё лаконично выглядит) Вы, я так понимаю, на нём работаете?

[@wolf_code]

да

[@alexandrguravskiy9985]

Странное бинарное дерево, я думал что левая сторона должна всегда быть меньше правой или нет ?

[@wolf_code]

Вы наверное имели ввиду что значения узлов в левом поддереве должно быть меньше чем в правом? Не совсем, то о чем вы говорите это бинарное дерево поиска, а на видео просто бинарное дерево

[@alexandrguravskiy9985]

@@wolf_code а по какому алгоритму в это дерево туда кладут элементы и как их находят, и какой смысл от такого бинарного дерева?

[@wolf_code]

@@alexandrguravskiy9985 смысл какой от такого дерева это уже другой вопрос искуственная задача по алгоритмам для проверки знаний

[@alexandrguravskiy9985]

@@wolf_code Спасибо, пытаюсь найти практическое применение а его нет!🙃

[@wolf_code]

@@alexandrguravskiy9985 по условию надо найти максимальную ветку, поиск практического применения это уже другая задача)

[@obukhoff]

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

[@wolf_code]

Второй раз не ходил

[@obukhoff]

@@wolf_code не понравилось?

[@wolf_code]

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

[@gobpblueex]

Что это у вас за IDE ?

[@wolf_code]

Intellij Idea от Jet Brains

[@linuxeed]

Решение с DFS проще, зачем так усложнять?

[@wolf_code]

и какое оно будет?

[@linuxeed]

@@wolf_code если я правильно понял, его вы разобрали в следующем видео

[@wolf_code]

@@linuxeed уже и не помню

[@shaad1337]

Решение не будет работать если в дереве есть отрицательные числа

[@wolf_code]

Почему? Есть контртест?

[@shaad1337]

@@wolf_code Да, правда мой косяк. Это следующая задача, найти максимальную сумму любого подбранча в дереве.

[@___________S_t_a_s___________]

Это собеседование на кого, джуниор фронт энд?)

[@wolf_code]

🤣🤣🤣

[@___________S_t_a_s___________]

@@wolf_code да сегодня для джунов пол сотни библиотек требуют, пара деревьев там совсем не заметны.)

[@KeizashiAcidRain]

Это че на джуна задание ? Выглядит крайне просто

[@wolf_code]

Наверное ты слишком скиловый)

[@KeizashiAcidRain]

@@wolf_code да нет, просто вполне ясная реализация

[@KeizashiAcidRain]

@@wolf_code так на какую позицию такой таск ?

[@wolf_code]

@@KeizashiAcidRain я тогда на мидла шел, это был первый этап из 3х

[@KeizashiAcidRain]

@@wolf_code o_o спасибо за информацию

[@user-wz2sl8yu6s]

Я тоже подумал о обходе в глубину

[@wolf_code]

Обычно на собесе приходят в голову не самые красивые решения)