CRACKING THE CODING INTERVIEW メモ

モチベーション

この本👇

をやっているんだけど、やる中で覚えておきたいことなどが出てきたのでメモしていく。

メモ

Chapter 1 配列と文字列

• 1.1
  • 文字列が与えられる、という条件が来たら、ASCIIかUnicodeかを面接官に確認しておく(ASCIIなら128種しかない)
  • 与えられた文字列自体を変更する方法（文字列をソートする等）も検討しよう
• 1.2
  • 文字列の比較するような問題のときは、大文字小文字を区別するか、空白をどう扱うか(無視するか)、ということを確認しておく
• 1.3
  • 文字列を操作を最後尾から順に行う方法も検討しよう。例えば、文字列中のaという文字をbbに変更する場合、末尾からやった方がやりやすい。逆にaaをaにする場合は先頭からやればよい。
• 1.4
  • 文字列が与えられたら、ASCIIかUnicodeかだけでなく、a~zのみ、a~zと空白のみ、といった具体的な文字種まで絞れないか確認する
  • 順にデータを走査しながらその調査結果をまとめたデータを作り、最後にそのデータを見直して結論を導くとき、最後のデータ見直しをするのではなく、走査中にデータの状態を逐一チェックすることで最後にすべてのデータを見直すことを省ける。（例：文字列を走査し、文字の出現回数を配列に保存していく場合、1文字保存するごとに配列がどうなっているかチェックしておく）
  • 1つの問題に対して同じ の解法を2つ以上思いつくかもしれない。冷静に判断し、どちらが良いかわからなければ面接官と一緒に議論しよう。
  • オン/オフだけを見れば良い→ビットの0/1で記録できないか？
  • ビット配列に1が1つだけあることをチェックするには-1したものと排他的論理和(XOR)^をとればよい
• 1.5
  • 場合分けをしてなんらかの判定をする場合、処理が似ていないか？場合分けせずに共通メソッド化して実装できないか？を検討する
• 1.6
  • forループの最終周の動作をきちんとチェックしよう！(aab->a2b1の圧縮メソッドで実装漏れ発生した)
  • 文字列の連結は なので注意。実行速度のボトルネックになるかも。JSであれば配列を使った実装を検討する。array.join("")で連結後のstringを吐ける。実際のボトルネックはどこかは議論すべきところ。
  • 文字列保存用の配列の必要な長さがわかれば、配列初期化時に長さを指定することも可能。そうすれば無駄にメモリを使わずに済む。そのために文字列を2回走査する/同じようなコードが増える、といったデメリットがある場合は、どっちをとるべきか議論すべきだ。
• 1.7
  • 二次元配列を行列として扱うときは、前の要素から処理するのではなく、外のレイヤーから内のレイヤーに向かって処理する方法も検討する
• 1.8
  • 該当する値(数値)をメモしていく場合、[1,3,4]のように数値でメモしていくよりその数値の最大値が決まっているならそのサイズのboolean配列で代替できる。さらにこれはスイッチのようなものなのでビットベクトル（ビット配列）にすることも可能
  • 行列の場合、1行目と1列目ををフラグ保持に利用して省メモリ化を行うという方法も可能ではある。
• 1.9
  • 組み込み関数を使って実装した場合にその関数の速度が時間計算量に影響を与える場合は、実装を予測して時間計算量を見積もる。ただしその仮定もきちんと面接官に伝えておく。

Chapter 2 連結リスト

• 2.1
  • 連結リストの問題では2つのポインタを別速度で走らせる方法がよくある
  • メモリ効率が非常に良くなって速度はからになるような解法でも思いついたら説明して議論しよう
  • doubly-linked listの要素を削るときはprev.nextとnext.prevどっちもいじるの忘れないように！
• 2.2
  • 別速度でなくとも2つポインタを使う方法を使えるか検討する
• 2.3
  • 怪しい方法しか思いつかなかったら再考する。たぶんキレイな方法がある。
• 2.4
  • null避けしてるところはundefinedも避けてるつもりだと面接官に伝えた方が良さそう
  • ロジックが問題ないかどうかを目でチェックするときは分岐網羅くらいがちょうどいいのかな？
  • 全if文の中にreturn入っていれば命令網羅するだけで分岐網羅になるんだな
• 2.5
  • [1, 2, 3]という配列だと都合が悪いから先頭に0をつけて[0, 0, 1, 2, 3]にしてしまうという発想
• 2.6
  • LinkedListの長さが不明なときはランナーテクニック！一方のポインタが末尾にいるとき、他方は真ん中にいる！
• 2.7
  • 2つのLInkedListのサイズが違うときに、サイズを合わせるために短い方にdummyデータを入れるのか、または長い方のポインタを差分だけ進めるのか...
