プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問

情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、AmazonMicrosoftGoogleのような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人がプログラミングに関してどのような質問をされるか見当もつきません。

この記事では、新卒生からプログラマになって1〜2年までの経験値が異なる人たち向けに、それぞれのプログラミングの面接でよく聞かれる質問をいくつか紹介していきます。

コーディングの面接では、主にデータ構造とアルゴリズムに基づいた質問がされますが、一時変数を使わずにどのように2つの整数をスワップするのか、というような論理的な質問もされるでしょう。

コーディングの面接で聞かれる質問は、トピックの分野ごとに分けると役立ちます。私が知る限り、ほとんどの面接でトピックになる分野は、配列、連結リスト、文字列、二分木はもちろんのこと、アルゴリズム(例えば文字列のアルゴリズム、クイックソート基数ソートのようなソートアルゴリズムや他の種類のアルゴリズム)も含まれます。それらの内容について、これから説明していきます。

実際のプログラミングの採用面接で、これから紹介するコーディングやデータ構造やアルゴリズムの質問をされるかは保証しませんが、どのような種類の質問をされるか十分に想定できるようになるはずです。

これから紹介する質問を一通り解いてみることで、電話の面接や対面の面接に自信を持って臨めるようになるでしょう。

ちなみに、必須となるデータ構造やアルゴリズムに関して十分な知識がない、あるいは長期間触れていない場合は、これらの質問に対処しようとしても意味がありません。

そのような場合は、「Robert Horvickによるアルゴリズムとデータ構造 パート1と2」のような素晴らしいコースを受けて、データ構造とアルゴリズムの技術を学び直すべきです。

アルゴリズムとデータ構造 パート1
日常的なアプリケーションで使用されるコアデータ構造とアルゴリズムを考える

アルゴリズムとデータ構造 パート2
日常的なアプリケーションで使用される高度なデータ構造とアルゴリズムを考える

面接で聞かれるアルゴリズムとコーディングに関する質問トップ50

難しい話は抜きにして、プログラミングの採用面接で頻繁に聞かれるコーディングの質問を以下の通り挙げていきます。

1. 面接で聞かれる配列のコーディングに関する質問

配列は、連続したメモリのロケーションに要素をストアする最も基本的なデータ構造です。そして面接官にとってもお気に入りの質問トピックの1つであるため、どのようなコーディングの面接でも、配列の反転や配列のソート、そして配列での要素の検索に関してなど、多くの質問をしてくるでしょう。

配列のデータ構造の重要な利点は、インデックスさえ知っていれば高速でO(1)の検索ができることですが、既存の配列のサイズは変更できないため、配列から要素の追加と削除を行う場合は遅くなります。

より短い配列や長い配列を作るためには新しい配列を作り、すべての要素を古い配列から新しい配列にコピーする必要があります。

配列に関する質問に答えるためには、配列データ構造についてだけでなく、ループや反復や根本的なオペレータなどの基本的なプログラミング構造を熟知することが重要です。

