コーディング面接で
アルゴリズムのチートシートに、
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
文字列
配列とハッシュ
ツーポインタ
ソート
済み配列の Two Sum を ツーポインタで解く 小さい
順に 並んだ 整数の 並びから、 足すと 目標に なる 2 つの 位置を 返します。 両端に 指を 置いて 内側へ 寄せ、 余分な 記憶を 使わずに 探す練習です。 ツーポインタで
水を 最も 多く ためる 2 本の 板を選ぶ 高さの
違う 板の 並びから 2 本を 選び、 間に ためられる 水の 量の いちばん 大きい 値を 返します。 両端に 指を 置き、 低い側の 指だけを 内側へ 寄せる 理由まで 言える 練習です。 ソートと
ツーポインタで 目標に いちばん近い 3 つの 和を 求める 整数の
並びから 3 つを 選んで 足し、 目標に いちばん近い 和を 返します。 並べ替えてから 1 つを 決め、 残りの 2 つを 両端の 指で 寄せて 探す練習です。 3 本の
指で 0 と 1 と 2 の 並びを 1 回で 並べ替える 0 と
1 と 2 だけが 入った 並びを、 その 場で 小さい 順に 並べ替えて 返します。 3 本の 指で 並びを 4 つの 区画に 分け、 1 回なめるだけで 仕分ける 練習です。 まん中から
広げて 最も 長い回文の 部分 文字列を探す 文字列の
中で、 前から 読んでも 後ろから 読んでも 同じに なる、 いちばん長い ひと 続きの 部分を 返します。 まん中に 2 本の 指を 置き、 両側へ 広げて 確かめる 練習です。
スライディングウィンドウ
スタック
再帰
二分探索
答えの
値で 二分探索して 締め切りに 間に 合う 最小の 速さを探す 何冊かの
本を 決まった 時間で 読み切るのに 要る、 1 時間 あたりの 最小の ページ 数を 返します。 並びではなく 答えの 値の 範囲を 半分ずつ 絞る、 二分探索の 使い方の 練習です。 二分探索で
同じ値が 続く 範囲の 両端を探す 小さい
順に 並んだ 整数の 並びから、 目標の 値が 続いている 範囲の 最初と 最後の 位置を 返します。 「この 値以上が 始まる 位置」を 探す 二分探索を 2 回使い、 端の 場合まで 詰める 練習です。 二分探索で
上って 下る 並びの 頂上を探す 上ってから
下る 整数の 並びから、 いちばん高い 所 (頂上) の 位置を 返します。 並び全体が 小さい 順でなくても、 隣と 比べた 向きで 範囲を 半分に 絞れる ことに 気づく 練習です。
木 (DFS と BFS)
二分探索木
スタックの
中順の 走査で 二分探索木の k 番目に 小さい 値を探す 二分探索木から、
小さい 方から 数えて k 番目の 値を 返します。 左、 自分、 右の 順に 読むと 小さい 順に なる ことを 使い、 その 読み方を 再帰ではなく スタックの 繰り返しで 書く 練習です。 二分探索木の
大小で 2 つの 節の 共通の 祖先を探す 二分探索木の
2 つの 値に ついて、 両方を 子孫に 持ついちばん深い 節 (共通の 祖先) の 値を 返します。 2 つの 値と 節の 大小だけで、 根から 1 本道で 下りられる ことに 気づく 練習です。 繰り返しで
二分探索木に 新しい 値を 葉と して足す 二分探索木に
新しい 値を 足し、 足した あとの 木を 返します。 大小で 左右へ 進んで 空いた 所を 探し、 そこへ 葉と して つなぐ 練習です。
ヒープ
トライ木
グラフ (グリッドの探索)
最短経路 (BFS)
素集合 (Union-Find)
トポロジカルソート
区間
バックトラック
動的計画法 (DP)
動的計画法で
最大部分配列和を 求める 整数の
並びから、 続いた 区間の 合計の うち最大の 値を 求める。 「ここで 終わる 区間の 最大」を 1 つ 持ち 歩き、 並びを 1 回なめるだけで 解く 考え方の 練習です。 動的計画法で
隣り合わない 要素の 合計を 最大にする 日ごとの
稼ぎの 並びから、 続けて 2 日は 選ばない 決まりで 合計の 最大を 求める。 各日で 「選ぶ」 「選ばない」の 2 通りを 比べて 表を 埋める、 動的計画の 練習です。 動的計画法
(DP) で おつりの 硬貨の 枚数を 最も 少なくする 何種類かの
硬貨を 何枚でも 使える とき、 ちょうど ある 金額を 作るのに 要る 最も 少ない 枚数を 求める。 大きい 硬貨から 取る 欲張りは 外れる ことが あり、 小さい 金額の 答えを 順に 積み上げる DP で 解きます。 動的計画法で
輪に なった 並びから 隣り合わない合計を 最大にする 日ごとの
稼ぎの 予定が 輪のように 繰り返し、 最後の 日と 最初の 日も 隣どうしに なる とき、 続けて 2 日は 選ばない 決まりで 合計の 最大を 求めます。 輪を 2 本の まっすぐな 並びに 分け、 同じ表の 埋め方を 2 回使う 練習です。 動的計画法で
2 つの 文字列に 共通する 最長の 部分列を 求める 2 つの
文字列から、 順番を 変えずに 文字を 拾って 作れる 共通の 並びの うち、 いちばん長い物の 長さを 求めます。 2 つの 文字列の 前から 何文字かずつを 表の 縦と 横に 取り、 欄を 順に 埋める 動的計画の 練習です。 部分和の
数え上げで 符号の 付け方を 数える 数の
並びの それぞれに + か - を 付けて 足した とき、 ちょうど 目標に なる 付け方が 何通り あるかを 数えます。 符号の 付け方の 問題を 「和が ある 数に なる 選び方の 数」に 言い換え、 1 次元の 表で 数える 練習です。 動的計画法で
硬貨の 組み合わせが 何通り あるかを 数える 何種類かの
硬貨を 何枚でも 使える とき、 ちょうど ある 金額に なる 組み合わせが 何通り あるかを 数えます。 並べる 順の 違いを 数えないために、 硬貨の 繰り返しを 外側に 置く 理由まで つかむ 練習です。 動的計画法で
文字列を 辞書の 単語に 区切れるか 調べる 空白の
抜けた 文字列を、 辞書に ある 単語だけで 区切れるかを 調べます。 「前から 何文字目までなら 区切れるか」を 表に 書き、 欲張りで 外れる 場合も 取り こぼさない 動的計画の 練習です。
設計
解いた
言葉で