時々私はこのようなインタビューの質問に出くわします：「ツリー内の任意の2つのノードの共通の親を見つけてください」。グーグルやアマゾンなどでもLCAの質問をしていることに気づきました。
ウィキペディアが言うように、LCAは、与えられたノードからルートへのパスの交差によって見つけることができ、O（H）を取ります。ここで、Hは木の高さです。さらに、O（N）でツリーを処理し、O（1）でLCAクエリに応答するより高度なアルゴリズムがあります。
このLCAの質問をする候補者について、インタビュアーが正確に何を知りたいのだろうか。パス交差の最初のアルゴリズムは些細なようです。彼らは候補者が前処理アルゴリズムを覚えていることを期待していますか？彼らは候補者がこれらのアルゴリズムとデータ構造をその場で発明することを期待していますか？
彼らはあなたが何でできているかを見たいと思っています。彼らはあなたがどのように考え、どのように問題に取り組み、締め切りからのストレスに対処するかを見たいと思っています。あなたがすでに解決策を知っているのであなたが問題を解決するならば、彼らはあなたに別の問題を提起するだけだと思います。それは彼らが望む解決策ではなく、あなたの頭脳です。
面接ではアルゴリズムに関する質問が多いので、答えを覚えていてもかまいません (または覚えてほしくありません)。あなたが知っている主な原則から答えを導くことができるようになってほしい.
現実的には、「X の実行方法」に対する答えがすでにわかっている場合、その場で答えをすばやく作成できる場合は、気にする必要が 2 つ少なくなります。最終的に: 現実の世界では、ドメイン X の問題に取り組んだ経験があるとは限りませんが、そのドメインの問題に出くわした場合は、合理的な答えを見つけ出す分析能力があることを願っています。 、あなたが持っている一般的な知識に基づいています。
ツリーは、ほとんどの人が知っていると想定しても安全な一般的なデータ構造です。答えがすぐにわかっている場合は、それを説明できるはずです。答えはわからなくても、データ構造を理解していれば、簡単に答えを導くことができるはずです。