• 2.8
  • 循環リストに2つのポインターを速度差2倍で走らせると必ず同じ場所でぶつかる

Chapter 3 スタックとキュー

• 3.1
  • どういうデータ構造を持てばよいか？みたいな問題も、自分なりの答えが出たらその構造のメモリ効率が良いか、データをadd/getしたときに速度はどうか？等を検討する
• 3.2
  • Stackにそれまで入った値の最小値も同じようにStackで持たせればよかった
• 3.3
  • 実装前に実装方法ごとのpros/consを議論しよう
• 3.4
  • データのコピーを頻繁に行う場合、コピーを遅延させることで速度改善できる（スタック2つでキューを実装する問題にて、一方のスタックが空かつremove/peek時のみにコピーすることで速度改善した）
• 3.5
  • 変数1つ、スタック2つでソートするとき、変数に退避させといて、邪魔な数を他方のスタックに戻す発想
• 3.6
  • 「先」にキューに突っ込んだかどうかを配列の順序じゃなく、単純にTimestampを持たせて判別するという発想

Chapter 4 木とグラフ

• 4.0
  • 二分探索木が問題に出てきたとき、重複する値が出てくるかどうか、また出てくる場合は左右どちらの子孫にいるのかを確認する
  • Complete Binary TreeやPerfect Binary Treeといったものが出てきたとき、どういったTreeなのか詳しく面接官に聞く

Chapter 7 オブジェクト指向設計

• 7.0
  • 曖昧な部分をきちんと質問してくるか、誰がどのように使うシステムなのかをきちんと理解しようとしているかを見ている。自分がイチ開発者として開発するスタンスで臨もう！
  • staticなクラスは継承が行えないためSingletonパターンで求められるようなサブクラスごとに実装を作り分ける柔軟性が持てない(参考)
  • シングルトンのクラスのメソッドをテストしようとすると、そのクラスが状態を持っておりテストの過程で状態が共有されるからテストの独立性を維持しにくい
• 7.1
  • 問題が分からなくても、それは俺の知識不足じゃない。問題の説明不足。聞けば良い。
  • トランプのカード全部とひかれた残りのカードをそれぞれListとして保持するか、ひかれたカードの位置をIntで持つか。
• 7.2
  • 柔軟性と保守性のあるコードが必要。クラス設計するときは、今後こういう変更がある場合にはこう対応できる、という説明をしよう。
  • てかまず要件定義めっちゃ大事。こういうことは今できるべきか？を聞く。やるべきじゃなかったら将来的にできるようにしとく
  • 同じような実装を持つなら親クラス作っとく。違う部分だけ子へ。
• 7.3
  • 構成要素を挙げる→オブジェクト　ありえる操作(振る舞い)を挙げる→メソッド
  • 振る舞い(日本語)からデータとしてはどう表現するか、に落とし込む！
• 7.4
  • たぶん超曖昧な問題文がくる。たぶん焦ってると先入観に囚われた1つの例しか思いつかない。冷静にいろんなケースがあるはずなので考えてみよう
  • Aを設計しろって言われてる場合でも、Aが依存するならBも設計することも全然ある。
  • とりあえず設計対象となる振る舞いを挙げて、どれを実装するか面接官と決めよう
  • クラスをこう分けるべき。なぜならこういうデータを持つときに複雑になってしまう、とかこういう機能が将来きたときしんどいとか、テストしづらいから、とか理由とともに説明
  • 型はこうすべき。選択肢としてはA,B,Cがあるが○○という理由からBだ。とか。
  • こうするとクラスは分けすぎかな。無駄な気がする。ただし今後種類が増えるときは・・・とか
• 7.6
  • こういうものを作れ、って言われたら、そのもののイラストを書いてみるのもいいかも。かなりイメージわく！
• 7.7
  • ウェブアプリ作る中で、Chat#addParticipantとかやらねぇなぁと思った。普通にList participantsを持つクラスにaddParticipantを持たせるとかやらなさそう。そもそも画面に見せるparticipantsのデータをメモリにもたせなさそう。スケールするときどうすんだ、こんな設計にして。
• 7.12
  • HashMapは衝突対策にLinkedListを使うのがシンプル

Chapter 9 スケーラビリティとシステムデザイン

