
コーディング面接で
アルゴリズムのチートシートに、
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
スライディングウィンドウ
窓の
左端に 最安値を 置いて 1 回の 売り 買いの 利益を 最大にする 日ごとの
値段の 並びから、 1 回だけ 買って、 それより 後の 日に 1 回だけ売る ときの、 いちばん 大きい 利益を 返します。 窓の 左端を それまでの 最安の 日に 置き、 右端を 1 日ずつ 進める 練習です。 スライディングウィンドウで
続いた 1 の 最長を 数える 0 と
1 だけの 並びから、 1 が いちばん長く 続いた 所の 長さを 返します。 並びを 1 回なめながら、 いま続いている 長さと 最長を 覚えて おく 練習です。 スライディングウィンドウで
幅 k の 平均が 最大の 所を探す 整数の
並びで、 続いた k 個の 平均が いちばん 大きくなる 所を 探し、 その k 個の 合計を 返します。 窓を 1 つずらすたびに、 入る 数を 足して 出る 数を 引く 練習です。
解いた
言葉で