コーディングインタビュー対策を始めよう

はじめに

今、転職したいなぁと考えていますが、コーディングインタビューは受けたことがありません。
外資系の会社に行くためには、コーディングインタビューが必須だということで、
コーディングインタビューについて調べてみることにしました。

コーディングインタビューの対策

コーディングインタビューを受けたことがないので、以下の方の記事を読み、備えることにします。

• コーディングインタビューの対策とその意義 (1/2)
• コーディングインタビューの対策とその意義 (2/2)

コーディングインタビューの対策とその意義 (1/2)で学んだこと

この記事では以下の２つに着目しています。

1. 受ける前に知っていると良い知識
2. インタビュー中の思考過程

文中でみんなのデータ構造についての記載があるため、読んでおくことにします。

• ホワイトボード上にプログラムを書く or オンライン上の共有エディで書く
• 効率的な解き方(Order)が求められる
• 競技プログラミングと似ているが、解き方をインタビュアーに説明する必要があるし、的確な質問をする必要もある。
• プログラムを書いた後で適切な入力例を用いて動くことを説明する必要もある

データ構造について

• Deque(Double-ended Queue): FIFO(queue)/FILO(stack)
• Priority Queue
• Binary Heap
• Hash Table
• Self-balancing Binary Search Tree
  • Hash Table には劣るが柔軟性がある
• Prefix Tree/Tri Tree
• 注意点: ヒープからの削除はO(logn)であり、O(1)ではない。

データ構造自体は基本を抑えておけば問題ない。
むしろ、コーディングインタビューにおける難しさは、
そのデータ構造の上で動くアルゴリズムの方にあります。

コーディングインタビューに必要なアルゴリズムの知識

連結リストに対しては、細かな技法がものを言います。例えば...

• リストを反転させる方法
  • 前の要素と次の要素をprev/nextとして、一時変数に保持する
• 場合分けを減らす方法
  • dummyノードをheadの前に付ける
• リストの真ん中の要素を効率的に見つける方法
  • 2コずつ要素を飛ぶfast,1コずつ要素を飛ぶslowを定義する
  • fastが動けなくなるまで前進する

あるいは、Binary Search における2つの繰り返し変数low/highの管理方法があります。
Binary Search は、nコの数値の列がソートされていることを利用して、O(log_2 n)の時間で目的の値を探します。
このときに実務的な問題に答える必要があります。

• ループする条件: while low < high ? while low <= high ?
• 変数名: low/high ? or ok/ng ?
• mid の更新: low + (high - low) / 2 の後に繰り上げ？繰り下げ？
  • 更新タイミング1: low = mid ? low = mid + 1 ?
  • 更新タイミング2: high = mid ? high = mid + 1 ?
• ループの動く条件: 要素数0-2でも大丈夫?
• whileループが必ず終了する理由について

重要なのは、自分の方法を提示して、なぜその方法が適切なのかを説明できることです。
そして、再起や基本的なパターンが深く身についた習慣となるまで訓練することが必要です。

また、例題としてLeetCodeのコードが紹介されています。
コーディングインタビュー用に登録しようかな。

コーディングインタビューの対策とその意義 (2/2)で学んだこと

この記事では、コーディングインタビュー当日の思考過程について学びます。

コーディングインタビューでは必ず以前に見たことのない問題を提示されます。
このような問題を解くためには以下の２つが必要となります。
How To Get Un-Stuck During a Tricky Coding Interview Problemを読んでおくこと)

1. 質の高い思考力
2. コミュニケーション能力

そのためには、以下のような考え方をする必要があります。

• 入力例・出力例の「動き」を分解します
• 入力例・出力例のケースをいろいろ考えてみる
  • 要素の重複したら？
  • 配列の大きさが数万だったら？
  • rootノードしかない？rootノードもない？
  • modの結果に何か意味があるか？
  • etc.
• データ構造間の関係のメンタルマップを作成する
  • Deque を使うと解ける？
  • Priority Queue を使うと解ける？
  • Hash Table を使うと解ける？
  • Binary Tree を使うと解ける？
• アルゴリズムを頭の中で試してみる
  • greedy では？
  • divide and conquer では？問題サイズを半分に減らせないか？
• 制約を緩める、前提を増やす
  • Binary search tree で探す要素が必ず存在する、重複がないと仮定する
  • 入力が事前にソートされている
• 自分の発想に対する面接官の言動に注意する
  • いろいろ発言して面接官の言動に注意する

第4回　海外で働くエンジニアは皆読んでいる"Cracking the Coding Interview"を読むと、
世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法 Kindle版が良いらしいので、読んでおくことにします。

How To Get Un-Stuck During a Tricky Coding Interview Problem

How To Get Un-Stuck During a Tricky Coding Interview Problemでは、
コーディングインタビューで、ホワイトボードの前で固まってしまっときの対処方法について紹介してくれています。

1. リラックスする
   • 固まってしまうのも想定内と思っておきましょう。
   • なぜなら、インタビュアーはあなたが知らない問題にどのように取り組むかを見たいのです。
   • 固まってしまうのは実力がないからではありません。
2. 手で問題を解く
   • 入力サンプルを実際に手で書きます。
   • それからその入力サンプルで問題を解いていきます。
   • 問題を解くステップに注意して、コードに落とします。
3. データ構造を放り込む
   • 問題を解くために必要なデータ構造を見つけ適用します。
   • どのデータ構造が適切なわからない場合は、いろんなデータ構造を当てはめてみます
   • Queues/Stacks/Arrays/Hash Tables/Hash Maps/Linked Lists/Trees/Graphs
4. 問題を解きほぐします
   • 提示された課題は、シンプルなものをひねっています。
   • そこで、一旦シンプルなものに落とし込み、そこから課題に迫っていきましょう。
5. 練習しましょう
   • 日頃から練習しておきましょう。コーディングインタビューも練習すれば上達します。

コーディングインタビューの例題はInterview Cake - All Questionsに載っていますので、練習しましょう。

まとめ

とにもかくにもコーディングインタビューには、
事前によく練習しておくことが必要だと分かりました。

とりあえずのところ、以下をやっていこうと考えています。

1. 世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法 Kindle版を読む。
2. データ構造についてみんなのデータ構造を読みます。
3. アルゴリズムはセジウィック:アルゴリズムC 第1~4部 ―基礎・データ構造・整列・探索― (日本語) 単行本 –で勉強でしょうか...(高いし、ページ数が多いのでへこたれそうですが...薄めの本があったらそちらにしよう...)
4. LeetCodeで練習する。

あと、こちらの方の記事(アメリカのグーグル本社に就職するまで)がとても良いと思うので、真似しようと思います。
また、良いエンジニアを採用するための方法論も良いと思うので対策として取り入れようと思います。

やることいっぱいですね。