Facebook エンジニアがまとめた 14 種類のアルゴリズム面接モード

プログラマー職の面接では、多くの場合、プログラミング面接プロセスを受ける必要があり、雇用主はこれを利用して面接者の技術的能力をテストします。しかし、これらの技術的な質問は実際の仕事とはあまり関係がない場合もあり、プログラミング面接の準備段階で大きなプレッシャーになる可能性があります。かつてFacebookとMicrosoftで働いていたEducative.ioの創設者、Fahim ul Haq氏は最近、プログラミング面接で遭遇する最も一般的な14の問題パターンをまとめた記事を公開しました。これは、さまざまなプログラミング面接の質問の「背後にある真実」を理解するのに役立つかもしれません。

多くの開発者にとって、プログラミングの仕事の面接準備は不安を誘発する可能性があります。面接ではカバーすべき内容が非常に多く、その多くは開発者の日常業務とは無関係であることが多く、余計なストレスがかかるだけです。

この状況は次のような結果をもたらしました。今日の開発者は、何百もの問題を理解するために、LeetCode などのサイトで何週間も費やす必要があることがよくあります。面接前に私が話す開発者が抱える共通の不安は、「現実世界の問題を十分に解決しただろうか？」というものです。もっとできたでしょうか？

だからこそ、私は開発者が各問題の背後にある根本的なパターンを理解できるように支援したいと思っています。そうすれば、開発者は何百もの問題を解決したり、LeetCode に疲れ果てたりすることを心配する必要がなくなります。面接の一般的なパターンを理解していれば、それをテンプレートとして使用して、さまざまなレベルでわずかに異なる問題を解決できます。

ここでは、プログラミング面接の問題を解決するために使用できる最も一般的な 14 のパターンをリストします。また、各パターンを識別する方法も説明し、各パターンの例題もいくつか示します。これらはほんの始まりに過ぎません。徹底的な説明、例、コーディングの練習については、「コーディング面接の理解: コーディングの質問のパターン」コースをぜひチェックしてみてください。

次のスキーマの説明では、データ構造がすでにわかっていることを前提としています。まだ知らない場合は、次のコースでデータ構造を確認できます: https://www.educative.io/m/data-structures

今日は以下の14のモードについて説明します。

1.スライディングウィンドウ

2.バイナリポインタまたはイテレータ

3.高速および低速のポインタまたはイテレータ

4.マージ間隔

5.循環ソート

6.リンクリストをその場で反転する

7.ツリー幅優先探索 (ツリー BFS)

8.ツリーの深さ優先探索 (ツリー DFS)

9. 2つの山

10.サブセット

11.修正二分探索

12. 最初のK要素

13. K-way マージ

14.トポロジカルソート

さあ始めましょう！

1.スライディングウィンドウ

スライディングウィンドウモードは、すべて 1 を含む最長のサブ配列を見つけるなど、特定の配列またはリンクリストの特定のウィンドウサイズに対して必要な操作を実行するために使用されます。最初の要素からウィンドウのスライドを開始し、要素ごとに右に移動し、解決する問題に応じてウィンドウの長さを調整します。ウィンドウサイズが一定のままになる場合もあれば、ウィンドウサイズが拡大または縮小する場合もあります。

特定の問題に対してスライディングウィンドウが必要かどうかを判断するために使用できるいくつかの方法を次に示します。

問題への入力は、リンクリスト、配列、文字列などの線形データ構造です。
最長/最短の部分文字列、部分配列、または目的の値を見つけるように求められます

スライディングウィンドウパターンを使用して解決できる一般的な問題:

サイズ K の部分配列の最大合計 (単純)
K 個の異なる文字を含む最長の部分文字列 (中)
同じ文字だが順序が異なる文字列を検索する（難しい）

2.バイナリポインタまたはイテレータ

2 つのポインタは、1 つまたは両方のポインタが特定の条件を満たすまで、2 つのポインタがタンデムパターンでデータ構造を反復するパターンです。バイナリポインターは、ソートされた配列またはリンクリスト内で一致を検索するときに役立ちます。たとえば、配列の各要素を他のすべての要素と比較する必要がある場合などです。

ポインタが 1 つしかない場合は、答えを見つけるために配列をループバックし続けなければならないため、ポインタが 2 つあると便利です。単一の反復子を使用したこのやり取りは、時間と空間の複雑さの両方において非効率的です。これは「漸近解析」と呼ばれる概念です。ブルートフォース検索や 1 つのポインタを使用した単純なバニラソリューションも機能しますが、これにより O(n²) 程度の結果が得られます。多くの場合、バイナリポインターは、より優れたスペースや実行時の複雑さを備えたソリューションを見つけるのに役立ちます。