1. 1から100までの与えられた整数の配列の中から足りない数字を探すにはどうすればよいですか? (解答)
2. 与えられた整数の配列において重複した数字を探すにはどうすればよいですか? (解答)
3. ソートされていない整数の配列から最大値と最小値を探すにはどうすればよいですか? (解答)
4. 合計すると与えられた数字と同じになる整数の配列のすべての組み合わせを探すにはどうすればよいですか? (解答)
5. 配列に複数の重複がある場合、配列内の重複した数字を探すにはどうすればよいですか? (解答)
6. Javaにおいて、与えられた配列から重複を削除するにはどうすればよいですか? (解答)
7. クイックソートのアルゴリズムを使用する場合、整数の配列をソートするにはどうすればよいですか? (解答)
8. 配置された配列から、重複を削除するにはどうすればよいですか? (解答
9. Javaにおいて、配置された配列を反転するにはどうすればよいですか? (解答)
10. ライブラリを全く使わないで配列から重複を削除するにはどうすればよいですか? (解答)

以上の質問に取り組めば、問題解決のスキルが伸びるだけでなく、配列データ構造に関する知識も増えるでしょう。

配列に基づく、より上級者向けの質問を知りたい場合は、「コーディング面接のブート・キャンプ:アルゴリズムとデータ構造」をご覧ください。これはアルゴリズムの短期集中トレーニング型コースで、特にGoogle、Microsoft、Apple、Facebookなどのテックジャイアントの採用面接の準備をするために考案されたものです。

注釈:
上部:Fibonacci Series→フィボナッチ数列
A series of numbers in which each number(Fibonacci number)is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc.
→各数字(フィボナッチの数字)の数列は2つ前の項と1つ前の項を足し合わせていくことでできる数列のことです。最も分かりやすい数列が1、1、2、3、5、8と続きます。
下部:Recursive solution: 再帰的解法

上述した10の質問では物足りずもっと練習したい場合は、配列に関する30の質問のリストを参考にしてください。

2. 面接で聞かれる連結リストのプログラミングに関する質問

連結リストは配列のデータ構造を補足するもう1つの共通したデータ構造です。配列と似ていますが線形のデータ構造でもあり直線状に要素をストアします。

配列と異なっているのは、隣接したロケーションに要素をストアするのではなく、ノードを使ってつながっているメモリ全体に散らばせる点です。

連結リストは、ストアされた値と次のノードのアドレスを含んでいるノードのリストにすぎません。

そういった構造上の理由から、配列を作る代わりにリンクを変更するだけでいいので連結リストで要素を追加及び削除するのは容易ですが、検索に関しては困難で要素を見つけるのに1つの連結リストでO(n)時間かかることが頻繁にあります。

こちらの記事では、配列と連結リストのデータ構造の違いについて、さらに詳しい情報を紹介しています。

連結リストには様々な種類があります。片方向(前方か後方)のものを片方向連結リスト、双方向(前方と後方)のものを双方向連結リスト、そして最後に円形になっているものを循環リストと呼びます。

連結リストは再帰的データ構造のため、連結リストに関する質問に答えるためには再帰に精通している必要があります。

連結リストから1つのノードを取った場合でも、残っているデータ構造は連結リストのままです。そのため、多くの連結リストの問題は反復よりも単純に解決できます。

ここで、連結リストに関する最も一般的でよくある質問とその答えを紹介します。

1. 1つのパスの中で片方向連結リストの真ん中の要素を探すにはどうすればよいですか? (解答
2. 与えられた連結リストがcycleを含んでいた場合、どのようにして確認しますか? cycleの最初のノードを特定するにはどうすればよいですか? (解答
3. 連結リストを反転するにはどうすればよいですか? (解答
4. 再帰を使わずに片方向連結リストを反転するにはどうすればよいですか? (解答
5. ソートされていない連結リストにおいて、重複したノードを排除するにはどうすればよいですか? (解答
6. 片方向連結リストの長さを調べるにはどうすればよいですか? (解答
7. 片方向連結リストにおいて、最後から3番目のノードを探すにはどうすればよいですか? (解答
8. スタックを使用して、2つの連結リストの合計を出すにはどうすればよいですか? (解答

上記の質問に取り組むことで、問題解決のスキルが伸びるだけでなく、連結リストのデータ構造についての知識も増えるでしょう。

連結リストのコーディングに関する上記の質問に答えるのが難しいようでしたら、「データ構造とアルゴリズム:JAVAで深く掘り下げる」コースを受けて、データ構造とアルゴリズムに関する技術を学び直すことをお勧めします。

もっと練習用の質問が必要であれば、面接で聞かれる30の連結リストに関する質問のリストもご確認いただけます。

3. 面接で聞かれる文字列コーディングに関する質問

文字列は、配列や連結リストのデータ構造と同じように、プログラミング系の採用面接で人気のあるトピックです。私が参加したコーディングの面接で、文字列に基づく質問がなかったことは一度もありません。

文字列のいい点は、文字列は文字の配列にすぎないので、配列を知っていれば文字列に基づく質問に簡単に対処できることです。

つまり、配列に基づくコーディングの質問に対処することで習得した技術は全て、文字列のプログラミングに関する質問にも応用できます。

以下に挙げるのは、プログラミングの採用面接で聞かれることが多い文字列コーディングに関する質問リストです。

1. 文字列から重複する文字を表示するにはどうすればよいですか?(解答
2. 2つの文字列が相互にアナグラムであるかどうかを確認するにはどうすればよいですか?(解答
3. 文字列から繰り返されない最初の文字を表示するにはどうすればよいですか?(解答
4. 与えられた文字列を再帰を使って反転するにはどうすればよいですか?(解答
5. 文字列に数字しか含まれていないかどうかを確認するにはどうすればよいですか?(解答
6. 文字列の中で重複する文字を探すにはどうすればよいですか?(解答
7. 与えられた文字列の中の母音と子音の数を数えるにはどうすればよいですか?(解答
8. 文字列の中の特定の文字の出現回数を数えるにはどうすればよいですか?(解答
9. 文字列のすべての順列を見つけるにはどうすればよいですか?(解答
10. ライブラリメソッドを何も使わずに、与えられた文の中で単語を反転させるにはどうすればよいですか?(解答
11. 2つの文字列が相互に順序が回転しているかどうかを確認するにはどうすればよいですか?(解答
12. 与えられた文字列が回文かどうかを確認するにはどうすればよいですか?(解答

これらの質問は、データ構造として、文字列の知識を深める助けになります。何もヒントを得ずに、ここに並べた全ての質問に解答できるなら面接は怖くありません。

もっと上級者用の質問が必要であれば、アルゴリズムに関する超難問が集められた『アルゴリズム設計マニュアル(Steven S Skiena著)』の問題を解くことをお勧めします。

更に練習したい場合は、こちらの20の文字列コーディングに関する質問のリストをご確認ください。

4. 面接で聞かれる二分木コーディングに関する質問

ここまで線形のデータ構造のみを説明してきましたが、実際の情報を全て線形で示すことはできません。そこで助けてくれるのが木構造というデータ構造です。

木構造は、階層的にデータを格納できるデータ構造です。各ノードが子ノードを最大2つしか持たない構造はニ分木といった具合に、どのようにデータを格納するかによって木構造の種類が変わります。

ニ分木は、近い関係にある二分探索木とともに最も人気のある木構造の1つです。そのため、どのように走査するか、どのようにノードを数えるか、どのように深さを知るか、どのように平衡木かどうかを確認するかなど、ニ分木に基づく質問は多いでしょう。

ニ分木の質問に対処するために大切なことは、ニ分木のサイズや深さはどれほどか、葉とは何か、ノードとは何かといった理論に関する深い知識を有していて、行きがけ順、帰りがけ順、通りがけ順など、走査のアルゴリズムに関しても理解していることです。

以下に挙げるのは、ソフトウェアエンジニアや開発者の採用面接で人気の、ニ分木に基づくコーディングの質問リストです。

1. 二分探索木を実装するにはどうすればよいですか?(解答
2. 与えられた二分木で行きがけ順の走査を行うにはどうすればよいですか?(解答
3. 再帰を使わずに行きがけ順で、与えられた二分木の走査を行うにはどうすればよいですか?(解答
4. 与えられた二分木で通りがけ順の走査を行うにはどうすればよいですか?(解答
5. 再帰を使わずに通りがけ順で、与えられた二分木の全てのノードを表示するにはどうすればよいですか?(解答
6. 帰りがけ順の走査のアルゴリズムを実装するにはどうすればよいですか?(解答
7. 再帰を使わずに帰りがけ順で、二分木の走査を行うにはどうすればよいですか?(解答
8. 二分探索木の全ての葉を表示するにはどうすればよいですか?(解答
9. 与えられた二分木の葉のノードの数を数えるにはどうすればよいですか?(解答
10. 与えられた配列で二分探索を行うにはどうすればよいですか?(解答

ニ分木のコーディングに関する理解が不十分だと感じ、上記の質問に自力で答えられない場合は、「0から1へ:JAVAにおけるデータ構造とアルゴリズム」など、データ構造とアルゴリズムに関する優良なコースで学び直すことをお勧めします。

他にもお勧めの学習方法を知りたい場合は、こちらで、手始めに丁度いいデータ構造とアルゴリズムに関する本コースのリストをご紹介しています。

5. 面接で聞かれるその他のコーディングに関する質問

プログラミング系のほとんどの採用面接では、データ構造に基づく質問とは別に、アルゴリズム、設計、ビット操作、論理に基づく一般的な内容についても聞かれます。本セクションでは、これらについて説明します。

これらの概念に関する質問は実際の面接で答えるのが難しくなる場合があるので、練習を重ねることが大切です。事前に練習しておけば、その分野に詳しくなるだけでなく、より大きな自信を持って面接官に答えを説明できるようになります。

1. バブルソートのアルゴリズムを実装するにはどうすればよいですか?(解答
2. 反復のクイックソートのアルゴリズムを実装するにはどうすればよいですか?(解答
3. 挿入ソートのアルゴリズムを実装するにはどうすればよいですか?(解答
4. マージソートのアルゴリズムを実装するにはどうすればよいですか?(解答
5. バケットソートのアルゴリズムを実装するにはどうすればよいですか?(解答
6. 分布数え上げソートのアルゴリズムを実装するにはどうすればよいですか?(解答
7. 基数ソートのアルゴリズムを実装するにはどうすればよいですか?(解答
8. 第3の変数を使わずに2つの数字を交換するにはどうすればよいですか?(解答
9. 2つ矩形が相互に重なっているかどうかを確認するにはどうすればよいですか?(解答
10. 自動販売機を設計するにはどうすればよいですか?(解答

コーディングに関する質問がもっと必要であれば、189以上のプログラミングに関する質問と解答が書かれた『コードの面接をクラッキングするGayle Laakmann McDowell著)』のような本が助けになります。プログラミングの採用面接について短期間で準備ができる良本です。

ところで、練習で多くの質問に答えるほど万全の準備が整っていきます。ですから、50の質問では足りない、もっと必要だと思うのであれば、電話面接のためのプログラミングに関する50の質問を追加でチェックし、完璧な準備を目指して、こちらの書籍コースを確認してください。

これでコーディングの面接の準備が整いました

上述したのはデータ構造とアルゴリズム以外で最も一般的な質問なので、面接の時に大いに役に立つでしょう。

私のブログでは、このような質問をたくさん共有していますので、本当に興味があれば、いつでも見に来て調べることができます。

一般的なコーディング、データ構造、アルゴリズムの質問は、採用面接で良い結果を出すために、大小に関わらず全ての企業、全てのレベルのプログラミングの職種で知っておくべきことです。

2018年にプログラミングやソフトウェア開発の仕事を探しているなら、このコーディングに関する質問リストから準備を始めてもいいでしょう。

このリストは準備に適したトピックを提供していますし、あなたの強みと弱みを見つける準備にも役立ちます。

データ構造とアルゴリズムついての深い知識はコーディングの面接を成功させるために重要ですし、最も注意を向けなければいけません。

更なる学習
データ構造とアルゴリズム:JAVAで深く掘り下げる
技術的なプログラミング/コーディングの採用面接に向けて準備するための10冊
全てのプログラマーが読むべきアルゴリズムに関する10冊
JAVA開発者のためのデータ構造とアルゴリズムに関するトップ5冊
0から1へ:JAVAにおけるデータ構造とアルゴリズム
データ構造とアルゴリズム解析 – 採用面接

結びの言葉

最後まで読んでくださり、ありがとうございます。プログラミングの面接がうまくいくよう願っています。確かに簡単ではありませんが、本稿でご紹介したロードマップとガイドに従えば、DevOpsのエンジニアに1歩近づきます。

もし本稿を気に入って頂けたら、友人や同僚に共有してください。Twitterでjavinpaulをフォローすることもお忘れなく!

追記 – 無料のリソースが必要でしたら、データ構造とアルゴリズムの無料コースリストをチェックして準備に役立ててください。