はてなブックマーク

この記事では，検索しても意外と解説が少なかったLRUキャッシュとLFUキャッシュをPythonで丁寧めに実装していきます．特にLFUキャッシュが厄介なのでそちらがメインです． キャッシュとは ざっくり言うとキャッシュはよく使うデータを取り出しやすい場所に一時的に保存しておくものです．メモリ上のデータは参照される頻度に差があるので（時間的，空間的局所性など），よく参照されるデータをキャッシュに入れておくことでデータアクセスが高速になります．現代のコンピュータにはまさに必須の構造です． キャッシュに蓄えられるデータは多くはないため，どのデータを置いておくかというのは重要な問題です．容量いっぱいのキャッシュに新たな要素が入ってきたとき，今保持しているどの要素を捨てるかという選択に関して，最も基本的なものが以下の2つです． LRUキャッシュ: Least Recently Used. 直近に参照し

実世界での株取引では，刻一刻と変化する株の値を見ながら，新たな株を買ったり自分の所有する株を売ったりしてより多くの利益を得ることを目指します． もちろん株の値動きを予測するのはとても難しく，この記事もそれを目指している訳ではありません．実際の状況では未来の値動きはわからないのですが，今回はこれを単純化し，値動きを記録した数値の列が与えられたときに，いつ「売り」や「買い」を行えば最も高い利益を得られるかを考えます． 問題設定 これは，各時刻での株価が入った配列を入力として，そこから得られる最大利益を出力するような関数を設計する問題になります． def calculate_max_profit(prices: List[int]) -> int: ... return max_profit のようになります．基本的なルールは以下のようなものです． 各時刻で買う操作と売る操作のどちらかを行うこと

突然ですが，この山って一体どれくらい水が溜まると思いますか？ 上から雨が降ったらたぶんこんな感じで池ができるはずです． この山を，縦横1マスを1とする座標系に置いた場合，溜まる水の量を数えてみると6になります．このもし山が巨大になったら，水の量はどうやって求めればいいのでしょうか？ さらに，こんな感じで立体的にした山はどうでしょうか？溜まる水の量，気になってきませんか？ 皆さんがどの程度共感してくださるかはさておき，実はこの問題はコーディング面接の教科書にも載っているような有名な問題です．その解法が面白かったので紹介していきたいと思います． 2次元の山 まず山が方向と高さを持つ2次元の場合を考えます． 山の高さを配列で表現すると，この問題は，各地点の高さを表現する配列 $height = [0,1,0,2,1,0,1,3,2,1,2,1]$ を入力とし，溜まる水の量を返す関数を設計する問題

はじめに コーディング面接というものをご存知でしょうか？ コーディング面接とはGAFAなどをはじめとする海外のTech系企業などで広く行われている面接で，データ構造やアルゴリズム，システムデザイン等の知識を問うものです． 面接 - Google Googleで行われるようなコーディング面接は， 45分程度の時間内に データ構造やアルゴリズムの基礎に関する問題を 面接官と話し合いながら（多くの場合英語で） ホワイトボードにコードを書いて解く といった特徴があります． データ構造とアルゴリズムの問題自体は，Cracking Coding Interviewのような書籍やLeetcodeのようなサイトを使って練習を積むことができます． しかしコーディング面接の最大の特徴は「面接官とコミュニケーションを取りながら」問題を解くことです．これは一人で本を読んで問題を解いたり競技プログラミングに取り組む