マナティ

世界で闘うプログラミング力を鍛える本

第1回 コーディング面接の最強攻略本!

『世界で闘うプログラミング力を鍛える本』は、"コーディング面接"の攻略本です。本書で取り上げているプログラミングの問題はアップルやグーグルなどの面接で実際に使われた問題で、IT企業からどのような能力を求められるのかがよく分かるものになっています。
本連載では書籍内容、およびコーディング面接について紹介しつつ、問題の内容とその解き方について解説していきます。

9784839960100.jpg

はじめに

『世界で闘うプログラミング力を鍛える本』は、米国のベストセラー書籍“Cracking the Coding Interview”第6版の翻訳書です。Googleなどでエンジニアとして活躍し、700名を超える候補者に対し面接を行ってきたGayle Laakmann McDowellさんによって執筆されました。テクノロジー系企業における採用面接(コーディング面接)の対策本として米国での人気は高く、企業に採用されることを目指す候補者だけでなく、自分がプログラマとしてどの程度の「能力」があり、今後どのようにステップアップしていけばよいのか、そのヒントがたくさん隠されています。

本連載では書籍の紹介を交えつつ、コーディング面接とその解き方について紹介していきたいと思います。

コーディング面接って何?

IT系の企業では、面接内でプログラミングに関する質問時にホワイトボードを用いて実際にコーディングを行う場合があります。

「コーディング面接」という言葉を初めて知った方、聞いたことはあるけれどもどんなものかはよく分からないという方は、実際にコーディング面接を行っている動画をご覧いただくと、その雰囲気がよくわかると思います。

実際の面接風景