2 つのポインターを使用するタイミングを識別する方法:

ソートされた配列（またはリンクされたリスト）を扱い、いくつかの制約を満たす要素のセットを見つける必要がある問題に使用できます。
配列内の要素はペア、トリプレット、またはサブ配列である。

2 ポインターパターンを満たす問題をいくつか示します。

ソートされた配列を平方する（簡単）
合計がゼロになる三つ子を見つける（中級）
バックスペースを含む文字列を比較する（中）

3.高速ポインタと低速ポインタ

高速ポインター方式と低速ポインター方式は、Hare & Tortoise アルゴリズムとも呼ばれ、配列 (またはシーケンス/リンクリスト) 内で異なる速度で移動する 2 つのポインターを使用します。このメソッドは、循環リンクリストまたは配列を処理する場合に非常に便利です。

異なる速度で移動することにより (循環リンクリストなど)、アルゴリズムは 2 つのポインタが出会う運命にあることを証明します。 2 つのポインタが同じループ内にある限り、高速ポインタは低速ポインタに追いつきます。

高速モードと低速モードをいつ使用するかを知るにはどうすればよいでしょうか?

リンクリストや配列内のループを扱う際の問題
特定の要素の位置やリンクリストの合計の長さを知る必要がある場合

上記の 2 ポインターアプローチよりもこのアプローチを優先すべきなのはどのような場合でしょうか?

移動を元に戻すことができない単一リンクリストなど、2 ポインターアプローチが適切ではない状況がいくつかあります。高速モードと低速モードが役立つケースの 1 つは、リンクリストが回文であるかどうかを判断する場合です。

高速ポインターモードと低速ポインターモードを満たす質問をいくつか示します。

リンクリストループ（シンプル）
回文リンクリスト（中）
円形配列をループする（難しい）

4.マージ間隔

Merge Intervals パターンは、重複する間隔を処理するための効果的な手法です。区間に関する多くの問題では、重複する区間を見つけるだけでなく、重複する区間を結合する必要があります。モードは次のように動作します。

2 つの間隔 (a と b) が与えられた場合、これら 2 つの間隔を相互に関連付ける方法は 6 つあります。

これら 6 つのケースを理解して識別すると、間隔の挿入から間隔のマージの最適化まで、さまざまな問題を解決するのに役立ちます。

では、Merge Intervals パターンをいつ使用するかをどのように決定するのでしょうか?

相互に排他的な範囲のみのリストを取得するように求められた場合
「重複区間」という言葉を聞いたことがあるなら

間隔パターンのマージに関する問題:

レンジクロスオーバー（ミディアム）
最大 CPU 負荷 (ハード)

5. 巡回ソート

このパターンは、特定の範囲の値を含む配列に関連する問題に対する興味深いアプローチについて説明します。ループソートパターンは、配列を一度に 1 つの値ずつ反復処理し、反復処理中の現在の値が正しいインデックスにない場合は、正しいインデックスの値と交換します。正しいインデックスの値を置き換えることもできますが、これは O(n^2) の複雑さを伴うため最適ではないため、循環ソートパターンが使用されます。

このパターンをどのように認識するのでしょうか?

指定された範囲内の値を持つ配列をソートする問題
ソートされた/ピボットされた配列内の欠落/重複/最小値を見つけるように求められた場合

ループソートモードの問題:

欠損値を見つける（簡単）
最小の欠損値を見つける（中）

6.リンクリストをその場で反転する

多くの問題では、リンクリスト内のノードセット間のリンクを逆にするように求められることがあります。通常、既存のノードオブジェクトを使用して、余分なメモリを消費せずにこれをインプレースで実行します。そこでこのモデルの出番です。このパターンは、リンクリストの先頭を指す変数 (current) から始まり、一度に 1 つのノードを逆にし、次に、処理された前のノードを指す変数 (previous) になります。ロックステップ方式では、次のノードに移動する前に、現在のノードを前のノードにポイントすることで、現在のノードの反転を実現できます。さらに、変数「previous」は、常に処理された前のノードを指すように更新されます。

このモードをいつ使用するかを認識する方法:

余分なメモリを使わずにリンクリストを逆にするように求められた場合

