サンダーボルト

相手モンスターを全て破壊する。

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つの問題に対して同じ O(n) の解法を2つ以上思いつくかもしれない。冷静に判断し、どちらが良いかわからなければ面接官と一緒に議論しよう。
    • オン/オフだけを見れば良い→ビットの0/1で記録できないか？
    • ビット配列に1が1つだけあることをチェックするには-1したものと排他的論理和(XOR)^をとればよい
  • 1.5
    • 場合分けをしてなんらかの判定をする場合、処理が似ていないか？場合分けせずに共通メソッド化して実装できないか？を検討する
  • 1.6
    • forループの最終周の動作をきちんとチェックしよう！(aab->a2b1の圧縮メソッドで実装漏れ発生した)
    • 文字列の連結は O(n^{2}) なので注意。実行速度のボトルネックになるかも。JSであれば配列を使った実装を検討する。array.join("")で連結後のstringを吐ける。実際のボトルネックはどこかは議論すべきところ。
    • 文字列保存用の配列の必要な長さがわかれば、配列初期化時に長さを指定することも可能。そうすれば無駄にメモリを使わずに済む。そのために文字列を2回走査する/同じようなコードが増える、といったデメリットがある場合は、どっちをとるべきか議論すべきだ。
  • 1.7
    • 二次元配列を行列として扱うときは、前の要素から処理するのではなく、外のレイヤーから内のレイヤーに向かって処理する方法も検討する
  • 1.8
    • 該当する値(数値)をメモしていく場合、[1,3,4]のように数値でメモしていくよりその数値の最大値が決まっているならそのサイズのboolean配列で代替できる。さらにこれはスイッチのようなものなのでビットベクトル（ビット配列）にすることも可能
    • 行列の場合、1行目と1列目ををフラグ保持に利用して省メモリ化を行うという方法も可能ではある。
  • 1.9
    • 組み込み関数を使って実装した場合にその関数の速度が時間計算量に影響を与える場合は、実装を予測して時間計算量を見積もる。ただしその仮定もきちんと面接官に伝えておく。