コーディング面接を行っている女性が本書の著者:Gayle Laakmann McDowellさんです(クリックするとYouTube動画 http://www.youtube.com/watch?v=2cf9xo1S134 に接続されます)。

面接は対話的に行うものですから、与えられた課題に対してただコードを書けばよいというわけではありません。対話を行いながら、どのような意図で質問されているのかを見極め、どのような前提で設計を行い、自分の設計の良い点・悪い点、改善策等、自分の言葉で説明できなければなりません。

コーディング面接を攻略!

ボリューム満点の面接攻略本

アルゴリズムやデータ構造に関する書籍は、初学者向けのわかりやすいものから高度な内容を扱ったものまで、本当にたくさんあります。単純にプログラミングの勉強をするなら選択肢は非常に多く、自分に合ったものを探せばよいでしょう。

しかしコーディング面接では、プログラミングの専門書に書かれていることをそのまま述べればよいわけではありません。簡単な質問は、単に解法を求めているとは限らないからです。

解法がわかった上で、実装上の工夫・汎用性・最適化に関して面接官と議論することが評価されるかもしれません。難しい問題を与えられ、その解法がわからなかったとしても、アプローチの方法や諦めずに取り組む姿勢を評価されるのかもしれません。

本書ではその点をよく考慮した上で、IT企業のコーディング面接について、主にアルゴリズム・コーディング・設計に焦点を当て、具体的な問題や解答例を多数解説しています。また、本書は面接官・候補者両方の視点で書かれています。著者の豊富な経験を元に書かれたコーディング面接の舞台裏や事例は具体的でわかりやすく、そのボリュームは圧倒的です。

面接で問われるレベルを知る

コーディング面接では質問の意図をうまく読み取ることが重要ですが、具体的にはどのようにすればよいのでしょうか?それが本書に書かれています。「この問題は、ココを評価したい」というポイントを著者が十分理解した上で、最初のアプローチからゴールまでを明確に示しています。

近年はプログラミングコンテストやプログラミング能力を判定するためのオンラインサービスが数多く存在し、学生から社会人まで気軽にプログラミング能力を測定し、学習することができるようになりました。その結果、学習環境としては年々充実している反面、通常の業務ではまず扱わないであろうかなり高度な知識を必要以上に覚えてしまう傾向を無視することができなくなりました。

高度なアルゴリズムを知っていることマイナス評価になることは決してありませんが、大きなプラス評価になるというわけでもありません。もし面接官が「未知の問題に対する取り組み姿勢や能力」を評価したかった場合、「知っている」だけで済んでしまうと評価したい点が評価できません。

もちろんこれは「高度な技術を学ぶな」という意味ではありません。すでによく知っている問題であれば、知っていることを面接官に伝えておく方が、面接が円滑に進んだり印象がよくなったりする場合があるということです。

高度なアルゴリズムについて、その知識を問われているのか、あるいは導出するための手法を問われているのかを把握できていれば、答えるべきことも自然に見えてくるでしょう。

「面接官」へのアドバイスを活用する

本書には面白い特徴があります。それは、面接を受ける側に目を向けた記述がメインであるものの、面接を行う立場の人に向けた記述もあるという点です。面接官にとって注意すべき点は、候補者にとって高評価を得るためのヒントになります。「私は面接官ではないから」と言って読み飛ばしたりせず丁寧に読み込むことで、もう1段ステップアップできるはずです。

バランス感覚をつかむ

先に述べた通り、どのレベルの知識を問われるのかを把握しておくことは重要です。しかしそれだけでは不十分で、問題のレベル以前に自分自身のレベルを知っていなければなりません。多くの場合、今までどのような環境でスキルを磨いてきたか、あるいは個人的な趣向によって、自分自身の知識や技術には多少なりとも偏りがあるはずです。

本書はプログラマとして必要な分野を網羅しています。今の自分がある分野についてどの程度の知識や理解があるのかを確認し、今後のステップアップに向けてビジョンを描くためのヒントが溢れています。

問題に挑戦してみよう!

「コンピュータを使わないプログラミング問題」を試しにやってみましょう。手元にPCがあっても、それを使わずに考えてみてください。ホワイトボードが手元にあることは少ないでしょうから、紙とペンを使ってください。最初からたくさんコードを書く問題も大変ですので、まずは『Chapter 5 - ビット操作』の問5.5から、次のような問題を紹介します。

これをコンピュータを用いずに答えるとしたら、どのように考えればよいでしょうか?この先を読む前に、少し立ち止まって考えてみてください。

最初のアプローチ

最初は具体的な数をいくらか書いてみて、特徴を見つけてみましょう。5と(5-1)、8と(8-1)のような小さな値では少しわかり難いので、大きな値の例を考えてみます。

たとえば593100から1を引くと、593099のように最下位から見て0の桁は繰り下がりが起こり、最初の0でない桁が1少なくなります。

2進数で考えてみる

2進数で表現した場合はどうでしょうか?

sekai_1_01.jpg

10進数の場合と同じように、最下位ビットから続く0はすべて繰り下がりが起こり、はじめて現れる1が0になっています。それより上の桁(青のマーカーで囲んだ部分)は全く変化していません。

ビットの変化があった桁(赤のマーカーで囲んだ部分)のみで n&(n-1) の値を計算すると、その部分は必ず0になっています。ビットが変化した部分のビット積は必ず0になるとすると、(n&(n-1))==0 が真になる場合はビットが変化していない部分が0である必要があります。

このような値は、ビットの1か所だけが1で、それ以外のビットはすべて0になっている数です。1か所のビットだけ1である数は、10進数で表すと2の累乗数ということになります。

答え合わせ

結論が出ましたが、今は面接試験を受けているわけではありませんので、自分で答え合わせをして終わりにしましょう。たとえばRubyで条件を満たすnを列挙するワンライナーを書けば、次のようになります。

$ ruby -e '1.upto(100){|n|puts n if (n&(n-1))==0}'
1
2
4
8
16
32
64

1から100までの範囲で調べてみたところ、確かに2の累乗数になっていますね。

いかがでしたか?

難しい問題ではありませんが、コンピュータが使えないと結構大変だったのではないでしょうか?分からないことを調べたり、コードを少しずつ書いていろいろと試しながら考えることはできませんから、理解が不十分であったり知識があいまいであったりすると、ちょっとしたことでもやっているうちに自信がなくなってきてしまいます。次回は実際にコードを書く問題を紹介しますので、実際に面接を受けているつもりで挑戦してみてください!

著者プロフィール

岡田佑一(著者)
「世界で闘うプログラミング力を鍛える本」翻訳者。小さな学習塾を営む。子どもたちとの日常から生まれたアイデアを元にプログラミング問題を多数作成し、解説記事等の執筆活動も行っている。著書に『ショートコーディング 職人達の技法』、執筆協力に『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 』(以上、マイナビ出版)。