コーディング面接問題

文字列の単語を逆順に並べ替える

空白で区切られた単語の順を逆にして、空白 1 つでつなぎ直す。文字列を前から読んで、単語の始まりと終わりを自分で見つける練習です。

辞書で同じ文字でできた語を組に分ける

文字を並べ替えると同じになる語どうしを、1 つの組にまとめます。語ごとに文字の数を数えた物を辞書の鍵にして、同じ鍵の語を集める練習です。

左右からの積で自分以外の積を並べる

整数の並びの各位置について、その位置を除いた全部の数の積を並べて返します。割り算を使わず、左からの積と右からの積を 2 回なめて掛け合わせる練習です。

集合で数独の盤に同じ数字の重なりが無いか確かめる

途中まで数字の入った 9 × 9 の数独の盤で、行、列、3 × 3 の箱のどれにも同じ数字が 2 回入っていないかを確かめます。見た数字を「どの行、どの列、どの箱か」と組にして集合に覚える、ハッシュの練習です。

前からの合計と辞書で和がちょうど k になる区間を数える

日ごとの増減の並びから、続いた日の合計がちょうど k になる区間の数を数えます。前からの合計を辞書に数えておき、「いまの合計から k を引いた値」が何回出たかを足していく、ハッシュの練習です。

集合で並べ替えずに 1 ずつ続く数の最長を求める

ばらばらに並んだ整数から、1 ずつ続いて並べられる数の、いちばん長い続きの長さを求めます。値を集合に入れ、続きの先頭の数からだけ数えて O(n) にする、ハッシュの練習です。

転置してから各行を逆にし、正方形の行列を時計回りに 90 度回す

n×n の行列を、新しい行列を作らずにその場で時計回りに 90 度回します。行と列を入れ替える転置と、各行の左右の反転の 2 つに分ければ、どちらも入れ替えだけで書ける練習です。

4 つの境目を狭めながら、行列を渦巻きの順に読む

m×n の行列を、左上から時計回りに外側の枠から内側へ渦巻きの順に読んだ並びを返します。上、下、左、右の 4 つの境目を持ち、1 辺を読むたびに 1 つ狭める練習です。

先頭の行と列を印の置き場にし、0 のある行と列を全部 0 にする

行列の中に 0 があれば、その行と列を全部 0 にします。どの行と列を消すかの印を、行列の先頭の行と先頭の列に書き込めば、追加の記憶を O(1) に抑えられる練習です。

繰り返し 2 乗で掛ける回数を減らし、x の n 乗を求める

小数 x と、負もありうる整数 n から、x の n 乗を求めます。n を 2 進で見て、x を 2 乗し続けながら 1 のビットの所だけ掛ければ、掛け算の回数が n の桁の数ほどで済む練習です。

筆算の位ごとの置き場に積を足し、数字の文字列どうしを掛ける

10 進の数字だけでできた 2 つの文字列の積を、文字列で返します。大きい整数の型に直さず、桁どうしの積を筆算の位ごとの置き場に足し、最後に繰り上げをまとめる練習です。

点の数を辞書に数え、向かいの角から軸にそろった正方形を数える

平面に点を足していき、ある点を 1 つの角とする軸にそろった正方形が何通り作れるかを数える仕組みを作ります。点ごとの個数を辞書に持ち、向かいの角を決めれば残りの 2 つの角が決まる、と気づく練習です。

XOR と AND の繰り上がりで、+ を使わずに 2 つの整数を足す

+ と - を使わずに、2 つの整数の和を求めます。繰り上がりを無視した和は XOR、繰り上がりは AND を 1 ビット左へずらした値なので、繰り上がりが 0 になるまで 2 つを足し直す練習です。

足す前にあふれを確かめながら、32 ビットの整数の桁を逆順にする

32 ビットの符号つき整数の 10 進の桁を逆順にした数を返し、範囲を出るなら 0 を返します。64 ビットの型に頼らず、桁を 1 つ積む前に「積んだらあふれるか」を確かめる練習です。

ソート済み配列の Two Sum をツーポインタで解く

小さい順に並んだ整数の並びから、足すと目標になる 2 つの位置を返します。両端に指を置いて内側へ寄せ、余分な記憶を使わずに探す練習です。

ツーポインタで水を最も多くためる 2 本の板を選ぶ

高さの違う板の並びから 2 本を選び、間にためられる水の量のいちばん大きい値を返します。両端に指を置き、低い側の指だけを内側へ寄せる理由まで言える練習です。

