Задача из Собеседования в Microsoft (Бинарные Деревья)

  Рет қаралды 228,276

Саша Лукин

Саша Лукин

Күн бұрын

Разбираем 2 задачи из собеседования в Microsoft в Пражский офис. Я постарался объяснить их так, чтобы было понятно даже тем, кто вообще про бинарные деревья в первый раз слышит.
Задачи на литкоде:
1 - leetcode.com/problems/path-sum/
2 - leetcode.com/problems/binary-...
Дисклеймер:
Изначальные задачи, которые спросили у подписчика, были другими. Я разобрал похожие, но которое уже есть на литкоде. Таким образом я и новые задачи не палю, и разбираем мы актуальные темы, на которые дают задачи на собеседованиях в топовые зарубежные IT компании.
00:00 О задачах
02:08 Немного теории
03:10 Первая задача
07:35 Разбираем на примере
09:50 Код первой задачи
11:38 Вторая задача
16:08 Разбираем на примере
18:26 Код второй задачи

Пікірлер: 578
@sashalukin
@sashalukin 25 күн бұрын
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
@alexanderpoplooukhin7448
@alexanderpoplooukhin7448 Жыл бұрын
Объяснение - просто 🔥. Это тот случай, когда у автора есть реальная способность доходчиво и лаконично объяснить алгоритмы и структуры данных
@victorprohorov6201
@victorprohorov6201 Жыл бұрын
а я не особо понял. лучше было бы если бы автор показал как это работает на примере
@yaroslavandreyev4246
@yaroslavandreyev4246 Жыл бұрын
@@victorprohorov6201 а чем этот пример, был не примером?
@victorprohorov6201
@victorprohorov6201 Жыл бұрын
@@yaroslavandreyev4246 я не понял как мы переходим по вершинам.
@user-hg8mk8tb2r
@user-hg8mk8tb2r Жыл бұрын
@@victorprohorov6201 рекурсивно, начиная с корня, до всех листов. Стрелки только немного сбивают - реально граф неориентированный, раз путь может идти от левого поддерева через вершину в правое поддерево.
@lostislandable
@lostislandable Жыл бұрын
POV устраиваешься в среднестатистический проект: просят на собеседовании решить задачу на алгоритмы и математические знания а после офера отправляют таски по верстке 🤯
@nickoni4
@nickoni4 Жыл бұрын
Ну так радоваться надо) изи мани)))
@user-rl8fy6xe1t
@user-rl8fy6xe1t Жыл бұрын
Да, но это не плохо
@bass1387
@bass1387 Жыл бұрын
Задачи могут быть разные, зависит от потребностей бизнеса))
@DevBer
@DevBer Жыл бұрын
Лишь бы платили как за алгиритмические задачи с вышматом под капотом =))
@lostislandable
@lostislandable Жыл бұрын
@@DevBer было б так, не было б пределу счастья :)
@sozinovss
@sozinovss Жыл бұрын
Александр, Спасибо! . У тебя талант объяснять сложные вещи, не останавливайся! Не оторваться - очень понятно и легко усваивается. Затягивает - утром вместо того, чтобы кофе налить - пошел смотреть другие ролики.
@lufavetskaya
@lufavetskaya Жыл бұрын
После обнаружения таких замечательных пояснений, начинаешь очаровываться алгоритмами! Спасибо за вашу работу. Нереально приятно изучать тему, с таким обучающим контентом❤
@Nardan78
@Nardan78 Жыл бұрын
Объяснение просто огонь. Сейчас как раз прохожу тему алгоритмов и структур данных, а ютуб подсунул видео. Несложные алгоритмы и сам нормально решаю, а вот структуры данных начали вызывать какой-то необъяснимый страх. Не думал, что весь алгоритм настолько прост. Спасибо!
@smileborsh9780
@smileborsh9780 9 ай бұрын
Даже ударение в слове «красивее» стоит правильно. 👏🏻💐
@user-to1sn4ft5e
@user-to1sn4ft5e Жыл бұрын
Очень круто, спасибо. Давно хотел разобраться с деревьями
@qumi645
@qumi645 Жыл бұрын
Шикарная подача! Всё доступно и понятно, особенно с учетом того, что я далек от программирования:)
@vasiliypupkin6311
@vasiliypupkin6311 Жыл бұрын
Дружище, спасибо тебе большое, пока твой разбор лучшее, что я видел в Ютубе для начинающих, разборы очень качественные, может сделаешь чек лист для джунов, что учить и как, спасибо!
@user-gs7ro3tl9t
@user-gs7ro3tl9t 7 ай бұрын
Я считаю, что это один из лучших каналов на ютубе по подготовке к алгоритмической секции! Спасибо огромное!!!
@ILikeActions
@ILikeActions Жыл бұрын
Отличный разбор и отличная подача! Ждем следующей задачи)
@sashalukin
@sashalukin Жыл бұрын
Спасибо!
@user-hg6tn5xn2k
@user-hg6tn5xn2k Жыл бұрын
шикарно, спасибо за разбор, с первой легко было, а вторая заставила подольше посидеть)
@2difficult2do
@2difficult2do Жыл бұрын
Хорошая подача и подробное объяснение. Буду заглядывать 😊
@sergiigordiienko2494
@sergiigordiienko2494 Жыл бұрын
Приятно смотреть и слушать. Очень понятное и детальное объяснение. Большое спасибо!
@user-zf9gl8fr5g
@user-zf9gl8fr5g Жыл бұрын
Разбор задачи хорошо подан. Классный контент. Буду ждать еще разборы алгоритмов
@vitali5615
@vitali5615 Ай бұрын
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!
@larnikodis1501
@larnikodis1501 Жыл бұрын
Саня, классный парень без понтов и умный. Так держать! Еще и спортивный.
@tima-obzor
@tima-obzor Жыл бұрын
Перешёл по рекам ютюба, подготовился, чаёк заварил. Накануне изучал видео о парадоксах математики и нобелевских лауреатах, доказавших ту или иную теорему. Так сказать был готов к удивляться, и что в итоге??? Теперь я понимаю из за каих специалистов у меня винда лагает)
@Dim4581
@Dim4581 Жыл бұрын
Спасибо!) отличный разбор. Интересно увидеть задачу о эффективном наполнении рюкзака
@georgiirozhnev
@georgiirozhnev Жыл бұрын
Блестящий разбор! Ждём продолжения
@user-cy5rq6ig6s
@user-cy5rq6ig6s Жыл бұрын
Лучший! Приятно смотреть) Продолжай записывать видео и не забрасывай)
@infomail8550
@infomail8550 Жыл бұрын
Очень классно все объяснил. Супер. Спасибо
@user-cv1jn5qy4v
@user-cv1jn5qy4v Жыл бұрын
Очень понравился формат. Сразу оформил подписку. Делай больше таких разборов, и добавляй их в отдельный плейлист на канале =)
@lyubov_zhulina
@lyubov_zhulina 10 ай бұрын
Если хотите понять деревья, посмотрите это видео 👌 идеально, большое спасибо за столь подробное объяснение 🔥🔥🔥
@goodvin8554
@goodvin8554 Жыл бұрын
Спасибо за разбор. Хотелось бы почаще.
@AnderPython-tw3kp
@AnderPython-tw3kp Жыл бұрын
Интересная задача. Объяснено довольно доходчиво! Спасибо
@FenBender01
@FenBender01 Жыл бұрын
Отличный разбор. Буду давать эту задачу на собеседованиях :)
@ValkRover
@ValkRover Жыл бұрын
Послушал с удовольствием. :) Удачи!
@enitefall
@enitefall Жыл бұрын
даже я понял после такого понятного объяснения! Супер!
@xlv4553
@xlv4553 Жыл бұрын
Топ, спасибо большое за такое объяснение, жду новых задач!
@RockyTheDog756
@RockyTheDog756 Жыл бұрын
Одна из лучших подач материала!
@niyazkhannanov5790
@niyazkhannanov5790 21 күн бұрын
Спасибо! посмотрел несколько роликов - очень доходчиво
@oOJIEWAOo
@oOJIEWAOo Жыл бұрын
Ура! Ты вернулся! Спасибо тебе за разбор
@user-pv5jf8vp5b
@user-pv5jf8vp5b 9 ай бұрын
Круто! Прям все по полочкам, реально класс! Спасибо👍🙏
@mtigames188
@mtigames188 Жыл бұрын
Круто! Спс! С первого раза непонятно, пересмотрю на досуге еще несколько раз)
@seyapanda108
@seyapanda108 11 ай бұрын
Спасибо за видео. В случае с деревьями желательно еще уметь решать dfs, bfs итерационно, а не только с помощью рекурсии. Если дерево будет выражено в список, то рекурсия уже не очень хороший вариант решения. Ну и не редко на собесах просят решить итерационно после решения с рекурсией
@_alexanderd
@_alexanderd Жыл бұрын
Спасибо за разбор задачи!
@Lammax2012
@Lammax2012 11 ай бұрын
Отличное объяснение! Just keep going! )
@Igor-tn7mq
@Igor-tn7mq Жыл бұрын
Побольше бы разборов задачек 🔥👍
@badcloud
@badcloud Жыл бұрын
Ого, поначалу зафтыкал, думал че за сложное объяснение, а на деле несколько строк кода емае. Мужик! Спасибо!
@zebrasbtl
@zebrasbtl Жыл бұрын
Просто супер, все просто и понятно!
@hopelesssuprem1867
@hopelesssuprem1867 Жыл бұрын
Спасибо за классные видео. Продолжай выпускать задачки по faang
@user-kp5og5so7f
@user-kp5og5so7f Жыл бұрын
Спасибо за понятное объяснение.
@VasillaRobocraft
@VasillaRobocraft Жыл бұрын
Спасибо за ролик! С удовольствием посмотрел
@GrigoriySokolik
@GrigoriySokolik 10 ай бұрын
Спасибо за интересный ролик. Удивительно, что решение с рекурсией "проходит".
@P0dCasts.io6o
@P0dCasts.io6o Жыл бұрын
Спасибо. Часть задач на бинарные деревья на лилкоде сделал, а часть отложил. Хотя для макс.пути понимал, что нужна рекурсия.
@acthanger7420
@acthanger7420 11 ай бұрын
Классный урок, очень доходчиво, пасибо))
@42jU29Mp
@42jU29Mp Жыл бұрын
Про Space: O(n) для первой задачи не сразу догадался. Видео хорошее.
@yaroslavandreyev4246
@yaroslavandreyev4246 Жыл бұрын
Очень хорошо объясняете👍
@NickRossik
@NickRossik 11 ай бұрын
В книге грохаем алгоритмы я не очень понял бинарные деревья, но зато теперь как понял! 😁 Супер объяснение, спасибо.
@user-cu4pi6ir9q
@user-cu4pi6ir9q 10 ай бұрын
Там не было деревьев…
@Mexanikkmm
@Mexanikkmm Жыл бұрын
Спасибо, довольно понятно и очень полезно.
@user-bj1ue3qs4m
@user-bj1ue3qs4m Жыл бұрын
Хорош, отличное объяснение !
@saveekglushchenko6903
@saveekglushchenko6903 Жыл бұрын
Думаю, что Вы хороший человек. Спасибо за видео
@reHgoc
@reHgoc Жыл бұрын
спасибо за разбор. Помню как на собеседовании на Unity dev решал задачу через алгоритм Дэйкстры (вглубь и вширь), а оказывается есть более простой способ.
@halcyon-s
@halcyon-s Жыл бұрын
Большое спасибо за урок!
@iforvard
@iforvard Жыл бұрын
Максимально понятно все стало, спасибо!
@ChannelYoJo
@ChannelYoJo Жыл бұрын
Динамическое программирование на деревьях! Крутизна!
@polinakir2991
@polinakir2991 Жыл бұрын
Супер! Красавчик!
@golodnenkiy
@golodnenkiy 2 ай бұрын
Классные задачи, спасибо автору. P. s. Не описать ту радость, когда сначала пытаешься решить задачу, а потом смотришь ролик, где твоё решение совпадает с решением автора. p.p.s Только сделать Answer и проверять на max в helper-e, я не догодался, а просто запихивал возможные пути в лист, а потом из него макс брал.
@go8tt
@go8tt Жыл бұрын
ты классный парень, спасибо за такие ролики С:
@luckyiam3532
@luckyiam3532 Жыл бұрын
Great. Thank you for the explanation. Now trees seems not so terrible...
@tsaykostya
@tsaykostya Жыл бұрын
Классный канал, автор приятный парень и никакого высокомерия
@TheYozka
@TheYozka Жыл бұрын
Хорошая подача материала
@user-wb1bh7sb2x
@user-wb1bh7sb2x Жыл бұрын
Каждый раз, когда собираюсь менять компанию, готовлюсь к таким задачам как в первый раз, затем на несколько лет забываю, и далее по кругу. Может быть лет 20 назад эти ОСНОВЫ ИЗ ЧЕГО ВСЕ СТРОИТСЯ и нужны были кому-то, сейчас для большиства разработки это вообще мимо. Впервые я изучил это все для собеседования, наверное, после 2х лет работы программистом, и никакого всевидящего ока в мир разработки мне не открылось, прошел собес и забыл, как всегда. С тем пор я поменял 4 компании и 3 страны, и заметил что зачастую на собесах попадаются консерваторы, которые считают, раз им это интересно, и раз они это заботанили, все вокруг должны это знать, и не важно что для проекта это нафиг не нужно, как будто это какие-то невероятные знания, смешно) Знание архитектурного дизайна намного важнее как по мне, потому что ты приходишь в компанию, и твой онбординг сокращается в разы, потому что ты уже скорее всего понимаешь как работает система. А эти стуктуры, достаточно знать что это такое, что такое бывает, и какая структура для чего работает, и для этого не обязательно решать какие-то сложные задачи и разбираться в них до транзиторов. Первая задача еще адекватная, но вторая это по-моему уже перебор, я бы наверное и решать ее не стал, потому что мне это тупо не интересно)
@MrOldschoolrocknroll
@MrOldschoolrocknroll Жыл бұрын
Если занимаешься простейшим формашлёпством или CRUDошлёпством, где нет ни хайлоада ни интересных задач, то да, это не пригодится. Но как только захочешь отойти от чужих либ и написать своё (более подходящее и масштабируемое решение), то упрёшься в узкость своих знаний, да даже тупо не зная как работает структура данных не сможешь оценить и быть уверенным, что нагруженное место не взорвётся в рантайме.
@user-wb1bh7sb2x
@user-wb1bh7sb2x Жыл бұрын
@@MrOldschoolrocknroll оо подъехали спецы нефармашлепы! 1) Я написал "А эти стуктуры, достаточно знать что это такое, что такое бывает, и какая структура для чего работает, и для этого не обязательно решать какие-то сложные задачи и разбираться в них до транзиторов. ", с чего ты взял что я "даже тупо не знаю как работает структура данных" и призываю вообще на них забить? 2) Я написал это в контексте собеседований, что зачастую их спрашивают когда они на проекте вообще не нужны. Если ты курнул и решил "написать своё (более подходящее и масштабируемое решение)", то флаг тебе в руки, никто не скажет тебе что структуры и алгоритмы для них не нужны. 3) И если ты "не зная как работает структура данных не сможешь оценить и быть уверенным, что нагруженное место не взорвётся в рантайме", то у меня для тебя плохие новости.
@MrOldschoolrocknroll
@MrOldschoolrocknroll Жыл бұрын
​@@user-wb1bh7sb2x Как же у тебя бомбануло то господи. Я же не конкретно про тебя писал а об индустрии в целом. Но раз ты воспринял всё на свой счёт, то у тебя с этим похоже какие-то проблемы))
@denvir2254
@denvir2254 11 ай бұрын
Ооооочень подробно объясняешь)) Прям для младших классов как будто бы
@dimasw99
@dimasw99 7 күн бұрын
От души братишка, под пиво вечерком посмотреть самое оно!
@leomysky
@leomysky 11 ай бұрын
Спасибо за видео Не очень понял идею с второй задачей, но суть уловил
@user-mi2st3eu3u
@user-mi2st3eu3u Жыл бұрын
Продолжай, брат ) У меня ничего не получается на литкоде )) Хотя принцип обхода знаю, но сложно уложить стэк в голове ))
@user-pg8ry1tm3t
@user-pg8ry1tm3t Жыл бұрын
Стек на самом деле самая простая структура после массива… можно представить себе тарелку с блинами - ты ж с низу блин не вытащишь и вниз не положишь🥴
@user-mi2st3eu3u
@user-mi2st3eu3u Жыл бұрын
@@user-pg8ry1tm3t да, так-то все понятно )) просто когда данные в стеке и тебе надо о них помнить это другое нежели тарелки представить )) это тарелки с данными ))
@user-fy6dm6mw9y
@user-fy6dm6mw9y 12 сағат бұрын
Спасибо за полезное видео
@AlexZvukov
@AlexZvukov Жыл бұрын
Отлично, спасибо. PS: качество подтянул 👍
@sashalukin
@sashalukin Жыл бұрын
Спасибо, учусь :)
@user-ev7uf3hi2s
@user-ev7uf3hi2s Жыл бұрын
Как раз вчера в университете начали проходить эти деревья)
@user-vv5jf6iy4j
@user-vv5jf6iy4j Жыл бұрын
лучшие разборы задач. у меня с литкодом разговор короткий, я его решать не умею, но приходится. а эти разборы вносят хоть какую-то светлую мысль в беспросветное.
@user-vv5jf6iy4j
@user-vv5jf6iy4j Жыл бұрын
@@ilya9261 задачи по дп слишком разные. книги раскрывают или совсем базовые задачи, которые не попадутся на собеседовании, или книги написаны исключительно для олимпиадников. потому что как раз из олимпиад эти задачи и вышли. я решил 60(возможно не показатель) задач по дп на литкоде. с барского плеча 10 максимум повторились. но в основном это довольно уникальные задачи, которые чаще всего решаются как по учебнику(рекурсия с мемоизацией, bottom up и может оптимизированное решение) но дойти к рекуррентому соотношению, я считаю, вообще не просто. ну или все вокруг меня слишком умные и им проще решать)
@ilya9261
@ilya9261 Жыл бұрын
@@user-vv5jf6iy4j а стоп, ну раз ты нарешал 60 задач по дп без подглядываний, то с чего бы ты тупил то на подобных задачах как в видео? она решается проще простого. Либо не интуитивно понимаешь свои же решения, либо хз в чем проблема. 60 не показатель, но уже что-то, не 0 (у меня сейчас меньше и я трудоустроен), продолжай в том же духе)
@user-vv5jf6iy4j
@user-vv5jf6iy4j Жыл бұрын
@@ilya9261 я перечитал свой коммент и понял, что забыл написать, что я так и не научился решать дп задачи)
@ilya9261
@ilya9261 Жыл бұрын
@@user-vv5jf6iy4j дак ты же 60 штук решил. Как решал?
@Saby1983x
@Saby1983x Жыл бұрын
@@user-vv5jf6iy4j > но дойти к рекуррентому соотношению, я считаю, вообще не просто. ну или все вокруг меня слишком умные и им проще решать) Это фигня и в жизни редко пригождается, поэтому примеры довольно вымученные. Я программирую 22 года, 10 в качестве хобби и 12 профессионально. Подобные задачи пригодились 3 раза - 2 в качестве хобби (игровой проект) и 1 на работе - тоже игровой, совершенно не типичный проект. Мой совет - требуют leetcode? пожелайте счастливого пути и ищите руководителя, который понимает, какие задачи Вы будете писать на работе. Если Вы не пишете AI для игр, то с подобными задачи будете иметь дело раз в пятилетку. Сядете, спокойно продумаете алгоритм (да, вместо 20 минут возможно целый день потратите) - но я Вас уверяю, отлаживать алгоритм и писать подходящие структуры для быстрой его работы (чтобы оно занимало вменяемое время и при этом можно было сохранить вне 1 Гигабайта) - Вы будете писать гораздо дольше.
@oleksandrl4136
@oleksandrl4136 8 ай бұрын
Дуже корисний канал. Дякую за Вашу роботу.
@overskam2699
@overskam2699 Жыл бұрын
побольше бы таких видео
@bass1387
@bass1387 Жыл бұрын
Это гениально!!))
@ihormilevskyi8175
@ihormilevskyi8175 Жыл бұрын
У тебя очень классный канал, вот бы ты чаще выпускал ролики. Очень сильно жду, ты предаешь мотивации идти дальше по IT. И ещё вопрос, кем конкретно ты работаешь? FrontEnd, BackEnd, Computer Science или что-то иное?
@sashalukin
@sashalukin Жыл бұрын
Спасибо! Всегда был Java backend, но сейчас в андройде, делаю фичи для новых версий. Тоже Java/C++. Но такие задачки в фаанг на всех спрашивают - и backend, и frontend, и ml
@ihormilevskyi8175
@ihormilevskyi8175 Жыл бұрын
@@sashalukin Спасибо за быстрый ответ, знаю что алгоритмы нужны везде)) Есть ли у тебя какая-то книга по алгоритмам которую ты бы мог порекомендовать, знаю только Grokking Algorithms
@sashalukin
@sashalukin Жыл бұрын
Если именно для собесов, то Cracking the Coding Interview, она очень известная, но мне как-то не очень зашло. А в целом по алгоритмам - Introduction to Algorithms Кормена
@user-cj1mq9fu3c
@user-cj1mq9fu3c Жыл бұрын
Ха-ха. Сегодня защищал лабораторную в универе, плохо сдал, а вот сейчас захожу в ютуб, чтобы найти, под какой видосик покушать, и вижу это! 🤩🤩🤩 Леди Фортуна, интернет и ютуб, спасибо вам! 😅
@eugenefedoryachenko8793
@eugenefedoryachenko8793 Жыл бұрын
Я смотрел твои видео чуть больше года назад, получил оффер с релокацией в европу) Теперь смотрю твои видео перед собеседованием в яндекс, но в этот раз решил подписаться)
@Gr-wv9rb
@Gr-wv9rb Жыл бұрын
В Европе не сложилось?
@eugenefedoryachenko8793
@eugenefedoryachenko8793 Жыл бұрын
@@Gr-wv9rb сложилось, просто яндекс предлагает больше денег, при этом ехать не далеко
@melheor4909
@melheor4909 Жыл бұрын
Я после его видосов получил офферы на альфа центавру, а второй на Ксандар. Вот думаю куда лететь
@eugenefedoryachenko8793
@eugenefedoryachenko8793 Жыл бұрын
@@melheor4909 я если что не писал, что я только после его видосов получил оффер, я в процессе подготовки натыкался на его видео, и объяснения мне понравились, даже е смотря на то, что тогда я собесился на позицию мидла в ts, а теперь на позицию синьора в go)
@melheor4909
@melheor4909 Жыл бұрын
@@eugenefedoryachenko8793 да я понял))
@airestonia
@airestonia Жыл бұрын
Очень хорошее видео! Огромное спасибо автору. Обрадовался когда увидел, что код на Java. Эх, нам бы вас в нашу команду 😊
@clenbuterol4989
@clenbuterol4989 Жыл бұрын
Какую команду вашу
@saimonshaplygin7867
@saimonshaplygin7867 11 ай бұрын
Привет! Саш, спасибо за разборы. У тебя очень хорошо получается. Рассказываешь сложные вещи доступным языком. Во второй задачке ошибка при инициализации поля answer. Изначально оно должно быть минус бесконечность. Так как если подать на вход функции дерево с одной вершиной, значение которой равно отрицательному числу. В версии на видео в качестве ответа мы получим 0, а не отрицательное число ps. Может быть кто-то уже писал об ошибке, но я не нашел в комментах
@alexyevdokimov642
@alexyevdokimov642 11 ай бұрын
И не только инициализация, там вообще с нулем нельзя сравнивать. Надо с минимально отрицательным. С чего автор решил, что понятие максимум это только для положительных чисел. А если там во всех узлах отрицательные value? Уже не будет правильного ответа? Ну а по сути, логика в целом верная. А рекурсия - это все равно зло :)
@Game_Pro_
@Game_Pro_ 4 ай бұрын
а кем работаешь? просто интересн окакая зарплата@@alexyevdokimov642
@user-hc2rx3ge2z
@user-hc2rx3ge2z Жыл бұрын
Во второй задаче можно использовать центроидную декомпозицию дерева, мне кажется это идейно проще
@user-xj7te3qs8u
@user-xj7te3qs8u Жыл бұрын
Лучший ❤ 😊
@HOMEP11
@HOMEP11 Жыл бұрын
благодарю!
@kseniiaefremova4696
@kseniiaefremova4696 Ай бұрын
Чудесная подача теории! И код на джаве действительно понятен, хоть я и по питону больше! У меня вопрос по первой задаче: почему при вычислении space comlexity худший вариан - это дерево, которое идет только на лево или только на право?
@Gribozhuy
@Gribozhuy Жыл бұрын
Вторая задача - все же answer = Integer.MIN_VALUE; Так как в случае с деревом состоящим всего из одного отрицательного желемента - ответ будет 0, а должен быть - само это отрицательное число.
@slavakonashkov
@slavakonashkov Жыл бұрын
Правильное замечание, но этого не достаточно. В коде, там где max, тоже нужно логику поменять.
@Gribozhuy
@Gribozhuy Жыл бұрын
@@slavakonashkov нет, в остальном все правильно.
@tsv83
@tsv83 Жыл бұрын
Просто решение у автора некорректное. Либо задача поставлена криво. Автор декларирует "дальше не пойдём" но по факту это работает только если отрицательный узел один и сравнивается с мнимым узлом, чьё значение 0. Если у 5 будет не один ребёнок -2, а ещё один, скажем -5 - решение будет несоответствовать задаче.
@user-xh1ms1ke6c
@user-xh1ms1ke6c Жыл бұрын
@@tsv83 работать будет и с вашим примером, поскольку с нулём сравнивается и helper(node.left) и helper(node.right), который, в свою очередь содержит максимальную сумму дальнейшего пути, то есть, в момент сравнивания уже учитывается, есть ли там что-то дальше, как то с "-3", у которой ребёнок "5"
@tsv83
@tsv83 Жыл бұрын
@@user-xh1ms1ke6c нет, не будет
@dreambreaker226
@dreambreaker226 Жыл бұрын
Да . столько раз ты это объяснял в элементарном введении в К.М. а они всё равно не понимают и спорят. Пасибо за ролик
@SolidG-ne4jt
@SolidG-ne4jt Жыл бұрын
Когда ты сказал, что нужно "найти путь", а потом продолжил говорить именно про сумму ветки, меня это смутило. Изначально из твоих слов верно было подумать, что требуется найти путь, то есть последовательность нод, список, так скажем, состоящих в ветке с наибольшей суммой. Как говорится, без внятного тз результат будет "хз" :)
@sovahc
@sovahc Жыл бұрын
Путь - это список нод (ну или список направлений). Так что задача не решена, автор собеседование не прошел :)
@AkramAzizmurodov
@AkramAzizmurodov Жыл бұрын
Спасибо тебе, Саша. На твоем канале очень полезный контент. Хотел бы узнать, ты работаешь как бэкенд Java-разработчик?
@sashalukin
@sashalukin Жыл бұрын
Рад стараться! Всегда работал как Java backend, но сейчас работаю над операционкой Android, делаю фичи для новых версий. Тоже Java/C++.
@AkramAzizmurodov
@AkramAzizmurodov Жыл бұрын
@@sashalukin Я работаю как Android-разработчик (Java/Kotlin) и хочу изучать Golang для бэкенда. Но я не уверен, является ли это хорошим выбором. Что бы ты посоветовал? Я хочу работать в крупных компаниях и люблю решать алгоритмические задачи.
@sashalukin
@sashalukin Жыл бұрын
Конкретный язык программирования не имеет значения на собесах в американские айти компании. Надо уметь решать литкод (любой язык программирования на твой выбор) + System Design, если идешь на middle и выше (3+ года опыта работы). Поэтому я бы сфокусировался на этом. Ну и самое главное - начать как можно раньше и как можно чаще проходить собесы. Конкретно сейчас с этим проблема, но из тех что я знаю - booking и uber продолжают нанимать. Напиши 10-20 рекрутерам каждой компании в Linkedin что хочешь устроиться работать к ним, и попробуй получить инвайты на собесы.
@tastebublik
@tastebublik Жыл бұрын
Спасибо за разбор, деревья моя ахилесова пята
@user-jg7ly1ib2z
@user-jg7ly1ib2z Жыл бұрын
Спасибо
@arenroger6507
@arenroger6507 Жыл бұрын
Супер
@imishka
@imishka Жыл бұрын
Есть у меня смутное предположение что если все значения в дереве будут отрицательными, то maxpathsum выдаст 0, а не мах отрицательный ответ, для этого наверное answer должен быть равен по умолчанию значению самой верхней вершины.
@gheoblink8862
@gheoblink8862 Жыл бұрын
Нет, по условию, мы имеем право взять 0 вершин, так что наш минимум - 0
@NoName-hi8bv
@NoName-hi8bv Жыл бұрын
Тож так думаю. Что если стоит отрицательное значение, а ниже много положительных
@user-bc5nm6fe3m
@user-bc5nm6fe3m Жыл бұрын
0 означает, что мы не берем левого\правого ребенка. Но после этого ответ для нашей вершины становится max(left, right) + val. Так что ошибки нет, и ответ может быть отрицательным, если положительных вершин вовсе нет
@imishka
@imishka Жыл бұрын
​@@user-bc5nm6fe3mэто возвращает функция helper, параллельно она записывает в переменную класса answer (максимум среди answer=0 и тем что вернул helper на данном шаге) А далее цель maxpathsum просто вывести эту переменную, соответственно если все отрицательно то answer так и останется 0. Выше написали что это вроде как правильно если ничего не брать, но в таких случаях наверное лучше уточнять данный кейс.
@michaeldeoz
@michaeldeoz Жыл бұрын
@@gheoblink8862 разве условие задачи не найти максимальный путь? Если два значения отрицательны не значит что одно из них не может быть максимальным?
@petraveryanov2572
@petraveryanov2572 Жыл бұрын
Во 2й задаче просто используем два значения - макс. путь в под-дереве и макс. путь в под.дереве, который начинается в корне. Ну и та же рекурсия. То же самое, но мне как-то проще.
@MVOralov
@MVOralov 7 ай бұрын
В T-SQL такие штуки, как практические алгоритмы решения прикладных задач прохождения по Parent-Child иерархиям - реализуется при помощи рекурсивных CTE. Используется, например, для обработки и поддержания товарных справочников в ритейле. Ну а сама суть так же ложится в основу b-tree индексов, которые стараются на уровне их ядра поддерживать баланс «веса» значений детей
@danilabagatyriya5737
@danilabagatyriya5737 5 ай бұрын
Когда сидел и не понимал, как решать, а потом сразу понял🙏🏾 Just do it!
@rudolfsikorsky7900
@rudolfsikorsky7900 Жыл бұрын
Спасибо, очень вовремя наткнулся на это видео! Как раз по работе надо решить дерево :) И к вопросу о том нужна ли программисту математика - НУЖНА! И не только для проникновения в Гугол :) Вот, я обычный вайтишник и мне понадобилась! Впервые за два года работы, но понадобилась :)
@user-ll2xw7tn6v
@user-ll2xw7tn6v Жыл бұрын
Это не та математика, о которой говорят что она не нужна. Это дискретная математика. А как правило не нужны, матан, тервер и геометрия. Конечно есть разделы, в которых нужна и геометрий (движки для игр, камера, свет) и тервер (всякие распознавания изображений), но это не программисты решают такие задачи, а математики.
@BellaLugoshi
@BellaLugoshi Жыл бұрын
напоминает обучение в автошколе - я купил тонюсенькую книжку с ПДД и учу правила, а остальные накупили разборы билетов и усиленно штудируют их. Но да - я потом сел и поехал на своем Заз-968М, а девочки расселись по новым Кайенам. Так что может вы и правы XD
@mew6085
@mew6085 Жыл бұрын
Вторая пожестче, понял со второго раза) 😂
@meerable
@meerable Жыл бұрын
Слово лист прозвучало, но без определения) Ну и казалось бы очевидный факт «почему дерево», ведь графически мы рисуем скорее густые корни?) Ну просто наши деревья растут вниз)
Задача из Собеседования на 160,000 Евро в Год
13:27
Саша Лукин
Рет қаралды 1,1 МЛН
I PEELED OFF THE CARDBOARD WATERMELON!#asmr
00:56
HAYATAKU はやたく
Рет қаралды 36 МЛН
La final estuvo difícil
00:34
Juan De Dios Pantoja
Рет қаралды 15 МЛН
Я Прошел Собеседование в Google… Как?
9:51
Саша Лукин
Рет қаралды 541 М.
Что такое WebSockets (веб-сокеты)
2:59
Хочу вАйти
Рет қаралды 4,3 М.
Хэш-таблицы за 10 минут
13:01
Николай Тузов — Golang
Рет қаралды 118 М.
УХОЖУ РАБОТАТЬ в MICROSOFT
45:11
itpedia
Рет қаралды 931 М.
Михаил Выборный собеседование junior python разработчик
56:37