
コーディング面接で
アルゴリズムのチートシートに、
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
二分探索
二分探索で
ソート 済み配列から 値を探す 小さい
順に 並んだ 整数から 目当ての 数の 位置を 探し、 無ければ -1 を 返す。 探す範囲を 毎回 半分に 狭める 二分探索の 練習です。 二分探索で
挿入位置を 求める 小さい
順の 並びで、 目当ての 数が あれば その 位置を、 無ければ 順を 崩さずに 入れる 位置を 返す。 二分探索が 止まった ときの 左の 端が 何を 指すかを 考える 練習です。 答えの
値で 二分探索して 締め切りに 間に 合う 最小の 速さを探す 何冊かの
本を 決まった 時間で 読み切るのに 要る、 1 時間 あたりの 最小の ページ 数を 返します。 並びではなく 答えの 値の 範囲を 半分ずつ 絞る、 二分探索の 使い方の 練習です。 二分探索で
同じ値が 続く 範囲の 両端を探す 小さい
順に 並んだ 整数の 並びから、 目標の 値が 続いている 範囲の 最初と 最後の 位置を 返します。 「この 値以上が 始まる 位置」を 探す 二分探索を 2 回使い、 端の 場合まで 詰める 練習です。 二分探索で
上って 下る 並びの 頂上を探す 上ってから
下る 整数の 並びから、 いちばん高い 所 (頂上) の 位置を 返します。 並び全体が 小さい 順でなくても、 隣と 比べた 向きで 範囲を 半分に 絞れる ことに 気づく 練習です。 二分探索で
回された 並びから 値を探す 小さい
順の 並びを 途中で 切って 前後を 入れ替えた 並びから、 目当ての 値の 位置を O(log n) で 探します。 半分に 割る たびに、 どちらの 半分が 順に 並んでいるかを 見分ける 練習です。 二分探索で
2 つの ソート 済み配列の 中央値を 求める 小さい
順の 2 つの 並びを 1 つに まとめずに、 まとめた ときの 中央値を O(log(min(m, n))) で 求めます。 短い方の 並びの 「切る 位置」を 二分探索で 探す練習です。
解いた
言葉で