ソートとツーポインタで目標にいちばん近い 3 つの和を求める

整数の並びから 3 つを選んで足し、目標にいちばん近い和を返します。並べ替えてから 1 つを決め、残りの 2 つを両端の指で寄せて探す練習です。

3 本の指で 0 と 1 と 2 の並びを 1 回で並べ替える

0 と 1 と 2 だけが入った並びを、その場で小さい順に並べ替えて返します。3 本の指で並びを 4 つの区画に分け、1 回なめるだけで仕分ける練習です。

まん中から広げて最も長い回文の部分文字列を探す

文字列の中で、前から読んでも後ろから読んでも同じになる、いちばん長いひと続きの部分を返します。まん中に 2 本の指を置き、両側へ広げて確かめる練習です。

まん中から広げて回文になっている部分文字列を全部数える

文字列の続いた一部のうち、前から読んでも後ろから読んでも同じになる物がいくつあるかを数えます。回文のまん中を 1 つずつ決め、左右の 2 本の指を外へ広げて数える練習です。

スライディングウィンドウで同じ文字の無い最長の部分を探す

文字列の中で、同じ文字が 2 回出てこない続いた部分のうち、いちばん長い物の長さを返します。左右の端を持つ窓を伸ばし、重なりが出たら左の端を飛ばして縮める練習です。

スライディングウィンドウで k 枚まで塗り替えて同じ色の最長の並びを作る

色を英大文字で表したタイルの並びで、k 枚まで塗り替えてよいとき、同じ色が続く並びを最も長くします。窓の長さから最も多い色の数を引いた数が k 以下、を保つスライディングウィンドウの練習です。

長さを決めた窓で並べ替えた言葉が文の中に続けて入っているか調べる

言葉 p の文字を並べ替えた物が、文 s の中に途切れずに入っているかを調べます。p と同じ長さの窓を 1 文字ずつずらし、窓の中の文字の数を足し引きして比べる、長さを決めたスライディングウィンドウの練習です。

スタックで逆ポーランド記法の式を計算する

演算子を 2 つの数の後ろに書く記法の式を、文字列の並びで受け取って計算します。数を積んでおき、演算子が来たら上の 2 つを取り出して計算する、スタックの練習です。

スタックで今日より暖かい日まで何日待つかを並べる

毎日の気温の並びから、日ごとに「今日より暖かい日が来るまで何日待つか」を並べます。まだ答えの決まらない日をスタックに積み、暖かい日が来たらまとめて答えを決める、単調スタックの練習です。

着く時刻を前から比べて一本道でゴールに着く自転車の群れを数える

追い越しのできない一本道を走る自転車が、ゴールにいくつの群れで着くかを数えます。ゴールに近い順に並べ、前の群れより遅く着く自転車だけが新しい群れになる、と見抜く練習です。

半分に分けて後ろを逆にし、連結リストを前と後ろから互い違いに並べ直す

連結リストを、先頭、最後、2 番目、後ろから 2 番目、と前と後ろから交互に取る順につなぎ直します。まん中を探す、後ろ半分を逆にする、2 本を交互につなぐ、の 3 つを組み合わせる練習です。

間をあけた 2 本の指で連結リストの後ろから n 番目の節を外す

連結リストの後ろから数えて n 番目の節を外し、先頭を返します。n 歩先に出した指と一緒に進め、1 回なめるだけで外す節の 1 つ前を見つける練習です。

繰り上がりを持ちながら、1 の位から並んだ 2 本の連結リストの数を足す

数の桁を 1 の位から順に 1 つずつ持つ 2 本の連結リストを受け取り、2 つの数の和を同じ形の連結リストで返します。繰り上がりを持ちながら、長さの違う 2 本を同時になめる練習です。

速い指と遅い指で並びの中の重なった数を探す

1 から n までの数が n + 1 個入った並びから、2 回以上出てくる数を、並びを書き換えず O(1) の記憶で返します。値を次の行き先と見て連結リストの輪を探す練習です。

元の節と写しの対応表で random つきの連結リストを丸ごと写す

次の節のほかに、同じリストのどこかの節を指す random を持つ連結リストを、全部新しい節で写して返します。元の節から写しの節を引ける対応表を先に作り、つなぎ先を 2 回目でそろえる練習です。

再帰で入れ子の配列を平らにする

整数と並びが入れ子になった並びから、中の整数を左から順に 1 段の並びにして返します。並びの中の並びを同じ関数に任せる、再帰の練習です。

