Ломаем решение из собеседования в Яндекс - пишем хвостовую рекурсию
HTML-код
- Опубликовано: 15 окт 2024
- В прошлом видео мы написали рекурсивное решение задачи из собеседования в Яндекс
В этом видео мы его сломаем, затем напишем улучшенную версию с хвостовой рекурсией.
Так же посмотрим на то в какой байткод компилируется обычная и хвостовая рекурсии и поговорим немного о внутренности JVM
Как всегда код пишем на языке скала в функциональном стиле
#Яндекс #Алгоритмы #Программирование
Топовый контент для подготовки к интервью!!!! Спасибо вам!!!!
Молодец, рад что открыл твой канал. Хорошая подача и умеешь доступно объяснить. Удачи в развитии канала :)
Рад, что в реках высветился именно ты. Очень полезная инфа
Нужно больше Scala на ютубе)
согласен
Аааааа, это scala?.. а я смотрю, думаю, что за функциональный питон случился?..
У автора большое будущее!
Круто обьясняешь! Впервые досмотрел видос с кодом и не пришлось себя продавливать к концу видео
По условию вроде было сказано, что имеется дерево "со взвешанными узлами". А судя по коду функция buildTree похоже генерирует дерево, которое "растёт" только в право.
Если бы дерево было бы "взвешенным", то тогда максимальная "глубина стека" будет примерно log(N). Что при N = 100000 (как в видео) будет не больше 17. А на 17 "погружений" стека точно хватит.
Поэтому получлось, что сам себе придумал задачу :)
Но всё это не отменяет полезности видео. А именно рассказ про стек и пример преобразования кода в хвостовую рекурсию.
UPD: Автор видео указал на то, что я не правильно понял термин "со взвешанными узлами". Я подумал, что подразумевается, что дерево сбалансировано. И комментарий написан исходя из такого предположения.
А разве дерево со взвешенными узлами всегда должно быть сбалансированным?
@@wolf_code Упс.
Меня просто смутила формулировка "со взвешанными узлами". Пытался нагуглить формулирвку но что-то ничего не получилось. Почему-то подумал, что имеется в виду, что дерево должно быть сбаралансированным.
@@krolser ага - тут нащупывается какая-та тонкая терминологическая грань. Если бы я сказал взвешенное дерево - то да это подразумевало бы сбалансированность (именно по количеству узлов)
Все равно спасибо за подробный анализ видео)
Спасибо за разбор, очень интересно, пойду попробую написать на других языках )
Нравятся твои видео
Классные картинки на превью, многие просто об этом не парятся, но это тоже влияет на восприятие и отношение автора к его контенту, зрителям
У тебя здорово получается совмещать юмористические вставки и грамотную техничесую речь
Желаю удачи в развитии канала, продолжай в том же духе!
P.S. Сам недавно проходил собеседование в Яндекс, но не прошел. Буду пробовать еще раз через пол года
Очень полезное видео! В топ!
Так а на самом собесе вы никак с собеседующим не обговаривали эту ситуацию? Или там было достаточно написать то что в первом видосе?
То же самое можно было попробовать объяснить иначе, ведь по сути это замена DFS на BFS, который можно и без компилятора наглядно написать итеративно.
Спасибо за уделенное на комментарий время Павел
Не совсем, DFS остался, ведь мы все равно достаем из начала (LIFO)
Без компилятора (Вы наверное имели ввиду без хвостовой рекурсии) у нас бы были смешаны логика работы со стеком/очередью с логикой работы алгоритма + мы бы нарушили ссылочную прозрачность
То же самое можно было объяснить тысячью разными способами)) Но специализация канала в том что тут любой код пишется в функциональном стиле
@@wolf_code Вы правы, спасибо большое за развернутый ответ
Если хвостовая рекурсия компилируется в итоге в цикл, то может сразу писать прогу в виде цикла?
Спасибо что уделили время на комментарий - это круто!
Метод с рекурсией получается более в функциональном стиле и более наглядным, мы не смешиваем логику работы со стеком с нашей логикой решения задачи кмк.
Использовав цикл с переменными мы бы нарушили ссылочную прозрачность (можно глянуть видео на канале про то что это)
Все примеры кода я стараюсь писать в функциональном стиле - поэтому на циклы и переменные изначально было наложено табу)
@@wolf_code а ок. я как-то не подумал про это. тогда действительно хвостовая рекурсия имеет место быть.
Разъяснил отлично, спасибо! Но хотелось бы чтобы где-то с права внизу было лицо рассказчика, и вместо курсора мышки использовать инструмент для выделения области, а не водить взгляд за твоим курсором.
Классно, удачи в развитии канала)
Спасибо, понятно. НО, а как не на функцианальном языке избавиться от рекурсии тут?
можно использовать стэк
Подскажите, как настроить ide так же минималистично ? Это intellij ? У меня в дефолтных настройках там глаза разбегаются от количества кнопок и окон
У меня так же))) Просто я включаю режим презентации (presentation mode) когда записиваю экран
Лайк за батю ))
Батя знает толк
Чувствую себя амебой но продолжаю смотреть и пытаться понять
Возможно для начала следует посмотреть предыдущее видео
ruclips.net/video/0-VQ3-jWGik/видео.html
Там очень понятное решение - затем можно повторно посмотреть это
Возник вопрос
Можно ли заменить веса вершин на веса ребер между ними и запустить Дейкстру?
В дейкстре ты ищешь кратчайший путь от А до Б, тут конечная точка неизвестна, она может быть любым узлом
@@wolf_code Мне казалось дийкстра ищет кратчайшие пути до всех точек, а А* до конкретной. Или это не про то?
@@PurpleDaemon_ да, ну применить можно, но кмк оверкилл
Хмм, интредастинг 🤔
Никогда раньше не задумывался о такой оптимизации (ну, раньше с подобной проблемой на практике и не встречался, бтв)
Завтра попробую это на крестах реализовать, а скала и правда довольно лаконичный язык.
Ух, кресты)) Как услышал словил вьетнамские segmentation фолты)
я почти ничего не понял, можно ли обойтись вообще без рекурсии?
Не нарушая принципов ФП нет
@@wolf_code ясно, спасибо
что за шрифт стоит у тебя в ide? Буду благодарен )
Jet Brains Mono
Впервые слышу, что такую рекурсию называют хвостовой. Чего не скажешь о варианте "восходящая рекурсия" и "нисходящая рекурсия" соответственно. Восходящая производит вычисление по факту выхода из рекурсии, нисходящая - по факту входа.
Спасибо за коммент
Про хвостовую рекурсию можно почитать тут ru.m.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
Буду рад за ссылки про нисходящую и восходящую рекурсии
Как я понял это не совсем общепринятые термины
@@wolf_code в этих формулировках они чаще встречаются в контексте функционального или логического программирования
@@maxlevs может быть, есть примеры статей или книг?
@@wolf_code позже накидаю, сейчас занят
И что же, ты устраивался в Яндекс не зная о хвостовой рекурсии или я что-то не так понял ?
Чтото не так понял
Что это за язык такой, скала (Дуэйн Джонсон?)
Сначала подумал, что это Python, уж больно синтаксис похож
Ага, язык от Дуэйна))
Можно погуглить scala language
Это язык общего назначения со строгой типизацией и поддержкой ФП и ООП
@@wolf_code А почему не раст?
@@joly3122 потому же почему не питон
@@wolf_code А почему не питон?
@@joly3122 ну я не знаю питон
Откуда Null в case(Null, sum)? притом, его подсказывает идея.
case object Null extends Tree
@@wolf_code В пред. видео было Nil, а в этом видео нет нового определения Tree
@@moonsund4085 ты прав, я переименовал Nil на Null чтобы не путать с Nil List-а
Странно, а разве в школе этому не учат? Про нехватку памяти и рекурсия. Как обойти это.
Ты про какую школу конкретно?
@@wolf_code 11 класс. Информатика. У нас была начальная инженерная школа. 2001г. Как первый курс универа. Я про то, что это базовые вещи. (Переполнение стека, работа с указателями итд итп.)
@@WhiteZSY крутая школа походу была))
Ну да знания базовые - канал в принципе про базовые знания) Но копаем вглубь
глядя на это видео, я понимаю, что я бы не стал писать на Scala D:
И код бати в итоге получился некрасивый
А какой код красивый по твоему?
Какой-то ты нервный. Зачем в моменты когда ничего печатаешь так адски много раз пожимать комбинации клавиш форматирования кода?
Есть такая привычка)) Это не форматирование кода, а сохранение в vim, никак не могу отделаться от привычки все время набирать :w, :w, :w когда думаю)
@@wolf_code можно вырезать эти звуки, если привычка как курение, хрен избавитшься)
@@uberLazyCoder хорошая идея, вообще думаю убирать звуки набора кода