コーディング面接で
アルゴリズムのチートシートに、
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
文字列
配列とハッシュ
Two Sum を
ハッシュマップで解く 整数の
並びから、 足すと 目標の 数に なる 2 つを 探し、 その 位置を 返す。 見た数を 辞書に 覚えて おくと、 並びを 1 回なめるだけで 見つかります。 アナグラムか
どうかを ハッシュで 判定する 2 つの
文字列が、 文字を 並べ替えるだけで 同じに できるかを 調べる。 並べ替えて 比べる 書き方と、 文字の 数を 数える 書き方を 比べる 練習です。 ハッシュで
最初の 重複しない 文字を探す 文字列の
中で 1 回しか 出ない 文字の うち、 いちばん前に ある物の 位置を 返す。 先に 全部を 数え、 もう 1 回読んで 探す、 2 回なめる 考え方の 練習です。 集合で
同じ値が 2 回出てくるかを 確かめる 整数の
並びの 中に、 同じ 値が 2 回以上 出てくるかを 判定します。 見た値を 集合に 覚え、 出てきた 値が もう 集合に あるかを 一定の 手間で 調べる 練習です。
ツーポインタ
スライディングウィンドウ
窓の
左端に 最安値を 置いて 1 回の 売り 買いの 利益を 最大にする 日ごとの
値段の 並びから、 1 回だけ 買って、 それより 後の 日に 1 回だけ売る ときの、 いちばん 大きい 利益を 返します。 窓の 左端を それまでの 最安の 日に 置き、 右端を 1 日ずつ 進める 練習です。 スライディングウィンドウで
続いた 1 の 最長を 数える 0 と
1 だけの 並びから、 1 が いちばん長く 続いた 所の 長さを 返します。 並びを 1 回なめながら、 いま続いている 長さと 最長を 覚えて おく 練習です。 スライディングウィンドウで
幅 k の 平均が 最大の 所を探す 整数の
並びで、 続いた k 個の 平均が いちばん 大きくなる 所を 探し、 その k 個の 合計を 返します。 窓を 1 つずらすたびに、 入る 数を 足して 出る 数を 引く 練習です。
スタック
連結リスト
二分探索
木 (DFS と BFS)
深さ優先探索 (DFS) で
二分木の 深さを 求める 二分木の
根から 一番 遠い 葉までの 段の 数を 返す。 左右の 子の 深さを 先に 求めて 1 を 足す、 深さ優先の 再帰の 練習です。 再帰で
2 本の 二分木が 同じか 確かめる 2 本の
二分木を 受け取り、 形も 値も まったく 同じかを 返します。 根を 比べ、 左どうし、 右どうしを 同じ 関数に 任せる、 木の 再帰の いちばん基本の 練習です。 再帰で
二分木を 左右反転する 二分木の
すべての 節で 左の 子と 右の 子を 入れ替え、 鏡に 映した 木を 返します。 下の 木を 先に 反転してから 付け替える、 木の 再帰の 基本の 練習です。 深さ優先探索で
二分木の 根から 葉までの 合計を 調べる 二分木の
根から 葉までの 道で、 値の 合計が 目標の 数に なる物が あるかを 調べる。 残りの 数を 子へ 渡しながら 潜る、 深さ優先の 再帰の 練習です。 再帰で
二分木の いちばん長い道の 長さを 求める 二分木の
中で、 いちばん離れた 2 つの 節を 結ぶ 道の 長さを、 辺の 数で 返します。 下から 高さを 返しながら、 ついでに 最長の 道を 数える、 木の 再帰の 練習です。 再帰で
二分木の 高さが 釣り合っているか 確かめる 二分木の
どの 節でも、 左と 右の 高さの 差が 1 以下かを 返します。 下から 高さを 返し、 崩れを 見つけたら 印を 返して 止める、 木の 再帰の 練習です。
二分探索木
動的計画法 (DP)
解いた
言葉で