Chapter 2 連結リスト

  • 2.1
    • 連結リストの問題では2つのポインタを別速度で走らせる方法がよくある
    • メモリ効率が非常に良くなって速度は O(n)から O(n^{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とすると O(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
    • 「こういうデータベースがあったとして...」って言われたら、テーブルじゃなくてデータベースってことなんやと再確認しよう
    • どういうテーブルが存在するのか不明ならきこう。決めろ言われると思うから決めよう。
    • 変数とかはしんどいな・・・

ビット演算子を色々試してみる

プログラミング基礎

モチベーション

Webアプリケーション等の製品のソースコードを書いている中ではビット演算なんてしないんだけど、エンジニアの嗜みとして知っておくべきだよな、と思ったので色々試してみます。

環境

とりあえずローカルのnodeで試した

% node -v
v12.16.1

演算子

これに基づいて勉強

ビット論理積 (AND)

1100 & 1010 は 1000になりそう。試してみよう。

> 24 & 20
16

おお〜〜！！

ビット論理和 (OR)

1100 | 1010 は 1110になりそう。試してみよう。

> 24 | 20
28

おおー！

ビット排他的論理和 (XOR)

1100 ^ 1010 は 0110になりそう。

> 24 ^ 20
28

そろそろ感動もなくなってきたね😅

ビット否定 (NOT)

~をつけると0と1が反転するらしい。

~ 1100が 0011、つまり3ってことか？

> ~ 24
-25

な、なんだってー😅 というわけで、調べる。 Mozillaさんによれば、

JavaScript の Number 型は IEEE 754 の倍精度 64ビットバイナリ形式

であるという。（IEEE 754は仕様の名前で、「倍」精度は昔は32ビットが基本だったからそれの倍の64だから「倍」精度と言っている。） ではそのこのとき、先程の24はどのようにビットとしては表現されていたのか？指数部とか仮数部とかはちょっと複雑なので単純化すると

00001100

みたいな感じになっている。これにNOT演算すると、0011ではなく、

11110011

となる。で、これはどういう数値か？ 24は00001100でした。 では、25は1足せば良いので、00001101ですね。では、試しに先程のNOTした後の11110011と25である00001101を足してみましょう

  11110011
+ 00001101
----------
 100000000

となり、今は8ビット(1バイト)のテイで24を00001100と定義していたので、100000000の一番左の1は桁が溢れて落ちます。つまり00000000、0となるわけです。

11110011はどういう数値か？25に加えたら0になる数値。つまり-25なのだ✌（2の補数表現で実装されているということがこれでわかる)

左シフト

a << b で2進表現の a を b ビット分だけ左にシフト（右から 0 で詰める）ができるらしい。つまり、桁が１つ増えるということは、 << 1で2倍できるということかな？

> 8 << 1
16
> 8 << 3
64

なるほど。ちなみにどれくらいの桁で溢れるんだろうか。0で埋めるんだからいつか突然0になるはず。

> 1 << 29
536870912
> 1 << 30
1073741824
> 1 << 31
-2147483648
> 1 << 32
1

ほう？29->30は普通に2倍されている。30->31は、01000...000だったのが10000...000のように1と0が31ビット続くようになって、2の補数なので-2147483648になったんだな。 で、なんで1 << 32で1になるの？😅

> 1 << 32
1
> 1 << 33
2
> 1 << 34
4
> 1 << 35
8

謎すぎる😅謎めいた心の中冷めた君はミステリアス♪😅 32ビットとして扱われるという前提だから、サポート外の動きだからこれ以上追っても意味ないのかな。Node.jsのソースはちらっと見たけど.ccということでC++だった。ちょっと追えそうになかった。。。C++のビット演算子をそのまま使っているのだろうか・・・

符号維持右シフト

a >> bで2進表現の a を b ビット分だけ右にシフトします。溢れたビットは破棄します。ですって。 正の数で試すと

> 4 >> 1
2
> 4 >> 2
1
> 4 >> 3
0

なるほど。負の数は？

> -4 >> 1
-2
> -4 >> 2
-1
> -4 >> 3
-1
> -4 >> 4
-1

これは算術右シフトです。つまり、-4は 11111100みたいな感じなんすけど、これを11111110としている、つまり右端の0を落としてその代わりに左に1を入れているんですね。シフト前の左端の数と同じ数を入れるのが算術右シフト。それと違ってとりあえず0入れちゃうのが論理右シフト。11111111以降は、いくら右にシフトしても11111111のままなんで、ずっと-1なんですね〜。

ゼロ埋め右シフト

👆でちょろっと触れてしまったけど、a >>> bで2進表現の a を b ビット分だけ右にシフトします。溢れたビットは破棄し、左から 0 で詰めます、との。つまり、

> 4 >>> 1
2
> 4 >>> 2
1
> 4 >>> 3
0

これは同じだけど

> -4 >>> 1
2147483646

WOW! 11111100 を01111110にしたってイメージですね。32ビットでの最大の正の数は2147483647ですから、そこから1引いた値になっているということで納得だ。

データ構造/アルゴリズム/概念のまとめ

プログラミング基礎

モチベーション

この本👇

を読んでいると、間違いなく必要な知識のリストというのが出てきたので、それらについて知らないことは勉強して自分なりにまとめておきたい。

間違いなく必要な知識

f:id:nao_666:20200709214806p:plain
間違いなく必要な知識

これらを順にまとめていこう！

データ構造

連結リスト

JavaでいうところのLinkedList。Nodeが次の要素へのポインタを持っているような構造。

  • 単方向(次の要素のポインタだけ)
  • 双方向(前の要素のポインタも持つ)

の2種類があり、また

  • 線形リスト
  • 循環リスト

となっている場合もある。 index指定で要素を取得するのはメモリを連続的に確保している配列に比べると遅い。先頭への要素追加は配列のようにその他の要素をコピーしなくていいので爆速。ポインタを付けかえるだけなので基本的に追加削除が得意。 LinkedListの要素の追加は、追加する前(後)のNodeまでは先頭か最後尾からたどっていく必要はあり、その分の時間はかかる。

JavaのLinkedListの指定したindexのNodeを取得するメソッド👇前半か後半かを判断して先頭と最後尾のどちらから辿れば速いか判断して探してる。

hg.openjdk.java.net

木、トライ木、グラフ

木

連結(どの2点もつながっている)であり閉路(始点と終点が同じとなる経路)をもたないグラフ。ノードとエッジで構成される。

f:id:nao_666:20200712222320p:plain:w300
木構造(Wikipediaより)

  • root node 親をもたないノード
  • leaf node 子をもたないノード
  • internal node 子をもつノード
  • height あるノードから葉ノードへのエッジ数の最大値。root nodeのheightはその木構造の高さ。
  • depth あるノードからroot nodeまでのエッジ数のこと。root nodeは0。

トライ木

f:id:nao_666:20200712223431p:plain:w300
トライ木(Wikipediaより)

複数の文字列を保持するのに適したデータ構造。文字列の検索が高速。n文字の文字列の検索、挿入ともに 0(n)で可能。辞書の実装などに使われている。

複雑なデータ構造や浮動小数点数などをトライ木で扱うには工夫が必要。少数の非常に長い文字列を格納する場合はメモリ効率が悪くなる。この場合はパトリシア木が適する。

グラフ

木やトライ木などを含む概念。ノードとエッジで構成されたもの。奥が深すぎるので一旦概念だけにしておこう。。。

スタックとキュー

スタック

いわゆる後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）ってやつ。割り込み処理などで使われる。

キュー

先入れ先出しのやつ。

ヒープ

f:id:nao_666:20200713000337p:plain:w300
ヒープ(Wikipediaより)
Wikipediaによれば「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造のことらしい。

挿入、削除がO(log n)で可能。探索はO(n)。 ルートが常に最小（または最大）要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。 このときの計算量はO(n log n)。(ヒープソート)

なるほどなぁ

ベクタ/配列リスト

これはいいか。

ハッシュテーブル

これもよく使うけど一応。

ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。 (Wikipedia)

検索や追加が O(1)で可能。ただし、ハッシュ値が衝突した場合は、最悪の場合 O(n)となる。

衝突の対策として、オープンアドレス法とチェイン法がある

オープンアドレス

衝突したら、空いているアドレスに入れればよくね？という発送。新たに空いているアドレスを調べる方法はいろいろあるが、とにかく何らかの方法で空いているところを探す。例えば、もし衝突したら、隣のアドレスを見る、といった方法でもよい。この場合、その要素にはキー&バリューを保存しておき、探索の際はハッシュ値によって特定したアドレスから順に要素（キー）を見て、お目当ての要素を探す。

チェイン

ハッシュ関数で導いたアドレスに、連結リストの先頭Nodeを入れておく。衝突した場合はそのリストの先頭に要素を追加していく。 探索の際は、ハッシュ関数で連結リストを特定し、そこから全要素を調べる。リストの要素にはキーも格納されているので、それを見て探索する。

アルゴリズム

幅優先探索

f:id:nao_666:20200714235922p:plain:w300
幅優先探索(Wikipediaより)

ツリー構造で使うアルゴリズム。言葉のまま。

Wikipediaの擬似コードがわかりやすかったので引用。

function 幅優先探索(v)
    Q ← 空のキュー
    v に訪問済みの印を付ける
    v を Q に追加
    while Q が空ではない do
        v ← Q から取り出す
        v を処理する
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i を Q に追加

深さ優先探索

f:id:nao_666:20200714235848p:plain:w300
深さ優先探索(Wikipediaより)

Wikipedia擬似コード👇

function 深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each v に接続している頂点 i do
        if i が未訪問 then
            深さ優先探索(i)

二分木

アルゴリズムの欄に二分木と書いてあってよくわからない（二分木はデータ構造のはず）のだけど、とりあえずデータ構造についてメモ。 二分木はedgeの数が2本以下の木構造。全部edgeが2本あったら全二分木、深さが全て同じなら完全二分木。二分木を走査するアルゴリズムとして👆の幅優先探索や深さ優先探索がある。

二分探索木はWikipediaによれば

構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。

という感じ。「子」じゃなくて「子孫」ってのがポイントやね

f:id:nao_666:20200716145358p:plain:w300
二分探索木(Wikipediaより)

マージソート

分割統治法にてソートする方法で、再帰的に二分し分解していき、2要素以下になったらソート->マージを繰り返す方法。

クイックソート

これも分割統治法の一種で、基準を決めてその基準より大きい<->小さいに分ける。それぞれのブロックについても再帰的にやっていく。計算量は n log n。最悪の場合は n^{2}。

概念

ビット操作

この記事でまとめた👇 naotech.hatenablog.com

メモリ（スタック vs. ヒープ）

スタック

OSやコンパイラが割当を行う領域で、プログラムから自由に確保はできない。関数の情報や、変数などをこの領域に保持する。例えば

main() {
  test();
}
test() {
  const a = 1;
}

とした場合は、main -> test -> a と順番にスタック領域に情報が積まれていって、使われなくなる順に沿って（つまり積まれたのとは逆順に） a -> test -> main とメモリから消えていく。 ソースコードを見て静的にどこのメモリを使えばいいか判断できるから、コンパイラがやってくれるんですね。メモリの管理方法としては、とびとびになったりしないので、高速なようです。

ヒープ

heap。英語で「積み重ね、山」という意味らしい。ヒープというデータ構造もまぁそれっぽいっちゃそれっぽいすね。 動的にプログラムから確保できる領域。例えば、ファイルをプログラムで読み込んでそれをメモリに乗せる場合、その容量がどれくらいかは分からないのでコンパイル時点では確保できませんね？つまりスタックには乗せられません。こういったものはヒープに乗せます。とりあえず動的にその都度必要なものを無計画に積んでいく様とheapという言葉はつながるものがありますね。 実際にheap領域をどう扱うかの実装はものによって違うので、実装が実際にヒープ構造になっているかどうかとかはあまり気にしなくて良さそう。

ガベージコレクションはこのヒープ領域の要らなくなったメモリを勝手に破棄してくれる仕組みです。

再帰

  • 自分を呼び出せば再帰
  • ベースケースの処理を入れて再帰をとめないとだめ
  • 再帰するときの途中までの結果をメモリに積んでおいて高速に処理する方法がメモ化再帰
  • n個に対する課題をn-1個に対する課題に帰着できれば、再帰で実装できそう
  • 部分和問題(n個のうち合計がXになる組み合わせを探す)については、1つ目の値Aを使う場合は、残りn-1個でX-Aの値を作れるかどうか、1つ目の値Aを使わない場合は残りn-1個でXを作れるかどうか、という話に帰着できるので再帰が使える

動的計画法

Wikipediaによれば

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

らしいです。この具体例がメモ化再帰ですね。

ビッグ・オー記法、スペース

これはこの本でも何回も出てきてますが、再度自分の言葉でまとめよう。以下はとりあえず学術的な定義。

ビッグ・オー記法

実際にかかる時間の上限であればいい。それより計算量が大きくなることはない、って意味合い。例えば配列の各要素を出力するのは O(n) だけど、ビッグ・オー記法で書け、と言われたら O(n^{2}) でも間違いじゃない。意味ないけどな。

ビッグ・オメガ記法

オーと違いこいつは下限であればいい。それより計算量が小さくなることはない、って意味合い。配列の各要素出力の例で言えば、 Ω(1) でもいい。意味ないけどな。

ビッグ・シータ記法

O と Ω の両方の意味、すなわち O(n) かつ Ω(n) のときに Θ(n) と言える。

面接では

ただしコーディング面接でのO記法はΘの意味合いに近く、あるアルゴリズムでありえる最悪の計算量をOを使って表すのが正しいとされている。つまり、各要素を出力するのは O(n^{2}) だと間違いで、 O(n) って答えないとだめ。

スペース

空間計算量のことかな。

計算量オーダーと具体例のメモ

プログラミング基礎

モチベーション

代表的な計算量にも色々あることを最近学んだ。

アルゴリズムを思いついたとき、その計算量がいくつなのかというのを瞬時に判断できるようにするために、各計算量のアルゴリズム例を自分の言葉でメモしておく。

参考：計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita

計算量と具体例

O(n)

リストの各要素を順に見ていくようなとき。個数に比例して計算量が増える。

例）線形探索、リストでfor文まわす

O(n^{2})

2つのリストの全組み合わせを見ていくようなとき。

例）2重のfor

O(n^{3})

3つのリストの全組み合わせを見ていくようなとき。

例）3重のfor

O(\log n)

nがx倍されると計算量が1回増えるようなとき。

例）二分探索、X進法展開

O(n\log n)

nがx倍されると計算量が1回*x回になるようなとき。二分探索×線形探索のようなとき。

例）マージソート、分割統治法において分割された1つ1つ部分の計算量が O(n)のとき

f:id:nao_666:20200716170848p:plain:w300
O(nlogn)のイメージ図

O(\sqrt{n})

そのままだけど、計算量が O(\sqrt{n})のとき。例えばn=9で3回、n=16で4回のとき。

定数倍は無視だから、例えばn=9で6回、n=16で8回というようなアルゴリズムが出てきても同様に O(\sqrt{n})なんだな。

例）素数判定

O(n2^{n})

2^{n}個数あるパターンを全て書き出して、そのパターンそれぞれに n 回の処理をするようなとき。

例）部分和問題（ 2^{n}個のパターンのリストを書き出したあと、求めている値になるか、全ての要素を足し合わせてるために n回の処理をする

O(nn!)

n!個数あるパターンを全て書き出して、そのパターンそれぞれに n 回の処理をするようなとき。

例）巡回セールスマン問題（ n!個の道順のパターンを書き出したあと、所要時間を合計するために全てを足し合わせないといけない。）

Concept Challenge: Which Tests Should You Run?のメモ

TechDevGuide

Tech Dev Guide の これ👇 techdevguide.withgoogle.com

の課題であるこれ👇

www.coursera.org

を見たときのメモ。

メモ

remove(0)メソッドが成功したと判断するための基準は何か？

自分の考え

  • エラーが発生しない
  • 戻り値が正しいか
  • sizeが1減っているか
    • 要素とは別の参照で管理されているから
  • 元indexが1の要素のpreviousがnullになっているか

解説 essential piece（必要不可欠）なものをテストしよう。

  • get(-1)はgetのテストでやるからいらない
  • get(0)のチェックは当然いる
  • get(1)はgetとかaddとかで見るでしょ。1つシフトされたのをget(0)で見てるから不要
  • get(2)もいらない　getのテストしてるんじゃないんや
  • sizeのテストはいる。不可欠や

ここまででremoveのテストはきちんとできているはず。しかし、1つめの要素のprevが消したはずの要素を指しているというバグにここまでのテストでは気づけない。

We'll recommend for you to actually break the boundaries of black box testing just a bit.

リストとして正しい動きをしているけど、内部構造がおかしい、というようなバグを見つけるにはデータ構造を考えてテストしないといけないね。 場合によってはブラックボックスバリアを破って（外からテストできることだけじゃなくて、内部構造についての観点で）テストしていかないとね〜

Algorithmic problem solving and interviewsのメモ

エンジニア転職 TechDevGuide

Tech Dev Guideのこれ👇

techdevguide.withgoogle.com

のこれ👇

www.coursera.org

を見たメモです

メモ

  • 面接では最初にめっちゃ質問せよ。面接官がまだ言ってない前提とか、いろいろを聞き出しまくれ
  • その後自分の理解を確認せよ。そのとき、具体例（実際の引数とか）を出せ。隠された前提とかが出てきたら👆に戻って質問して問題を明確化せよ
  • エッジケースの確認をせよ。（隠された）難しいポイントを見つけておけ。追加で出てきた前提条件とかもちゃんとメモっとけ
  • ここでやっと設計を始める。とりあえず思いついた1つめの奴で設計してみよう。もしエレガントな方法じゃなくてもまずは正しい方法をブルートフォースでも良いので見つけておくべき
  • で、ブルートフォースでも良いので、まずは頭の中テストする。ノーマルテスト、エッジケース。その後、どういうデータ構造が良いか考える。ブルートフォースにはどんなデータ構造が適切か？そしてパフォーマンスはどうか？メモリ性能は？実行速度は？？
  • そこまで確認して、良い感じに設計できたら、再度別の方法で設計する。そしたらまた別の方法で設計する。その後、一番良い設計ができたら、やっと実装開始だ

Activity Log(2020年5月 第5週)

この記事は何？

技術に関する個人的な学びやアウトプットをまとめたもの。

インプット

公式ドキュメントや本など

Admob系の記事をたくさん読んだけど、あんまメモってなかった😅

アウトプットした記事の中にたくさんリンクが貼ってると思う。

その他記事

なし

アウトプット

ブログ

開発

仕事以外では特にやってないか〜

まとめ

  • アップデートした結果、3日間くらい広告収入が3~40円くらいになって、月に1000円くらい儲かりそうと思って、すごくやる気が出てAdmobをめっちゃ調べていた
  • きちんと科学的にアプローチしたく、KPIツリーを作って、どういったAnalyticsを仕込めば良いかを考えていた
  • 。。。なんだけど、広告収入が高かったのは最初の3日間だけでその後はほぼ0円となっており、急激にやる気がなくなっているのが今😅