wataru, спасибо, а то я задавился авторитетом и чуть мозг не вывихнул. Задача точно правильно понята, мы ее с голосом решали минут десять, но я пытался две очереди сходу сделать и не успел.
wataru, сравниваем именно упорядоченный результат обхода. В одном цикле можно, с двумя очередями, но это другая реализация того же самого алгоритма: получаем последовательность. Точно ведь линейно?
Есть основания полагать, что интервьюер таки умный и это я чего-то не понял. Что меняется, если деревья несбалансированные? Получаются лишние тупики, но их максимальное количество n+1. Может, еще что-нибудь?
Спасибо. Обойти два дерева в одном цикле было бы слишком просто. Сравнивать нужно именно упорядоченную последовательность, которая в дереве хранится, но вопрос не об этом.
Вопрос такой: DFS он ведь за O(n), а если два раза вызвать, то ведь все равно O(n), правильно?
Сначала я написал в лоб вот так, без if с лишними вызовами:
def tree_walk(node):
yield from tree_walk(node.left)
yield node.value
yield from tree_walk(node.right)
Получил feedback:
"Такое решение будет работать за O(n log n) на сбалансированных деревьях и за O(n^2) на несбалансированных. Следующим шагом я бы попросил его еще немного улучшить до O(n)."
Потом исправил, ответа не получил и теперь не знаю, есть ли что-то еще. Правильно ведь, что рекурсия и цикл дают одинаковую сложность обхода, разве что цикл эффективнее?
2. Извините, вопрос про обход и я не уточнил, что деревья по заданию считаются одинаковыми, если одинакова упорядоченная последовательность чисел. Форма может быть разной, иначе бы это в одном цикле все проверилось, что не интересно.
В вашем примере оба дерева хранят [1, 2, 3]. Код был оценен как глупый, но рабочий, так что об улучшении можно думать.
1. Tail call это да, было бы круто. На практике, я очень не люблю рекурсию и делаю ее только если данных совсем чуть-чуть и код получается почище, чем с циклом, т.е. очень редко. Я ведь прав, полагая, что указатель в очередь положить это дешевле, чем функцию вызывать?
Но вот абстрактно, когда начинается O(n), когда и почему оно заканчивается?
Спасибо, зайду к ним в офис.
Начинаю подозревать, что prepaid и debit карты это не всегда одно и то же. Встретил в сети упоминание 'prepaid credit', это когда по кредитной линии создается отдельная карта со специальным лимитом. Еще, на одном из форумов упоминание о том, что prepaid это когда баланс пополняется вручную.
Написано
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