再帰で部分集合を全列挙する

整数の並びから作れる部分集合を、決まった順で全部返す。数ごとに「入れる、入れない」の 2 つに分かれる再帰の練習です。

答えの値で二分探索して締め切りに間に合う最小の速さを探す

何冊かの本を決まった時間で読み切るのに要る、1 時間あたりの最小のページ数を返します。並びではなく答えの値の範囲を半分ずつ絞る、二分探索の使い方の練習です。

二分探索で同じ値が続く範囲の両端を探す

小さい順に並んだ整数の並びから、目標の値が続いている範囲の最初と最後の位置を返します。「この値以上が始まる位置」を探す二分探索を 2 回使い、端の場合まで詰める練習です。

二分探索で上って下る並びの頂上を探す

上ってから下る整数の並びから、いちばん高い所 (頂上) の位置を返します。並び全体が小さい順でなくても、隣と比べた向きで範囲を半分に絞れることに気づく練習です。

二分探索で行ごとに並んだ表から値を探す

各行が小さい順に並び、行の頭が前の行の最後より大きい表から、目標の値があるかを返します。表を 1 本の長い並びと見なして二分探索する練習です。

二分探索で回された並びのいちばん小さい値を探す

小さい順の並びを途中で切って前後を入れ替えた並びから、いちばん小さい値を O(log n) で返します。まん中と右端を比べて、切れ目のある側へ絞る二分探索の練習です。

幅優先探索 (BFS) とキューで二分木を段ごとに読む

二分木の値を、上の段から順に、段ごとの並びにまとめて返す。待ち行列で近い節から順に見ていく、幅優先の読み方の練習です。

再帰で二分探索木の決まりを確かめる

二分木が二分探索木の決まりを守っているかを返します。親と子だけを比べる落とし穴を避け、各節に入ってよい値の範囲を上から渡していく練習です。

再帰で二分木の 2 つの節にいちばん近い共通の祖先を探す

二分木の中の 2 つの値について、両方を下に持つ節のうち、いちばん深い節の値を返します。左右の部分木から見つけた物を上へ返し、両側から返った所で答えを決める再帰の練習です。

幅優先探索 (BFS) で二分木を右から見たときに見える節を並べる

二分木を右側から眺めたときに見える節の値を、上の段から順に返します。段ごとに読む幅優先探索で、各段のいちばん右の節を拾う練習です。

深さ優先探索で根からの道でいちばん大きい値を持ち回り、二分木のよい節を数える

根からその節までの道に、その節より大きい値が 1 つも無い節を「よい節」と呼び、その数を返します。上から下へ、ここまでの最大値を引数で渡していく深さ優先探索の練習です。

スタックの中順の走査で二分探索木の k 番目に小さい値を探す

二分探索木から、小さい方から数えて k 番目の値を返します。左、自分、右の順に読むと小さい順になることを使い、その読み方を再帰ではなくスタックの繰り返しで書く練習です。

二分探索木の大小で 2 つの節の共通の祖先を探す

二分探索木の 2 つの値について、両方を子孫に持ついちばん深い節 (共通の祖先) の値を返します。2 つの値と節の大小だけで、根から 1 本道で下りられることに気づく練習です。

繰り返しで二分探索木に新しい値を葉として足す

二分探索木に新しい値を足し、足したあとの木を返します。大小で左右へ進んで空いた所を探し、そこへ葉としてつなぐ練習です。

ヒープで k 番目に大きい値を求める

整数の並びから、大きい方から数えて k 番目の値を返します。全部を並べ替えず、大きい方の k 個だけを小さい順のヒープに持ち続ける練習です。

ハッシュとヒープで出てくる回数の多い値を k 個選ぶ

整数の並びから、出てくる回数の多い値を k 個、決めた順で返します。辞書で回数を数え、「いちばん弱い候補」が根に来るヒープに k 個だけ持つ練習です。

ヒープで原点にいちばん近い k 個の点を選ぶ

平面の点の並びから、原点 (0, 0) に近い方の k 個を選んで返します。全部を並べ替えず、近い k 個だけを「いちばん遠い物が根に来るヒープ」に持ち続ける練習です。

ヒープで同じ作業の間を空けて全部を終える最短の時間を求める

同じ種類の作業のあいだに決まった数の休みを挟む決まりで、全部の作業を終えるのに要るいちばん短い時間を数えます。残りの多い作業から先に入れる欲張りを、大きい順のヒープで回す練習です。

