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