コーディング面接問題
コーディング面接でよく出る型を、易しい順に並べました。1 問ずつ、面接での聞かれ方、まず考える手順、Python と JavaScript の解答、計算量、よくある間違い、面接での話し方の例まで載せています。上から順に解くと、前の型が次の型の足場になります。
文字列
配列とハッシュ
- 03足して目標になる 2 つの位置整数の並びから、足すと目標の数になる 2 つを探し、その位置を返す。見た数を辞書に覚えておくと、並びを 1 回なめるだけで見つかります。
- 04並べ替えて同じ言葉になるか2 つの文字列が、文字を並べ替えるだけで同じにできるかを調べる。並べ替えて比べる書き方と、文字の数を数える書き方を比べる練習です。
- 051 回だけ出る最初の文字の位置文字列の中で 1 回しか出ない文字のうち、いちばん前にある物の位置を返す。先に全部を数え、もう 1 回読んで探す、2 回なめる考え方の練習です。
2 つの指
- 06前から読んでも後ろから読んでも同じか英字と数字だけを見て、大文字と小文字を区別せずに回文かどうかを調べる。両端に置いた 2 つの指を、まん中へ寄せていく考え方の練習です。
- 070 を後ろへ寄せる整数の並びの 0 を全部後ろへ寄せ、0 でない数の順は保ちます。書き込む位置の指と読む指の 2 つを使い、新しい並びを作らずに入れ替える練習です。
- 08小さい順の並びで足して目標になる 2 つ小さい順に並んだ整数の並びから、足すと目標になる 2 つの位置を返します。両端に指を置いて内側へ寄せ、余分な記憶を使わずに探す練習です。
スタック
再帰
二分探索
木の走査
動的計画の入口
- 18階段の上り方を数える1 段か 2 段ずつ上るとき、n 段の階段の上り方が何通りあるかを数える。小さな段の答えを覚えて使い回す、動的計画の最初の練習です。
- 19続いた区間の合計の最大整数の並びから、続いた区間の合計のうち最大の値を求める。「ここで終わる区間の最大」を 1 つ持ち歩き、並びを 1 回なめるだけで解く考え方の練習です。
- 20隣り合う日を選ばずに合計を最大にする日ごとの稼ぎの並びから、続けて 2 日は選ばない決まりで合計の最大を求める。各日で「選ぶ」「選ばない」の 2 通りを比べて表を埋める、動的計画の練習です。