Задачи в текcтовом виде и Домашка: right-lupin-f79.notion.site/BST-a7f237c4bcdf4898b17a0800017ae720?pvs=4 Продукт "Хакни алгоритмические собеседования" : tskills.ru/algo Бесплатный бот, чтобы прокачаться в теме "бинарные деревья": t.me/algocode_team_bot Личный ТГ канал: t.me/maksimfatin
Когда я учился на курсах, там было задание написать BST. Но странное BST. Слева от узла были узлы меньше, а справа - больше либо равные. То есть, BST допускало дубликаты. Плюс нерекурсивные методы обхода в глубину и в ширину. С удалением элемента вообще туши свет.
Обычно BST не допускает дубликатов и хранит их как дополнительный счетчик в вершине. Но то что справа есть дубликаты по значению - просто доп правило построения дерева, но мы в таком увеличиваем число узлов, что не очень для производительности На собесах обычно не просят удалять элементы из BST и не рекурсивные обходы так же редко спрашивают, но знание о них точно будет плюсом :)
что то в домашке супер сложное решение, там все намного проще, одним циклом и 2 строчки кода) идея такая же как в задаче 160. Intersection of Two Linked Lists public Node lowestCommonAncestor(Node p, Node q) { Node p1 = p; Node q1 = q; while(p1 != q1){ p1 = p1.parent != null ? p1.parent : q; q1 = q1.parent != null ? q1.parent : p; } return p1; }
Можно и так решать, но тут нужно объяснять еще дополнительно почему это работает :) Код простой, но как по мне чуть сложнее, хотя тут скорее вкусовщина Но как вариант указать дополнительно и это решение хороший поинт
Привет! пару дней назад по случайности наткнулся на твой видос, подумал: «гм, алгосы, сразу флешбеки с коляги вспомнились, все эти манипуляции с красно-чёрными деревьями, сортировки. но все же, зачем мне это, я ведь мобильщик» в итоге просмотрел почти все видосы в захлёб 😃 А ты сам как думаешь, насколько в бигтехах интересуются алгосами у мобильщиков?
А если задачу про валидацию дерева так решить. Дерево валидно, если при обходе получится отсортированный по возрастанию массив. Сам массив делать не обязательно. Храним предыдущий и текущий элемент при обходе. Если предыдущий больше или равен текущему - дерево не валидно.
Интересный вариант :) Кажется, что можно - единственное, что хранить предыдущий нужно будет как указатель или через замыкание или как class member, а так why not
Задачи в текcтовом виде и Домашка:
right-lupin-f79.notion.site/BST-a7f237c4bcdf4898b17a0800017ae720?pvs=4
Продукт "Хакни алгоритмические собеседования" :
tskills.ru/algo
Бесплатный бот, чтобы прокачаться в теме "бинарные деревья":
t.me/algocode_team_bot
Личный ТГ канал:
t.me/maksimfatin
за один час продолжительностью в 2.16)
Когда я учился на курсах, там было задание написать BST. Но странное BST. Слева от узла были узлы меньше, а справа - больше либо равные. То есть, BST допускало дубликаты. Плюс нерекурсивные методы обхода в глубину и в ширину. С удалением элемента вообще туши свет.
Обычно BST не допускает дубликатов и хранит их как дополнительный счетчик в вершине. Но то что справа есть дубликаты по значению - просто доп правило построения дерева, но мы в таком увеличиваем число узлов, что не очень для производительности
На собесах обычно не просят удалять элементы из BST и не рекурсивные обходы так же редко спрашивают, но знание о них точно будет плюсом :)
к тебе просьба про Джаву не забывай, нас много
меня в сбере про деревья и подавно не спрашивали)
что то в домашке супер сложное решение, там все намного проще, одним циклом и 2 строчки кода) идея такая же как в задаче 160. Intersection of Two Linked Lists
public Node lowestCommonAncestor(Node p, Node q) {
Node p1 = p;
Node q1 = q;
while(p1 != q1){
p1 = p1.parent != null ? p1.parent : q;
q1 = q1.parent != null ? q1.parent : p;
}
return p1;
}
Можно и так решать, но тут нужно объяснять еще дополнительно почему это работает :) Код простой, но как по мне чуть сложнее, хотя тут скорее вкусовщина
Но как вариант указать дополнительно и это решение хороший поинт
@@fatin.maksim Согласен, про доп объяснение) поэтому лучше к деревьям после связных списков переходить)
мне кажется потски нужно было сначала ообъяснить
в гдубину и ширину
Привет! пару дней назад по случайности наткнулся на твой видос, подумал:
«гм, алгосы, сразу флешбеки с коляги вспомнились, все эти манипуляции с красно-чёрными деревьями, сортировки. но все же, зачем мне это, я ведь мобильщик»
в итоге просмотрел почти все видосы в захлёб 😃
А ты сам как думаешь, насколько в бигтехах интересуются алгосами у мобильщиков?
Не очень сильно. Только в паре компаний спрашивают
А если задачу про валидацию дерева так решить. Дерево валидно, если при обходе получится отсортированный по возрастанию массив. Сам массив делать не обязательно. Храним предыдущий и текущий элемент при обходе. Если предыдущий больше или равен текущему - дерево не валидно.
Интересный вариант :) Кажется, что можно - единственное, что хранить предыдущий нужно будет как указатель или через замыкание или как class member, а так why not
1:27:08 почему по памяти O(h), а не O(N)?
O(h) просто более точная оценка. Т е h
Спасибо
Здравствуйте, на каком планшет пишете, что за стилус?
Привет! Samsung S7, стилус был из коробки :)
что делать если не получается перейти в notion ((
Хммм, грусненько. В ближайшее время постараюсь обновить ссылочки
@@fatin.maksim заработало, может быть без впна пытался