コーディング面接で
アルゴリズムのチートシートに、
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
動的計画法 (DP)
動的計画法
(DP) で 階段の 上り方を 数える 1 段か
2 段ずつ 上る とき、 n 段の 階段の 上り方が 何通り あるかを 数える。 小さな 段の 答えを 覚えて 使い回す、 動的計画の 最初の 練習です。 
動的計画法で
最大部分配列和を 求める 整数の
並びから、 続いた 区間の 合計の うち最大の 値を 求める。 「ここで 終わる 区間の 最大」を 1 つ 持ち 歩き、 並びを 1 回なめるだけで 解く 考え方の 練習です。 
動的計画法で
隣り合わない 要素の 合計を 最大にする 日ごとの
稼ぎの 並びから、 続けて 2 日は 選ばない 決まりで 合計の 最大を 求める。 各日で 「選ぶ」 「選ばない」の 2 通りを 比べて 表を 埋める、 動的計画の 練習です。 動的計画法
(DP) で おつりの 硬貨の 枚数を 最も 少なくする 何種類かの
硬貨を 何枚でも 使える とき、 ちょうど ある 金額を 作るのに 要る 最も 少ない 枚数を 求める。 大きい 硬貨から 取る 欲張りは 外れる ことが あり、 小さい 金額の 答えを 順に 積み上げる DP で 解きます。 動的計画法で
輪に なった 並びから 隣り合わない合計を 最大にする 日ごとの
稼ぎの 予定が 輪のように 繰り返し、 最後の 日と 最初の 日も 隣どうしに なる とき、 続けて 2 日は 選ばない 決まりで 合計の 最大を 求めます。 輪を 2 本の まっすぐな 並びに 分け、 同じ表の 埋め方を 2 回使う 練習です。 動的計画法で
2 つの 文字列に 共通する 最長の 部分列を 求める 2 つの
文字列から、 順番を 変えずに 文字を 拾って 作れる 共通の 並びの うち、 いちばん長い物の 長さを 求めます。 2 つの 文字列の 前から 何文字かずつを 表の 縦と 横に 取り、 欄を 順に 埋める 動的計画の 練習です。 部分和の
数え上げで 符号の 付け方を 数える 数の
並びの それぞれに + か - を 付けて 足した とき、 ちょうど 目標に なる 付け方が 何通り あるかを 数えます。 符号の 付け方の 問題を 「和が ある 数に なる 選び方の 数」に 言い換え、 1 次元の 表で 数える 練習です。 動的計画法で
硬貨の 組み合わせが 何通り あるかを 数える 何種類かの
硬貨を 何枚でも 使える とき、 ちょうど ある 金額に なる 組み合わせが 何通り あるかを 数えます。 並べる 順の 違いを 数えないために、 硬貨の 繰り返しを 外側に 置く 理由まで つかむ 練習です。 動的計画法で
文字列を 辞書の 単語に 区切れるか 調べる 空白の
抜けた 文字列を、 辞書に ある 単語だけで 区切れるかを 調べます。 「前から 何文字目までなら 区切れるか」を 表に 書き、 欲張りで 外れる 場合も 取り こぼさない 動的計画の 練習です。 動的計画法
(DP) と 二分探索で 最長の 増える 部分列を 求める 整数の
並びから、 順を 保ったまま 飛び飛びに 選んで、 どんどん 大きくなる 数の 列を 作る とき、 その 最も 長い 長さを 求める。 O(n²) の DP から 入り、 長さごとの 「最も 小さい 末尾」を 二分探索で 直す O(n log n) に 縮めます。 動的計画法で
2 つの 単語の 編集距離を 求める 1 文字の
挿入、 削除、 置き換えを 何回すれば、 ある 単語を 別の 単語に 変えられるかの 最小を 求めます。 2 次元の 表で 考え、 記憶を 表の 1 行分まで 縮める ところまで 詰める 練習です。 0-1 ナップサックで
荷物を 同じ 重さの 2 組に 分ける 荷物の
重さの 並びを、 重さの 合計が 同じ 2 組に 分けられるかを 調べます。 「半分の 重さちょうどの 選び方が あるか」に 言い換え、 1 次元の 表を 後ろから 埋める 0-1 ナップサックの 練習です。
解いた
言葉で