• 9.0
  • システム設計問題を出す目的はコミュニケーション能力の評価。きちんとシステムの要件や問題点を明らかにできるか。最終的な設計よりもプロセスを見ている。
  • システムデザインの問題の進め方 要件定義(前提を確認)→図を描く→問題点が無いか？→あれば修正
  • スパイクは事前に予測しておくのが吉。それ以外に普通に月末月初とかで徐々に増えるならAuto ScalingでもOK
  • MapReduceのHelloWorld -> 文書内の単語の使用頻度を数える処理。文書を行ごとに分け、1行ごとにMapを作成、Map<Word, Count>を作り、shuffleプロセスで同じkey(Word)のものに分け、Reduceでsumする。
  • どんなシステム設計でも可用性(稼働時間)availabilityと信頼性(平均故障間隔)を意識しないとダメ。ちなみに耐久性(データを失わない)durabilityも。
  • 障害も意識する。どんな障害があるか、どう防げば良いか？
• 9.1
  • クライアントが使いやすい、自分たちのメンテコストが低いとか将来変更に強い、スケーラビリティと効率とか普段設計やるように、仕事をするようにやれば大丈夫、落ち着いて！
  • SQL書かせるメリ/デメ=追加機能あってもクライアントにSQL書いてもらえばいい、実装コストほぼ0/SQL書くのがお客さんが面倒、GUI作りがちでコスト増加/悪意がなくても負荷かけちゃう
• 9.2
  • 幅優先探索は最悪全辺を見ないといけないので、辺の数をnとすると となる
• 9.4
  • 1文字はASCIIなら1バイト仮定でいっか。回答例は4バイトだったけど。
  • hashで文字列を数値に
  • メモリが少ないマシンでどうにかせよ、みたいなときは一旦txtファイルに吐き出すという発想
  • メモリが少ないマシンでどうにかせよ、みたいなときにマシンを増やしてしまう発想。でも実装コストもかかるし、全部きちんと動作するとは限らないのでエラーハンドリングが必要
• 9.5
  • 問題の前提の深堀り足りないよ！リクエストはどれくらいくる？キャッシュしたい数ってどれくらい？マシン間の呼び出し速度は？どんなデータをキャッシュしたい？
  • キャッシュの問題が来たら、古い（ランクの落ちた）キャッシュの削除方法、最近アクセスしたものの順位を上げる（削除優先度を下げる）方法等を考えないとダメ
  • 簡単にキャッシュを実装するなら、HashMapとLinkedListを使う。Map<Key, Node>, LinkedList, Node = {key, value} としておけばよい
  • キャッシュされている内容が更新される場合はどうするかも考える。リアルタイムじゃなくていいなら定期的チェック、リアルタイムならメモリに簡易的なデータを持つとか
  • キャッシュの自動タイムアウトも考えよう
• 9.7
  • バッチプログラムで裏で処理を行う場合、対象となるデータを絞れないか検討すべき。例えば最近ログインしていないユーザーについては処理をしなくても良い等の前提を加えられる可能性がある。
  • 最近使っていないユーザーはアカウント停止するとか。（さすがにやりすぎ？
  • 銀行口座から支出の傾向知るとか言われて、口座とか支出の種類普通わからんやんって思ったらそれ聞いて前提を変える。銀行口座でも何に使ったか、店名だけはわかるとする、とか。
• 9.8
  • データがシンプルで検索の必要がないテキストファイル、しかもデータ量が多いならファイルで保存する説もある。S3とかに入れちゃうか？
  • Clarify Problem -> Precondition -> Architecture -> What's Problem??
  • 許されるなら、アクセスログのデータを省スペース化して保存するために、1/10の確率でログを記録するとか。アクセス数が多いほど確率下げてもよい。

Chapter 10 ソートと探索

• 10.1
  • a[b.length - 1] = b.pop()ってしたら、popする前のlengthで左辺は評価されるよ！
  • 引数でarrayを受け取って array = anotherArrayってやっても副作用は作れないよ！呼び出し側の変数は書き変わらないよ！
• 10.2
  • アナグラム（文字並び替えて他の言葉作る奴）になっているかの確認は、文字ごとの出現回数を持つMapを比較するか、ソートしてしまうこと。ソートしてしまえば全く同じ文字列になる。
• 10.3
  • 二分探索を適用するためにデータを整えるのではなく、崩れたデータでも二分探索のロジックを応用して解けないか考える。他の有名ロジックも、無理にそれを使おうとしない。有名ロジックを参考に独自ロジック、あると思います！
• 10.4
  • 与えられた文字列を検索せよ→空文字が与えられることがあるかどうかチェック！

Chapter 11 テスト

