コーディング面接で
アルゴリズムのチートシートに、
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
設計
最小値を
並べて 持ち、 いちばん 小さい 値を すぐ 返す スタックを作る 積む、
取り出す、 いちばん上を 見る、 いま入っている 中の いちばん 小さい 値を 見る、の 4 つの 操作を、 どれも O(1) で こなすスタックを 作ります。 積むたびに 「ここまでの 最小値」も 一緒に 覚えて おく 練習です。 
辞書と
並びを 組み合わせて O(1) で 出し入れと 無作為な 取り出しが できる 集合を作る 値を
足す、 取り除く、 入っている 値から 1 つを 同じ 確率で 選ぶ、の 3 つを、 どれも 平均 O(1) で こなす集合を 作ります。 辞書と 並びの 2 つを 持ち、 取り除く ときは 末尾と 入れ替えて 穴を 作らない 練習です。 
辞書と
双方向 リストで LRU キャッシュを 設計する 容量が
決まった 覚え場所で、 いっぱいに なったら 最も 長く 使われていない 物から 捨てる 仕組みを 作る。 辞書で 鍵から 節へ 一度で 飛び、 双方向 リストで 使った 順を 並べると、 読むのも 書くのも 平均 O(1) で 済みます。 辞書と
二分探索で 時刻つきの 設定の 履歴を 設計する 設定の
名前ごとに、 いつどの 値に したかを 全部 残し、 「ある 時刻には どの 値だったか」を 答える 仕組みを 作る。 時刻が 増える 順に 書き足される ことを 使い、 読む ときは 二分探索で 探します。 ヒープで
短い 投稿の SNS の タイムラインを 設計する 投稿する、
フォローする、 外す、 タイムラインを 見る、の 4 つの 操作を 持つ 小さな SNS を 作る。 人ごとの 投稿を 新しい 順の 列と して 持ち、 タイムラインは ヒープで 何本もの 列から 新しい 順に 10 件だけ取り出します。 2 本の
ヒープで 流れてくる 数の 中央値を すぐ 答える 仕組みを作る 数が
1 つずつ 届く たびに 足しておき、 いつ 聞かれても、 それまでの 数の 中央値を 答える 仕組みを 作ります。 小さい 半分と 大きい 半分を 2 本の ヒープに 分けて 持ち、 境目の 2 つだけを 見る 練習です。
解いた
言葉で