---
title: "Телефонное интервью с Facebook 2014.07.21, 2-й вопрос"
description: "Телефонное интервью с Facebook 07/21/2014: Задача 2 2) Hайти наименьшего общего предка (lowest commo..."
author: "codekrolik"
published: "2014-07-23T02:21:38+00:00"
modified: "2014-07-24T00:30:48+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-2-y-vopros-422422"
markdown_url: "https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-2-y-vopros-422422/markdown"
site_name: "Yvision.kz"
---

# Телефонное интервью с Facebook 2014.07.21, 2-й вопрос

> Телефонное интервью с Facebook 07/21/2014: Задача 2 2) Hайти наименьшего общего предка (lowest commo...

Телефонное интервью с Facebook 07/21/2014: Задача 2

2) Hайти наименьшего общего предка (lowest common ancestor) для двух нод дерева. Ссылки на родителей не являются частью ноды дерева. Это "простое" бинарное дерево, т.е. не являющееся бинарным деревом поиска.

Мое решение: получить путь к двум нодам от корня, затем пройти от первого элемента листа до первого отличающегося элемента. Time complexity O(N) где N - количество элементов дерева.

[https://gist.github.com/codekrolik/ec86d6fcbf6c223b9dc9](https://gist.github.com/codekrolik/ec86d6fcbf6c223b9dc9)

Тесты для всех решений

[https://gist.github.com/codekrolik/2c2b9badeb45bb72fc3f](https://gist.github.com/codekrolik/2c2b9badeb45bb72fc3f)

Слабость моего решения в необходимости двух проходов по дереву для формирования путей к нодам. Книга Cracking the coding interview дает несколько другое решение данной проблемы. Этот подход я планирую реализовать в качестве тренировки позднее (это и будет, собственно, класс LCA2). По time complexity, насколько я понял, радикально не отличается от моего решения (тоже дает O(N)), но оптимальнее по фактическому количеству операций.

---

Source: [https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-2-y-vopros-422422](https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-2-y-vopros-422422)