就職活動インタビュー反省記録 with Yahoo

Yahoo とのインタビューは、明らかに失敗だったとインタビュー中に分かったケースです。というのも、電話インタビューの最中に私のプリペイドの携帯の残高がゼロになり、会話が 8 分も途切れてしまったからです。前回残高を追加したのが夏学期の途中だったので、残高をチェックするのを忘れて、電話インタビューをしてしまいました。これは問答無用でアウトです ;(   だって、interviewer からしてみれば、「おいおい、こっちは貴重な勤務時間を割いてインタビューしてるのに、残高ゼロで会話できませんってどういうことだよ。スキル以前の問題じゃないか」て思いますもんね、普通。

このインタビューに関しては、反省すべき点は火を見るより明らかなので、以降は Yahoo にアプライした経緯やインタビューで聞かれた問題を紹介したいと思います。

私がアプライしたのは、Back End Engineer、Quality Assurance (QA) Engineer のふたつのポジションでした。Salesforce.com に続き、私が Quality Assurance のポジションにアプライをしている理由は「エンジニアは、その会社が作っている製品のことをまず熟知すること。そのためには製品をテストして内部の構造を理解することから始める」ということをいつも念頭に置いているからです。この言葉は実は受け売りで、私が 2006 年に CMU にいたときに Boeing Company の Technical Fellow、John Vu 博士のレクチャーを受け、そのときに学んだ言葉です。もちろん鵜呑みにしているわけではなく、私なりに自分の能力を考慮して、納得した上でそれを受け入れました。これまで実務経験のない私に特に当てはまる言葉だと思っています。

さて、Back End Engineer のポジションでインタビューを受けるよう Yahoo の女性のリクルータから連絡がありました。上記で述べたように、本当は QA のポジションから始めたいとは思いましたが、Back End Engineer もトライしたいポジションだったので、そのまま OK の返事をしました。

Back End Engineer の電話インタビューは全てアルゴリズムとデータ構造絡みでした。全ての問題をコードにしていると、このエントリーが長くなってしまうので、今回は聞かれた問題を覚えている限り列挙することにします。

• 配列、リストについて、以下の操作の実行速度の違い：要素の検索、要素の挿入、要素の削除
• Singly linked list の途中に要素を挿入するコード、途中の要素を削除するコードをそれぞれ読み上げてください
• Singly linked list の途中の要素を削除したいと考えています。ただし、その削除する要素およびそれ以降のノードにしかアクセスできません。その要素をどう削除しますか？そして、あなたの考えたアルゴリズムが機能しないケースがあるとすれば、それはどのようなときですか？
• Binary search のコードを読み上げてください
• Vector について、capacity と size について説明してください
• Vector は capacity いっぱいに要素が格納されると、次の要素の挿入時に capacity が倍になるように実装されているケースが多いです。これはなぜですか？
  
  （プリペイド電話の残高がここでゼロになり、会話ドロップ。インタビュー再開まで8分かかる orz ）
  
  
• Hashtable を実装するとして、そのアウトラインを説明してください
• Hash function の持つべき特性を考えられるだけ挙げてください
• 文字列の中で、重複のない文字のうち、最初に現れる文字を返す関数を設計してください。"abcbbad" であれば、'c'　が返されます。なぜなら、'c' は first non-repeated character だからです。複数のアプローチを考えて、そのトレードオフを考えてください。そのうちひとつのアプローチをコードで書いて、私に読み上げてください

6つめの問題、 capacity いっぱいの時点で要素を挿入する際に vector の capacity を倍にする理由というのは、他のインタビューではあまり聞かれないものでした。これは Introduction to Algorithms （この CLRS 本、Thrid Edition も出ましたね！）の第17章 Amortized Analysis で取り上げられていますので、そちらを見ていただけると詳しい説明が載っています。つまるところ、長い目で見てその操作のコストをコンスタントにするために、一連の操作の途中でコストの高いセットアップをする必要がある。でも、その痛恨の一撃のようなセットアップはたまにしかやって来ないので、それを操作のコストだ、と決めつけるのは too pessimistic だよね、ということです。Amortized Analysis については、私が去年の春にとったアルゴリズムのクラスにも教材がありますし、MIT の OCW でもご覧になれます。



Yahoo からオファーを受けた友人は二人います。二人ともインド人で、一人は QA のポジションで、もう一人は Developer のポジションでした。どちらも、電話インタビューが二回、onsite インタビューが一回。そして、CareerCup の Yahoo の問題を事前に解いていったら、似たような問題を聞かれてしっかり答えられたと言っていました。ただ、QA のポジションでオファーを受けた彼は、最終的には別の会社を選びましたね。 私？インタビューの問題にはきちんと答えましたが、結果は当然アウトですよー。QA のポジションでもインタビューできないかどうか、インタビューの最後に interviewer に聞きましたが、結局スルー ;(
No second chance for a first impression ということでした。