インプレース逆リンクリストパターンの問題:

サブリストを反転する（中）
K 要素のすべてのサブリストを反転する (中)

7.ツリー幅優先探索 (ツリー BFS)

このパターンは、ツリーをトラバースし、キューを使用して 1 つのレベルのすべてのノードを追跡してから次のレベルにジャンプする幅優先探索 (BFS) 手法に基づいています。このアプローチを使用すると、ツリーをレベルごとにトラバースする必要がある問題を効率的に解決できます。

ツリー BFS パターンは、ルートノードをキューにプッシュし、キューが空になるまで継続的に反復することで機能します。各反復で、キューの先頭にあるノードを削除し、そのノードを「訪問」します。各ノードをキューから削除した後、そのすべての子ノードもキューに挿入します。

ツリー BFS モードを識別する方法:

ツリーをレベルごとに（またはレベルごとに）トラバースするように求められた場合

ツリー BFS モードの問題:

バイナリツリーレベル順序トラバーサル（シンプル）
ジグザグトラバーサル（中）

8.ツリーの深さ優先探索 (ツリー DFS)

ツリー DFS は、深さ優先探索 (DFS) 手法に基づいてツリーをトラバースします。

再帰 (またはそのような反復的なアプローチのスタック) を使用して、トラバーサル中に以前の (親) ノードをすべて追跡できます。

ツリー DFS パターンの動作は、ツリーのルートから開始し、ノードがリーフノードでない場合は次の 3 つの処理を実行します。

1. 現在のノードを処理するか（前順序）、2 つの子ノードを処理する間に処理するか（順序内）、または 2 つの子ノードを処理した後で処理するか（後順序）を決定します。

2. 現在のノードの2つの子ノードに対して2回の再帰呼び出しを実行して処理します。

3. ツリー DFS モードを識別する方法:

ツリーをインオーダー、プレオーダー、ポストオーダーのDFSを使用してトラバースするように求められた場合
問題が、ノードがリーフノードに近いものを探すことを必要とする場合

ツリー DFS モードの問題:

パス数の合計（中）
合計のすべてのパス（中）

9. 2つの山

多くの問題では、与えられた要素のセットを 2 つの部分に分割する必要があります。この問題を解決するには、一方の部分の最小要素ともう一方の部分の最大要素を知ることが重要です。このモデルは、この種の問題を解決する効果的な方法です。このパターンでは、最小の要素を見つけるための最小ヒープと、最大の要素を見つけるための最大ヒープの 2 つのヒープを使用します。このパターンの動作は、まず前半の値を最大ヒープに格納するというものです。前半の最大値を見つけたいからです。次に、残りの半分を Min Heap に格納します。これは、後半の半分で最小値を見つける必要があるためです。いつでも、現在の値のリストの中央の値は、2 つのヒープの最上位要素から計算できます。

2 つのヒープパターンを識別する方法:

優先キュー、スケジュール設定などに役立ちます。
問題に集合の最小/最大/中間の要素を見つける必要があると書かれていた場合
バイナリツリーデータ構造の問題に使用されることもある

2 つのヒープモデルの問題点:

値のストリームの中央値を見つける（中）

10. サブセット

多くのプログラミング面接の質問には、与えられた要素セットの順列と組み合わせを操作することが含まれます。サブセットパターンは、これらすべての問題を効率的に処理するための幅優先探索 (BFS) アプローチについて説明します。

パターンは次のようになります。

集合[1, 5, 3]が与えられたとき

1. 空のセットから始める: [[]]

2.既存のサブセットすべてに最初の数字（1）を追加して、新しいサブセットを作成します：[[]、[1]]

3.既存のすべてのサブセットに2番目の数字（5）を追加します：[[]、[1]、[5]、[1,5]]

4.既存のすべてのサブセットに3番目の数字（3）を追加します：[[]、[1]、[5]、[1,5]、[3]、[1,3]、[5,3]、[1,5,3]]

このサブセットパターンを視覚的に表すと次のようになります。

サブセットパターンを識別する方法:

与えられた集合の組み合わせや順列を見つける問題

サブセットモードの問題:

重複したデータを含むサブセット化（単純）
大文字と小文字を変換して文字列をソートする（中）

11. 修正二分探索

ソートされた配列、リンクリスト、または行列が与えられ、特定の要素を見つけるように求められた場合、使用できる最適なアルゴリズムはバイナリ検索です。このパターンは、バイナリ検索に関連するすべての問題を効率的に処理する方法を説明します。