• 11.0
  • 現実の物体(ペン)等のテスト、ソフトウェアの一部のテスト、テストコードを書く、既存の問題の処理の4パターンに問題は分かれる
  • 全体像の理解：テストする部分の優先順位をつけよう、Amazonでは商品が表示されるところより、決済等の方が大事だ。
  • どうソフトウェアが組み合わさっているか：Googleスプレッドシートの開く、保存、編集機能のテストは当然大事だが、その他GmailやDriveとの統合テストも大事
  • 系統化：系統立ててテストについて話す。全体的には1,2,3があって、まずは1からテスト考えます、的な
  • 実用性：不具合の原因を特定できるよう問題を切り替え動作テストを行えるか
  • 現実の物体のテスト
    • 誰が何のために使うのか？→使用事例は？→使用の限度は？（回数？使用環境？）→不具合の条件は？→どうやってテストする？（5年間もつか→5年間の予想使用回数をテストする）
  • ソフトウェアの一部のテスト
    • 手動 vs 自動：ポルノが含まれるか、とかは人間の方が楽。あとはテスト外のことにも人なら気づける
    • ブラックボックス vs ホワイトボックス：ブラックボックスはホワイトボックスに比べると自動化しにくい
    • ブラック/ホワイトどっちのテストをしてるか確認→誰が何のために使うのか？→使用事例（ユースケース）は？→使用の限度は？（機能要件）→不具合が発生したときに起きる障害は？→テスト方法の検討
  • 関数のテスト
    • ケースの洗い出し（通常ケース、エッジケース、null/不正値、奇妙な入力値（既にソート済、ソート逆順になってる））→期待値の定義（戻りだけでなく、副作用あるかも確認）→コード書く
  • 問題解決（こういう障害をお客様から受けたときどう問題を切り分け、テストし原因を特定しますか？）
    • お客様から「Chromeが起動時にクラッシュします><」→詳細を把握（いつから？バージョンは？再現手順？クラッシュって何？）→問題の発生しうる箇所（オペレーション）をリスト化→どのステップで問題があるか特定できるケースを作成
• 11.2
  • ランダムにクラッシュするプログラムの要因として、ランダム変数（現在時刻等）、メモリリーク、未初期化変数（使いまわしている）、外部要因（筐体が壊れている）等が考えられる
• 11.3
  • ソースコードの一部を与えられ、そのテストコードを考えろと言われた場合、テストコード全体を思い浮かべた方がいい、どんなクラスがあるのかなど。じゃないと観点が漏れる。
• 11.4
  • 負荷テストと言われたら、応答速度のリソース利用率をとりあえず思い出す。そこから仕事通りにやればOK
• 11.5
  • 物体のテストでの異常系の観点漏れに注意。ペンのテストなら、書くだけじゃなくて踏むとか
• 11.6
  • ブラックボックスかホワイトボックスか（ソースコードを見れるのか）確認！
  • テストの優先度をつけよう。そのためにはテストを設計する→実際にどれくらいのスケジュールで叩く、というのが現実世界にはあるはずなので、そこを考えれば良い。どこまでも現実世界のものとして考えれば大丈夫なはず！

Chapter 14 データベース

• 14.0
  • 完全に正規化しているとデータは最小限で良いが読み取り時に（結合）コストがかかる。非正規化DBは一般に大規模システムで利用される
  • LEFT (OUTER) JOIN : 左(From直後)のテーブルは全て表示するよう結合する。GROUP BY とかはその結合した表に対して行う（だからGROUP BYした奴しかSELECT直後に書けない）
  • DBは論理設計(エンティティ定義、正規化等)→物理設計(テーブル定義、インデックス、ハードウェアとか)
  • 論理設計せよと言われたらエンティティ定義→関係性(1 to many等)見る→正規化
• 14.4
  • INNER JOIN -> 結合するためのIDが対象のテーブルに全て存在するデータを抽出
  • LEFT OUTER JOIN -> From 直後のテーブルの行を全て表示
  • RIGHT OUTER JOIN -> JOIN句の後のテーブルの行を全て表示
  • FULL OUTER JOIN -> 左右どちらも全て表示
• 14.5
  • 正規化/非正規化；data normalization/denormalization
  • 非正規化メリット：読み込み時に結合が必要なくなるので高速化される。クエリが単純になる（バグが減る）
  • 非正規化デメリット：同期処理を実装する必要がある、そのタイミングについても考慮が必要。同じデータが2箇所以上に存在するため一般的に設計が複雑、容量も使う。データの整合性が取れない時間が存在するかも（どっちが正しいのかを決めておく）。
• 14.6
  • XX図を書けって言われたらどういう図か確認しよう。思ってるのと違う図かもしれん。
• 14.7
  • 「こういうデータベースがあったとして...」って言われたら、テーブルじゃなくてデータベースってことなんやと再確認しよう
  • どういうテーブルが存在するのか不明ならきこう。決めろ言われると思うから決めよう。
  • 変数とかはしんどいな・・・