トライ木 (Trie) で言葉の頭を調べる仕組みを作る

言葉を足す、言葉がまるごとあるか調べる、ある頭で始まる言葉があるか調べる、の 3 つの操作を持つ仕組みを作る。1 文字ずつ枝分かれする木に言葉をしまう練習です。

幅優先探索 (BFS) でグリッドの島を数える

陸と海の地図から、上下左右でつながった陸のかたまりがいくつあるかを数える。まだ見ていない陸を見つけるたびに、そこから広がる陸を待ち行列で全部塗りつぶします。

幅優先探索 (BFS) で東と西の両方の海へ流れる場所を探す

島の高さの地図から、雨水が東の海にも西の海にも流れていける場所を全部返す。海の側から逆に、高いほうへ登れる所を幅優先で広げ、両方から届いた場所を集めます。

深さ優先探索 (DFS) でグリッドのいちばん大きい島の広さを求める

陸と海のマスが並んだ地図から、上下左右につながった陸のまとまり (島) のうち、いちばん広い島のマスの数を返します。島を見つけたら塗りつぶしながら数える練習です。

盤の端からたどって囲まれた空き地だけを埋める

土と水のマスが並んだ盤で、盤の端につながっていない水のまとまりを土で埋めた盤を返します。囲まれた所を探すのではなく、端から届く水に印を付けて、残りを埋める練習です。

幅優先探索 (BFS) と辞書でつながりのグラフを写し取る

1 つの節から届くグラフを、節を 1 回ずつだけ写して、つながりごと写し取ります。元の節と写した節の対応を辞書に持ち、初めて見た節だけを写して列に並べる練習です。

幅優先探索 (BFS) の色塗りで、つながった 2 人を別の組に分けられるか調べる

人と人のつながりを、どのつながりも 2 つの組をまたぐように 2 組へ分けられるか (二部グラフか) を調べます。隣を反対の色で塗りながらたどり、同じ色どうしがつながっていたら分けられない、と判断する練習です。

プリム法で全部の倉庫を道でつなぐいちばん安い費用を求める

平面に散らばった倉庫を、碁盤の目の道でつないで、どの 2 つも行き来できるようにするいちばん安い費用を求めます。つないだまとまりから最も近い倉庫を 1 つずつ足していく、最小全域木のプリム法の練習です。

幅優先探索 (BFS) でグリッドの最短の道を数える

通れるマスとふさがったマスの地図で、左上から右下まで 8 方向に進むときの最短の道のマスの数を返す。近いマスから順に広げる幅優先で、最初に着いた時の歩数が答えになります。

幅優先探索 (BFS) で知らせが全員に届くまでの分を数える

座席の表で、知らせを持つ人から上下左右の人へ 1 分ずつ知らせが広がるとき、全員に届くまでの分を数えます。始めに知らせを持つ人を全員、同時に列へ入れて段ごとに広げる練習です。

幅優先探索 (BFS) で全部の部屋からいちばん近い出口までの歩数を求める

部屋と出口が並んだ間取りで、どの部屋についても、いちばん近い出口までの歩数を書き込んだ表を返します。全部の出口から同時に広げる幅優先探索で、1 回で全部の歩数を決める練習です。

ダイクストラ法で合図が全部の中継所に届くまでの時間を求める

一方通行の回線でつながった中継所に、1 か所から合図を流したとき、全部の中継所に届くまでの時間を求めます。重みのある最短経路を、ヒープで近い所から確定していくダイクストラ法で解く練習です。

ベルマン・フォード法で乗り継ぎ k 回までのいちばん安い運賃を求める

都市を結ぶ便の運賃の並びから、乗り継ぎを k 回までに抑えて出発地から目的地へ行く、いちばん安い運賃を求めます。使う便の数を 1 本ずつ増やしながら運賃を緩めていく、回数に上限のある最短経路の練習です。

素集合 (Union-Find) でつながった町のまとまりを数える

町どうしが道でつながっているかを表す表から、行き来できる町のまとまりがいくつあるかを数える。町を 1 つずつ同じまとまりへ合わせていく、素集合の練習です。

素集合 (Union-Find) で木に 1 本だけ足された余分な道を見つける

輪の無いつながり (木) に 1 本だけ道が足されて輪ができた道の並びから、外すと木に戻る道を見つけます。道を順につなぎながら、両端がもう同じまとまりにいる道を素集合ですぐ見つける練習です。

トポロジカルソートで全部の講座を受けられるか調べる

