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