ВБ
Size: a a a
2019 January 26
ДК
Павел сегодня джуну 2 месяца опыта без профильного образования задал задачку твою с LCA за О(1) по памяти, он с моими подсказками придумал алгоритм за 5 минут в итоге
Типа
Типа
find(node1,node2)
while (node1.hasParent) {
tmpNode: Node = node2
while (tmpNode.hasParent) {
if (node1 == tmpNode) return tmpNode
tmpNode = tmpNode.getParent
}
node1 = node1.getParent
}
П
Павел сегодня джуну 2 месяца опыта без профильного образования задал задачку твою с LCA за О(1) по памяти, он с моими подсказками придумал алгоритм за 5 минут в итоге
Типа
Типа
find(node1,node2)
while (node1.hasParent) {
tmpNode: Node = node2
while (tmpNode.hasParent) {
if (node1 == tmpNode) return tmpNode
tmpNode = tmpNode.getParent
}
node1 = node1.getParent
}
Круто че
П
А если искомые ноды лежат на разных уровнях
ДК
Чек алгоритм
П
Что за чек
ДК
Смотри
ДК
Check
ДК
Павел
А если искомые ноды лежат на разных уровнях
Алгоритму похуй, если ноды лежат на разном уровне, он для каждой левой ноды проматывает правую ноду до самой вершины в поиске совпадения
П
Ты не понял меня.
Root
/\
n1 n2
/ \
n3 n4
/ \
n5 n6
/ \
n7 n8
Root
/\
n1 n2
/ \
n3 n4
/ \
n5 n6
/ \
n7 n8
П
n5 и n8
П
n7 и n4
ДК
Просто алгоритм примени к дереву
ДК
Это работает
П
Ну ок. Пусть будет по твоему. Я беру твоего джуна в яндекс потому что мне похуй)
ДК
Не разочаровывай
ДК
Павел
Ну ок. Пусть будет по твоему. Я беру твоего джуна в яндекс потому что мне похуй)
Я просто хотел сказать, что задание то не такое уж и сложное и вместо того, чтобы бомбить лучше бы пришел домой и додумался до правильного решения, либо хотя бы нашёл его
ДК
А тебя просили закодировать там?
П
Я просто хотел сказать, что задание то не такое уж и сложное и вместо того, чтобы бомбить лучше бы пришел домой и додумался до правильного решения, либо хотя бы нашёл его
Ну в тако случае я скажу тебе что решил двумя способами, через пол часа после собеседования, отправил в скайп и он сказал чтотвсе верно. А вот код что ты скинул не мешало бы протестить. И про О(1) очень мало вероятно.