「この講座の前にあの講座を終える」という決まりの並びから、全部の講座を受け終えられるかを答える。前提の残り数が 0 の講座から順に待ち行列で取り出す、トポロジカルソートの練習です。

トポロジカルソートとヒープで講座を受ける順を決める

「この講座の前にあの講座を終える」という決まりの並びから、全部の講座を受ける順を 1 つ返す。いま受けられる講座のうち、番号のいちばん小さい物をヒープで取り出していきます。

トポロジカルソートで手持ちの材料から作れる料理を全部見つける

料理ごとに要る材料と、手持ちの材料から、作れる料理を全部見つけます。ほかの料理を材料に使う料理もあるので、「要る物が全部そろった料理から作る」を、残りの数を数えながら列で回すトポロジカルソートの練習です。

並べ替えで重なる区間を 1 つにまとめる

会議室の予約の時間帯の並びから、重なったり接したりする時間帯をまとめて、使われている時間帯の一覧を作る。始まりの順に並べ替えれば、前から 1 回なめるだけでまとめられます。

3 つの組に分けて新しい区間を差し込む

始まりの順に並んだ重ならない予約の並びに、新しい予約を 1 本差し込み、重なる物をまとめた並びを返す。手前、重なる所、後ろの 3 つに分ければ、並べ替えずに前から 1 回なめるだけで済みます。

終わりの順の貪欲で重なりを消す

1 台の機械に入った作業の時間帯の並びから、残りが重ならないように外す本数の最少を求める。終わりの早い順に並べ、残せる物を前から選んでいくと、外す本数が最も少なくなります。

2 本の指で 2 人とも空いている日を求める

2 人それぞれの、日の順に並んだ休みの範囲の一覧から、2 人とも休みの範囲を並べて返す。両方の並びに指を 1 本ずつ置き、先に終わる方の指を進めれば、1 回なめるだけで全部の重なりが拾えます。

始まりと終わりを分けて要る部屋の数を数える

研修の日程の並びから、同じ部屋で日が重ならないように割り当てるときに要る部屋の最少の数を求める。始まりの日と最終日を別々に並べて前から数えれば、同時に開いている研修の最大の数が分かります。

貪欲で最後のマスに着けるかを判定する

すごろくのマスごとに進める歩数の上限が決まっているとき、最初のマスから最後のマスに着けるかを返す。「いままでに届く最も遠いマス」を 1 つ持ち歩き、前から 1 回なめるだけで判定できます。

貪欲で最後のマスまでの最少の跳ぶ回数を求める

すごろくのマスごとに進める歩数の上限が決まっているとき、最後のマスに着くまでの跳ぶ回数の最少を返す。「あと 1 回跳べば届く範囲」を段ごとに広げていけば、前から 1 回なめるだけで数えられます。

貪欲で輪を 1 周できる出発点を求める

輪になった配送の道で、電気自動車が 1 周できる出発の充電所の番号を返す。電池が足りなくなったら、その次の充電所から出発し直すと決めるだけで、前から 1 回なめて答えが出ます。

貪欲で札を連続する数の組に分ける

数の書かれた札の束を、決まった枚数の連続する数の組に全部分けられるかを返す。残っている最も小さい札は必ず組の先頭になるので、小さい順に組を作っていくだけで判定できます。

貪欲で 3 つ組の最大から目標を作る

3 つの数の組の並びからいくつかを選び、位置ごとの最大を取って目標の組を作れるかを返す。目標を 1 か所でも越える組は使えないので捨て、残りの組で目標の 3 つの値がそろうかだけを見れば判定できます。

最後の位置を使って文字列をできるだけ多く切る

文字列を、どの文字も 1 つの切れにしか出ないように、できるだけ多くの切れに分けたときの切れの長さを返す。文字ごとに最後に出る位置を先に調べておけば、前から 1 回なめて切れ目を決められます。

数の幅を持ち歩いて星入りの括弧を判定する

開きかっこ、閉じかっこ、どちらにも空にもなれる星の 3 つの文字だけの文字列が、正しいかっこの並びにできるかを返す。開いたままのかっこの数がとりうる最小と最大の 2 つだけを持てば、前から 1 回なめて判定できます。

バックトラックで並べ方を全部作る

違う数ばかりの並びから、全部の数を 1 回ずつ使った並べ方を残らず作る。1 つ選んでは先へ進み、戻るときに選んだ印を外す、バックトラックの基本の形です。

バックトラックで足すと目標になる組み合わせを全部集める