課題とスコープ
0からnum_courses - 1までのラベルが付けられたnum_courses個のコースがあります。前提条件のペア [course, prerequisite]は、courseの前にprerequisiteを修了しなければならないことを意味します。すべてのコースを 修了できる任意の順序を返してください。そのような順序が存在しない場合は、空のリストを返してください。
このバージョンでは、0 <= num_courses <= 2000であり、各コースのラベルは有効で、ペアは 重複せず、入力には自己ループ（self-edge）が含まれていないと仮定します。num_courses == 0の場合は空のリストを返します。 num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]の場合、 [0, 1, 2, 3]と[0, 2, 1, 3]のどちらも正解です。[[1, 0], [0, 1]]の場合、2つのコースが相互に 依存しているため、唯一の有効な応答は空のリストです。
これは代表的な一般的なソフトウェアエンジニアリングのコーディング問題です。その中心的なタスクは、 自然言語の依存関係を有向グラフに変換し、そのグラフが非巡回であるかどうかを判定することです。 基本問題は任意の有効な順序を1つ求めています。辞書順で最小の順序、 コースの所要期間、あるいは同時履修コース数の上限は求めていません。
面接官が評価するポイント
最初の評価シグナルはエッジの向きです。[course, prerequisite]は prerequisite -> courseになります。前提条件を完了することでコースが解放されるためです。グラフを反転させても 順列が生成されることはありますが、その順列は逆の制約を表すことになります。
2つ目のシグナルは、候補者が「現在履修可能なコース」というフレーズから入次数（indegree）を導き出せるかどうかです。コースの入次数は、未達成のまま残っている直接の前提条件の数です。 入次数が0のコースのみが履修準備完了状態です。1つのコースを完了すると、その直接の後続コースの入次数のみがデクリメントされます。優れた回答は、単に「BFSを使う」と言うのではなく、この状態遷移を説明します。
3つ目のシグナルはサイクル検出です。キューが空になったからといって、部分的な結果を返すことは正当化されません。 結果の長さがコース総数と一致する場合にのみ、すべてのノードが処理されたことになります。結果がコース総数より短い場合は、 残りの部分グラフに入次数0のノードが存在せず、有向サイクルが含まれている必要があります。
面接官は計算量、境界条件、規約の厳密さも確認します。隣接リストによる実装は O(V + E)の時間と空間を使用します。deque.popleft()を使用することで、キューの先頭からの 取り出しを定数時間で維持します。テストには複数の有効な順序、孤立したコース、空の入力、 長い依存チェーンを含める必要があります。
回答前の明確化の質問
- 任意の順序を返せばよいですか、それとも辞書順最小である必要がありますか？ 通常のキューは任意の
順序を返します。辞書順最小の順序には最小ヒープ（min-heap）が必要となり、時間計算量の境界がO(E + V log V)に変化します。
- 前提条件のペアは重複することがありますか？ この問題では重複しないとされています。重複する可能性がある場合は、
隣接リストのエントリを重複して保持して両方を入次数にカウントするか、グラフ構築時に両方の構造から重複を排除します。 一方のみ重複を排除すると、カウントの整合性が崩れます。
- ラベルが無効であったり、入力に自己ループが含まれることはありますか？ 基本問題では検証済みの入力を
前提としています。防御的なAPIであれば、サイクルを含む有効なグラフと無効なリクエストを区別し、 両方のケースを単に空リストにマッピングしないようにするべきです。
- 有効な順序を1つ求める必要がありますか、それともすべて列挙する必要がありますか？ 1つの順序を見つけるのは線形のグラフ探索です。
すべての順序を列挙すると、現在利用可能なすべてのノードについて分岐が発生し、階乗に近い数の結果が生成される可能性があります。
- コースを並列に履修することは可能ですか？ 基本の結果は線形順序です。セメスターあたりの容量が無制限の場合、
最小セメスター数を求めるにはレベルごとのキュー処理が必要です。コースに所要期間がある場合、 問題はDAG上の最長経路計算になります。
- グラフはメモリに収まりますか？
V <= 2000に対して隣接リストは容易に収まります。
外部ストレージや分散処理が必要な場合は、異なるシステム問題となります。
30秒の回答フレームワーク
「各コースをノードとしてモデル化し、[course, prerequisite]を前提条件からコースへのエッジに変換します。また、各コースの入次数をカウントします。入次数が0のすべてのコースをキューに入れ、結果配列に1つずつ取り出しながら、その後続コースの入次数をデクリメントし、入次数が0になった後続コースをキューに追加します。キューには前提条件がすべて完了した未処理のコースのみが正確に含まれるため、どの選択も安全です。結果にすべてのコースが含まれていればそれを返し、そうでなければ残りのノードにサイクルが含まれているため空のリストを返します。隣接リストを使用した場合、時間と追加空間計算量はともにO(V + E)です。」
ステップバイステップの詳細解説
素朴な解法は、未選択のコースを繰り返しスキャンし、前提条件がすでに登場したものを選択します。完了したコースの集合を持っていたとしても、各ラウンドで全てのエッジを検査する可能性があります。チェーン状の依存関係ではV回のラウンドが必要となり、最悪ケースの計算量はO(VE)になります。満たされた依存関係を繰り返し再計算することがボトルネックです。
Kahnのアルゴリズムは、その情報を入次数としてインクリメンタルに維持します。graph[u]にuを完了した後に解放される可能性のあるコースを保持させ、indegree[v]に残っているvの直接の前提条件の数をカウントさせます。各[course, prerequisite]に対して、courseをgraph[prerequisite]に追加し、indegree[course]をインクリメントします。
このアルゴリズムは2つの不変条件を維持します：
indegree[v]は、未処理ノードからvへのエッジの数と等しい。- キューには、残りの入次数が0である未処理のコースのみが過不足なく含まれている。
初期カウントによって最初の不変条件が満たされ、入次数0のすべてのノードをキューに入れることで2つ目の不変条件が確立されます。コースuが取り出されるとき、それを指す未処理の前提条件は存在しないため、結果に追加しても安全です。uの削除は、graph[u]を訪問し、各後続ノードの入次数をデクリメントすることによって表現されます。後続ノードは、そのカウントが初めて0になった瞬間にのみキューに追加され、両方の不変条件が維持されます。
from collections import deque
def find_course_order(
num_courses: int,
prerequisites: list[list[int]],
) -> list[int]:
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prerequisite in prerequisites:
graph[prerequisite].append(course)
indegree[course] += 1
ready = deque(
course for course, degree in enumerate(indegree) if degree == 0
)
order: list[int] = []
while ready:
course = ready.popleft()
order.append(course)
for dependent in graph[course]:
indegree[dependent] -= 1
if indegree[dependent] == 0:
ready.append(dependent)
return order if len(order) == num_courses else []すべてのコースが取り出された場合、不変条件によって前提条件がすべてそれ以前に出現したことが保証されるため、結果は有効です。結果がVより短い場合、残りの有限部分グラフのすべてのノードは正の残余入次数を持ちます。残りの任意のノードから開始し、入ってくるエッジを繰り返し辿ると、有限グラフは最終的にノードを再訪しなければならず、その繰り返されるセグメントは有向サイクルです。したがって、完全な順序は存在しません。長さのチェックはサイクル検出テストでもあります。
各ノードはキューに高々1回入り、高々1回出ます。各エッジはグラフ構築時に1回、後続ノード解放時に1回処理されるため、時間計算量はO(V + E)です。隣接リスト、入次数配列、キュー、結果配列はO(V + E)の空間を使用します。Pythonのlist.pop(0)は残りの要素をシフトしてキュー操作を線形時間にしてしまう可能性があるため、実装にはdequeを使用します。
敵対的（Adversarial）なテスト検証では、1つの固定された答えではなく特性を検証する必要があります。成功した結果には正確にV個の一意なラベルが含まれていなければならず、すべてのペアについてprerequisiteの位置がcourseの位置より前でなければなりません。空のグラフ、1ノード、完全に独立したノード群、長いチェーン、複数の順序が存在するダイヤモンド構造、非連結成分、有向サイクルをテスト対象にします。ダイヤモンド構造のケースは、特定のトポロジカル順序を誤って要求するテストを検出します。
DFSでもトポロジカル順序を計算できます。白、灰、黒の状態を使用します。灰色ノードへのエッジはサイクルを検出し、ノードは帰りがけ順（ポストオーダー）で結果に追加され、最後に反転されます。DFSはAPIが具体的なサイクルを報告する必要がある場合に有用ですが、長いチェーンではPythonの再帰制限を超える可能性があります。Kahnのアルゴリズムは現在利用可能なコースのセットを明示し、並列セメスターへも自然に拡張できるため、ここではより直接的な選択肢となります。実現可能性のみが重要であるごく小さなグラフでは、繰り返しのスキャンの方がコードが短くなる場合がありますが、線形と呼ぶのではなく最悪ケースのコストを述べてください。
高品質な回答例
「まず、任意の有効な順序が許容されることを確認し、ラベルと重複のないエッジが有効であると仮定します。各[course, prerequisite]のペアは前提条件からコースへのエッジを作成します。これにより、コースの入次数は未完了の直接の前提条件の数を表すようになります。
隣接リストと入次数配列を構築し、入次数が0のすべてのコースをdequeに追加します。ループ内では、コースを結果に取り出し、その後続コースの入次数をデクリメントします。後続コースは、その入次数が0になったときにのみキューに追加されます。重要な不変条件は、キューには未完了の前提条件がないコースのみが含まれていることであり、キューから選択することでエッジの制約に違反することはありません。
キューが空になったときに無条件で返してはいけません。結果の長さがコース数と等しい場合、すべての依存関係が満たされました。短い場合は、残りのすべてのノードに入力エッジが存在します。有限グラフで入力エッジを辿ると必ずノードを再訪することになり、サイクルが残っていることが証明されるため、空のリストを返します。
隣接リストはすべてのノードとエッジを定数回処理するため、時間計算量はO(V + E)、空間計算量はO(V + E)になります。空のグラフ、1ノード、長いチェーン、複数の解があるダイヤモンド構造、非連結成分、2ノードのサイクルをテストします。複数の解が存在する場合、1つの固定配列と比較するのではなく、各前提条件の相対位置を検証します。」
よくある間違い
course -> prerequisiteを構築してしまう → 前提条件の前にコースが出現する可能性があります → 『このノードを完了すると何が解放されるか？』という問いに従ってprerequisite -> courseを構築する。- コース0からのみ探索を開始する → 非連結成分が欠落します → すべてのノードをスキャンし、初期状態で入次数が0のノードをすべてエンキューする。
- キューが空になったときに部分的な結果を返してしまう → サイクルを含む入力が成功として報告されます →
len(order) == num_coursesの場合にのみ順序を返す。 - ノードを複数回エンキューしてしまう → 結果に重複したコースが含まれます → 入次数が1から0へ遷移するときにのみエンキューする。
- キューとして
list.pop(0)を使用する → 大規模な入力で要素のシフトが繰り返されます →deque.popleft()を使用する。 - 出力を1つの固定されたトポロジカル順序と比較する → 別の有効な順序がテストで不合格になります → 一意性、長さ、およびすべてのエッジの相対位置を確認する。
- グラフの重複は排除するが入次数は排除しない、またはその逆を行う → 重複エッジの契約下でカウントが一致しなくなります → 重複を一貫して保持するか、グラフ構築中に各エッジの重複を排除する。
- 追加空間計算量を
O(V)と主張する → 隣接リストは依然としてすべてのエッジを保持します → この疎グラフ表現ではO(V + E)と報告する。 - 進行中（in-progress）状態を持たずにDFSを使用する → サイクルノードが何度も再帰するか、誤って終了します → アクティブなノードと完了したノードを分離するために少なくとも3つの状態を使用する。
発展的な質問と対策
フォローアップ1：辞書順最小の有効な順序を返すにはどうすればよいですか？
キューを最小ヒープに置き換えます。現在利用可能なすべてのノードの中から最小のラベルを選択することで、貪欲な交換論法により辞書順で最小の結果が得られます。エッジの処理はO(E)のままであり、ヒープの挿入と取り出しにより合計はO(E + V log V)になります。任意の順序でよい場合は、通常のキューの方がシンプルで高速です。
フォローアップ2：1セメスターあたりの並列コース数が無制限の場合、最小セメスター数はいくつですか？
現在のレベルサイズごとにキューを処理します。1つのレベルのコースは同じセメスターで完了し、新しく解放された入次数0の後続コースが次のレベルを形成します。レベルごとにセメスター数をインクリメントします。これは、すべてのコースが同じ所要時間であり、セメスターの容量が無制限である場合にのみ機能します。1セメスターあたり最大kコースという制限がある場合、単純なレベル処理では大域的最適性を達成できません。
フォローアップ3：コースの所要時間が異なる場合、最短の卒業時期をどのように見つけますか？
まずトポロジカル順序を取得し、その順序で動的計画法（DP）を実行します。コースの最早開始時刻は、その前提条件の最早終了時刻の最大値です。これにコース自身の所要時間を加えることで最早終了時刻が得られます。答えは最大終了時刻になります。10週間のコースと1週間のコースを同等に扱うことはできないため、Kahnのレベル分けだけでは不十分です。
フォローアップ4：具体的な依存関係のサイクルを1つ返すにはどうすればよいですか？
Kahnのアルゴリズムは残りの部分グラフにサイクルが存在することを証明しますが、そのパスは保持しません。残りのノードに対して3色のDFSを実行し、親ポインタを保存します。灰色ノードへのエッジに遭遇した際、親ポインタを逆に辿ることでサイクルを再構築します。診断が主要な要件である場合は、最初から親ポインタを追跡するDFSトポロジカルソートを使用できます。
フォローアップ5：前提条件のエッジが動的に追加される場合、順序をどのように維持しますか？
更新頻度が低い場合は、追加のたびにO(V + E)アルゴリズムを再実行するのが最も信頼性が高く検証も容易です。頻繁に更新される大規模グラフの場合は、各ノードの現在の位置を保持します。その順序とすでに整合しているエッジは変更不要です。整合していないエッジは、到達可能性チェックと影響を受ける区間内での再並べ替えが必要です。動的トポロジカル順序付けは複雑であるため、そのコストは測定されたグラフサイズと更新レートによって正当化される必要があります。
フォローアップ6：すべての有効なコース順序を列挙するにはどうすればよいですか？
バックトラッキングを使用します。各ステップで、現在のすべての入次数0のノードについて分岐し、一時的に1つを選択して後続ノードを更新し、再帰呼び出しを行った後に入次数を復元します。これにより無効な順列を回避できますが、有効な順序の数はV!に近づく可能性があるため、実行時間は少なくとも出力に比例します。まず小さな制限値を確認し、呼び出し側が実際に必要としているのが総数なのか、サンプルなのか、それとも最初のk個の順序のみなのかを尋ねてください。