> For the complete documentation index, see [llms.txt](https://y-meguro.gitbook.io/reading-record/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://y-meguro.gitbook.io/reading-record/algorithms/cracking_the_coding_interview.md). # 世界で戦うプログラミング力を鍛える本 ## 概要 ### 本 * [世界で戦うプログラミング力を鍛える本](https://amzn.to/2FFq2Hf) * 参考: [CRACKING the CODING INTERVIEW](http://www.crackingthecodinginterview.com/) ### かかった時間 * xxx 時間 ### 進め方 * xxx ### 感想 * xxx ## 読書メモ ### 1: 面接の流れ * たいていの場合、面接担当者は次のような軸に基づいて評価を下している * 分析スキル * 問題を解く際、多くの手助けが必要だったか？導かれたソリューションはどこまで最適なものだったか？ソリューションが出てくるまで、どのくらいの時間が必要だったか？新たなソリューションをデザイン、あるいは設計する必要があった場合、問題を適切に構造化して、複数の選択肢のトレードオフを検討したか？ * コーディングスキル * 考えたアルゴリズムを適切なプログラムに変換できたか？コードが整理され、見やすくなっているか？潜在的なエラーに対処しているか？コーディングのスタイルは優れているか？ * 技術知識 / コンピュータサイエンスの基礎知識 * コンピュータサイエンスや関連技術について、基礎的な知識をしっかりと持っているか？ * 経験 * これまで技術的な問題について、適切な決定を下してきたか？難易度が高く、面白い内容のプロジェクトを経験してきたか？プロジェクトを後押ししたり、先導したりするなど、重要な役割を演じてきたか？ * 企業文化との相性 / コミュニケーションスキル * 性格や価値観が、自社や配属予定のチームとあっているか？面接担当者と適切なコミュニケーションができたか？ ### 2: 面接試験の舞台裏 * Microsoft の面接 * リクルータとは良い関係を持つようにしておきましょう。もし、最初の面接でつまづいたとしても、リクルータが再面接できるように動いてくれたり、大きな味方になるかもしれません * 必ずしておく準備 * 「なぜマイクロソフトで働きたいのですか？」 * Amazon の面接 * 必ずしておく準備 * スケーラビリティに関する質問の準備(9 章「システムデザインとスケーラビリティ」をよく見ておくこと) * オブジェクト指向に関する質問も多い * Google の面接 * 必ずしておく準備 * 大規模なシステムの設計を重視する(9 章「システムデザインとスケーラビリティ」をよく見ておくこと) * 経験よりも分析(アルゴリズム)スキルを重視している * Apple の面接 * 必ずしておく準備 * もしどんな開発チームが面接を担当するのか知っていれば、その製品についてよく調べておく * どの部分が好きか、どの部分を改良したいのか、できるだけ具体的に述べることでアピールできる * Facebook の面接 * 面接の役割が 3 つに分かれている * 行動 * コーディングとアルゴリズム * デザイン / アーキテクチャ * 必ずしておく準備 * 素早くものを作り出すことが好きであることをアピールすると良い ### 3: 特殊な状況 * 職歴の長い候補者 * システム設計とアーキテクチャについても聞かれる * 「これまでに直面した最も困難なバグは何でしたか?」のような質問も聞かれる * 開発リーダー / マネージャー * 以下の能力についての質問に対する準備が必要 * チームワーク / リーダーシップ * 優先順位づけ * コミュニケーション * 「仕事を成し遂げる」 * 面接官に向けたアドバイス * 本書で紹介している質問をそのまま尋ねることはしない * 難易度が中から高の問題を出す * 複数のハードルがある問題を探す * 難しい知識を問うのではなく、難しい問題を問うこと * 「脅かすような」問題は出さない * ポジティブな態度で接する * 行動については深く探る * 候補者のコーチをする * 候補者が黙りたければ、黙ることを許すように * 「モード」を理解する - サニティテスト、クオリティ、スペシャリスト、プロキシ * サニティチェック(Sanity Check) * 問題解決における、最低限のスキルを評価するための質問を行う * クオリティチェック * より高度な問題で、候補者には本気を出して頭をひねることが求められる * スペシャリスト問題 * 特定のトピックに関する知識について質問する。スペシャリストを採用する際に使う * プロキシ知識 * スペシャリストのレベルではないものの、これから採用する候補者にしっておいてほしい知識を問う質問をする ### 4: 面接の前に * 良い経験を得る * 履歴書が素晴らしいものでなければ、面接のチャンスも得られません * 履歴書の書き方 * 適切な履歴書の長さ * 経験が 10 年未満なら 1 ページに収めることを強くおすすめする * 職歴 * 携わってきた職歴のすべてを記入する必要はない * 目立つ箇条書きにする * 「Y を実装することで X ができて、その結果 Z になった」という書き方にする * プロジェクト * 経験の豊富さをアピールするには、履歴書にプロジェクトでの開発項目を設けるのが良い * プログラミング言語とソフトウェア * ソフトウェア * リストに載せるものは、どれが応募している企業に対してアピールできるものか判断して載せる * 言語 * 経験レベルを併記して載せると良い * 「〜のエキスパート」や「〜が堪能」など。経験年数はあまり適切な指標ではない * 英語圏でない人や留学生 * 企業によっては、タイプミスがあるというだけで履歴書をはねられてしまうこともある。1 人くらいはネイティブの人に校正してもらうと良い * 米国企業の場合、年齢・婚姻状態・国籍は書かないほうがよい * (潜在的な)悪いイメージに注意すること * プログラミング言語の経験にフォーカスしすぎている * 1 つか 2 つのプログラミング言語しか理解していない * p34 に面接の準備表あり ### 5: 行動に関する質問 * 3 つ程度のプロジェクトで以下を考えておくと良い * 苦労したこと * 失敗 * 楽しんだこと * リーダーシップ * 衝突 * やり方を変えてみたこと * あなたの弱点は何ですか？ * 正直に弱点を伝え、その弱点をどう克服しようとしているかも伝える * 面接官に対してどんな質問をすべきですか？ * 質問には 3 つの種類が考えられる * 純粋な質問 * 洞察力を示す質問 * 情熱を示す質問 * 技術的プロジェクトについて整理する * 選択するプロジェクトは以下の条件に合致しているものがいい * 困難な課題を乗り越えたものであること * あなたが中心的な役割を演じたものであること * 技術的な側面について、深く語れるものであること * 行動に関する質問への対応 * 具体的に、偉そうなのはダメ * 詳細を制限する(ポイントだけを話す) * チームではなく、自分自身に焦点を当てる * 構造化された答え * 要点から入る * S.A.R.(Situation, Action, Result) 手法 * 概要からスタートし、自分が取った行動の説明を行い、最後に結果を述べる * 自分自身の行動を以下の観点から整理しておくとよい * 要点 * 状況 * 行動 * 結果 * それにどのような意味があるか * 「では、あなた自身のことについて聞かせてください…」 * 多くの面接官は、自己紹介やレジュメの説明から面接をはじめる。第一印象を左右するので、上手く行いたい * 構造 * 一般的に有効なやり方は、時系列に沿って説明するというもの * まず現在の職について説明し、最後に仕事外での関連事項や趣味を説明する * 趣味について語るのが有効な場合 * 非常にユニークな場合 * 技術的な趣味の場合 * 自分の性質が望ましいものであることを示す趣味の場合 * 自分の成功をちりばめる ### 6: ビッグ・オー記法(Big O) * 償却計算量 * これを用いると、時々起こる最悪ケースについて記述できる * 例: 配列の挿入 * 配列がいっぱいになった時、要素数が N なら新しい要素の挿入には O(N) の時間がかかる。これはサイズが 2N の新しい配列を作り、そこへ N 個の要素をコピーするから * しかし、これはめったに起こるものではなく、ほとんどの場合、要素の追加は O(1) で済む * 解き方 * 要素を挿入する場合、配列のサイズが 2 のべき乗になる時に配列のサイズを 2 倍にする。したがって X 個の要素を追加すると、配列のサイズを 1, 2, 4, ..., X と 2 倍にしていく * 配列のサイズを 2 倍にするたびに、それぞれ 1, 2, 4, ..., X 回のコピーを行う * 1 + 2 + ... + X = 2X なので、X 個の挿入には O(2X) の時間を要し、挿入ごとの償却計算量は O(1) になる ### 7: 技術的な質問 * どうやって準備するか * 自分で問題を解く * コードを紙に書く * テストも紙の上で書く * 紙に書いたコードをそのままコンピュータに入力してみる * おそらくたくさんミスをするが、どのようなミスをするかリストアップして確認する * 解答フローチャート(p74) * 聞く * 例 * ブルートフォース * 最適化 * 見直し * 考え方を詳細に見直す * 実装 * テスト * 何が望まれるのか * 注意深く聞く * 問題についてはっきりしない部分は質問する * 問題固有の情報はしっかりと記録しておく * 例を描いてみる * 具体的に / 十分な大きさで / 特殊なケースにならないように * ブルートフォースで記述する * BUD で最適化 * Bottlenecks(ボトルネック) * Unnecessary Work(不必要な作業) * Duplicated Work(重複する作業) * 最適化する * 見直しする * 初期の段階で可能な限り「完璧」に近いコードになっていることを確認しておく * 実装する * 美しいコードを書く * モジュール化されたコード * エラーチェックができている * 必要に応じてクラス / 構造体を使っている * いい変数名を使っている * リファクタできる部分が見つかったら、面接官にそれを説明し、それに時間をかける価値があるか判断する * テストする * 大きなテストデータを用いる代わりに以下のアプローチを試す * コンセプトテストを始める * コードの各行を読み、それらがどのように動くか分析する * レビュアーに対して、コードの内容を説明するようにやる * 怪しいコードを再度チェックする * ホットスポットに注意する * 小さなテストケースを使う * 特殊なテストケースを使う * バグを発見した時、自分が最初に思った修正だけで済ませず、なぜそのバグが発生したか注意深く分析する * 最適化と解答テクニック * 1: BUD を探そう * 2: DIY の精神で * わかりやすく大きい例を用いて、特定の例に対して直感的に(手動で)解いてみる * それから自分がどのように解いたか考える(思考過程を逆算する) * 3: 単純化と一般化 * 4: 初期状態からの積み上げ * 5: データ構造総当り * 単純にデータ構造の一覧を順に調べて、うまくいくものがないかそれぞれを適用していく * BCR: Best Conceivable Runtime * 問題の解法として考えられる最善の実行時間を意識する * 時間計算量を BCR にできないか考える、あわせて空間計算量をできるだけ減らせないか(O(1) にできないか)考える * 問題を以前に聞いたことがある時 * それを面接官に伝える。誠実であるという高評価を得られる * 良い、きれいなコードとは * 正確である * 効率的である * シンプルである * 読みやすい * 保守しやすい * データ構造はどんどん使おう * 独自のデータ構造を設計するのも OK * 適切なコードの再利用 * モジュール化 * 柔軟かつ堅牢であること * エラーチェック * あきらめないで! ### 8: オファーとその後 * オファーと不採用の取り扱い * オファーを断る場合、不快感を与えず議論の余地がない理由を話すようにする * 不採用の場合、リクルータからのフィードバックを求めることもできる * オファーの評価 * 給与以外の要素もちゃんと見ること * 契約ボーナス、転勤費用などの特典 * 生活費の違い * 年間ボーナス * ストックオプションと補助金 * キャリアアップ * 会社の安定性 * 自分の幸せ * 製品 * マネージャーとチームメイト * 社風 * 時間 * 交渉のヒント * とにかくやってみる * 現実的な代替案を持つ * 具体的な「お願い」をする * 余分に要求する * 給与より上を考える * ベストな媒体で * 仕事をしていく上で * 時間的な計画を設定する * 強力な関係性を構築する * 自分の望むものを求める * 面接対策を続ける ### 9: 問題 * 自分の解答は [y-meguro/competitive-programming/cracking-the-coding-interview](https://github.com/y-meguro/competitive-programming/tree/master/cracking-the-coding-interview) に記載