昇順コレクションの場合、パターンは次のようになります。

1.まず、開始点と終了点の中間点を見つけます。真ん中を見つける簡単な方法は、真ん中 = (開始 + 終了) / 2 です。ただし、整数オーバーフローが発生する可能性が高いため、中央の位置を次のように表すことをお勧めします: middle = start + (end — start) / 2。

2.キーが中間のインデックスの値と等しい場合は、中間の位置を返します。

3.キー値が中間のインデックスの値と等しくない場合:

4. key < arr[middle]が成立するかどうかを確認します。真の場合、検索を end = middle — 15 に簡略化します。 key > arr[middle]が成立するかどうかを確認します。真の場合、検索を終了 = 中間 + 1 に減らします。

この修正されたバイナリ検索パターンの視覚的な表現を以下に示します。

修正二分探索パターン問題:

順序に依存しない二分探索（単純）

ソートされた無限配列の検索（中）

12. 最初のK要素

与えられたセット内の最初の/最小の/最も頻繁に発生する K 個の要素を見つける必要がある問題はすべて、このパターンの範囲内です。

K 個の要素を追跡するのに最適なデータ構造はヒープです。このパターンでは、ヒープを使用して、一度に特定のセットの K 要素を処理する複数の問題を解決します。パターンは次のように機能します:

1. 問題に応じて、K個の要素を最小ヒープまたは最大ヒープに挿入します。

2.残りの数値を繰り返し処理します。ヒープ内の数値よりも大きい数値が見つかった場合は、その数値を削除して、大きい数値を挿入します。

ヒープが要素を追跡するため、ここではソートアルゴリズムは必要ありません。

最初の K 要素パターンを識別する方法:

与えられた集合の中で最初/最小/最も頻繁に出現するK個の要素を見つけるように求められた場合
特定の要素を見つけるために数字を並べ替えるように求められた場合

最初の K 要素パターンの問題:

最初の K 個の数字 (単純)
K 最も一般的な数字 (中)

13. Kルート合流

K 方向マージは、ソートされた配列のセットに関連する問題を解決するのに役立ちます。

K 個のソートされた配列が与えられた場合、ヒープを使用して、すべての配列のすべての要素のソートされたトラバーサルを効率的に実行できます。各配列の最小要素を Min Heap にプッシュして、全体の最小値を取得できます。全体の最小値が見つかった後、同じ配列の次の要素がヒープへプッシュされます。次に、このプロセスを繰り返して、すべての要素のソートされたトラバーサル結果を取得します。

パターンは次のようになります。

1.各配列の最初の要素を最小ヒープに挿入します。

2.その後、最小 (最上位) の要素がヒープから取得され、マージされたリストに追加されます。

3.ヒープから最小の要素を削除した後、同じリストの次の要素をヒープに挿入します。

4.手順2と3を繰り返して、結合されたリストをソート順に入力します。

K-way マージパターンを識別する方法:

配列、リスト、行列のソートに関する問題
問題がソートされたリストをマージするように要求している場合は、ソートされたリスト内の最小の要素を見つけます。

K-way マージモードの問題:

K ソートされたリストをマージする (中)
最大の K ペアを見つける (難しい)

14. トポロジカルソート

トポロジカルソートは、相互に依存する要素の線形順序を見つけるために使用できます。たとえば、イベント B がイベント A に依存する場合、トポロジカルソートでは A が B の前に来ます。

このパターンは、要素のセットのトポロジカルソートを実行する手法を理解するための簡単な方法を定義します。

パターンは次のようになります。

1.初期化。 a) HashMapを使用してグラフを隣接リストに格納します。b) すべてのソースを見つけるには、HashMapを使用して入次数を記録します。

2.グラフを構築し、すべての頂点の入次数を見つけます。 a) 入力に基づいてグラフを構築し、入次数ハッシュマップにデータを入力する

3.すべてのソースを検索します。 a) 入次数0の頂点はすべてソースであり、キューに格納されます。

4.選別。 a) 各ソースについて、次の操作を実行します。i) ソート済みリストに追加します。ii) グラフに従ってそのすべての子ノードを取得します。iii) 各子ノードの入次数を 1 減らします。iv) 子ノードの入次数が 0 になった場合は、ソースキューに追加します。 b) ソースキューが空になるまで (a) を繰り返します。

トポロジカルソートパターンを識別する方法: