Matsushita's Blog

グローバルIPアドレスの利用 NAPT

NATとは LANに接続した複数のPCからインターネットを利用するには、各PCのプライベートIPアドレスをグローバルIPアドレスに変換する機能が必要。これの機能をNATという。 コンピュータはプライベートIPアドレスという住所をもっている。しかし、インターネッ…

分散データベースの2相コミット

2相コミット (2フェーズコミット) とは 複数のデータベースの内容を更新する時に、処理が矛盾しないように整合性を保つための手法。 具体的には、複数のデータベースを更新する前に、全てのデータベースが更新可能かどうかを確かめてから、一斉に更新を行…

バッファサイズの計算

バッファとは バッファとは、処理速度の異なる装置間にデータを転送する際に、速度のギャップを埋めるためにデータを一時的に蓄える機能。 例 以下のような転送を考える。 装置A ---送信量S---> バッファ ---受信量R---> 装置B 装置Aは1秒当たり送信量Sに対…

仮想記憶システムのページング方式

主記憶 CPUが直接書き込みができるメインメモリの事。 仮想記憶 主記憶上にある実記憶領域の1部を必要に応じてハードディスクなどに退避させることで、見かけ上、物理的な容量より大きな主記憶領域を利用できるようにする仕組み。 ページング方式 仮想記憶…

RAID (Redundant Array of Inexpensive Disks)

RAIDとは RAIDとは、複数の磁気ディスクを並列に接続して、信頼性の向上やアクセスの拘束を図る手法。 RAIDには複数の種類がある。 RAID 0 RAID 0とは、データを複数のディスクに細分化して書き込み、アクセスを高速化する方式。(ストライピング) RAID 1 RAI…

キャッシュメモリの書き込み方式

キャッシュメモリの書き込み方式 キャッシュメモリへの書き込み方式には、ライトスルー方式とライトバック方式がある. ライトスルー方式 プロセッサがメモリにデータを書き込む際、キャッシュと主記憶に同時に書き込む方式。 書き込み処理は高速化できない。…

MIPS計算

MIPS計算 MIPSとは、プロセッサが1秒間に実行する命令数を百万単位(106)で表したもの。 問題 動作クロック周波数が700MHzのCPUで、目入れ実行に必要なクロック数及び、その命令の出現率が表に示す値である場合、このCPUの性能は約何MIPSか 命令の種別 命令…

筋肉をつけるために

最近 細マッチョになりたくて筋トレをはじめました。 近所の市民ジム的な所でいそいそとやっています。 プロテインも買いました。ついでにシェーカーも。 牛乳で割ると案外美味しい。 スポーツドリンクの役割は水分補給だけじゃない 最近はじめて知ったので…

Binary Search Tree Iterator in LeetCode

問題 Binary Search Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。 Binary Search Tree Iterator - LeetCode ソースコード

House robber ⅲ in LeetCode

問題 2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。 条件 直接つながれている隣同士のノードは取る事ができない。 House Robber III - LeetCode 解き方 それぞれのノードについて、そのノードの値を和に含め…

Serialize and Deserialize BST in LeetCode

問題 2分木に対するSerializeとDeserializeを実装するクラスを作る問題 leetcode.com ソースコード My simple and clear Java solution | LeetCode Discuss

Insert Delete GetRandom O(1) - Duplicates allowed

問題 通常のHashTableの機能に加え、テーブル内の要素をランダムで返すメソッドを実装されているデータ構造を作る。データ構造内の要素は重複が許されており、重複した要素の数はランダムな要素を返す関数に影響する。 leetcode.com ソースコード

Insert Delete GetRandom O(1)

問題 通常のハッシュテーブルの機能に加えて、テーブル内の要素をランダムで取得するメソッドが実装されたデータ構造をデザインする問題。 全ての操作はO(1)で行う必要がある。 leetcode.com 解法 HashMapとArrayListを用いることで解くことができる。問題は…

Add One Row to Tree

問題 2分木が与えられ、与えられた深さに1行分ノードを追加するという問題 leetcode.com ソースコード

オーダー計算量と実際の処理時間と使用容量を比較する

結果 僕の環境では以下の値となった。言語はJava。 空間計算量O(N)とすると実際の使用容量はN byte程度 時間計算量O(10x) とすると、10-1*(9-x) 秒程度 ※オーダーの値が小さいと誤差は出る Javaのメモリーサイズ Javaのメモリーサイズはメソッドによって取得…

Design TinyURL in LeetCode

Problem TinyUrl is a URL that a original URL is compressed. This problem is how should we design TinyURL services. https://leetcode.com/problems/design-tinyurl/#/solutionsDesign TinyURL - LeetCode How to code First, I prepare two HashMap t…

2分探索木からノードを削除する Delete Node in a BST in LeetCode

問題 2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。 leetcode.com 解法 以下のステップで解く 2分探索でkeyを見つける 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。 右側のサブツリーから…

Perfect SquareかをO(logN)で判定する LeetCode

問題 leetcode.com 解法 単純にfor文を用いた解法だとO(√N)となり間に合わない。 2文探索を用いることでO(logN)で解くことができる。 ソースコード

【グラフ理論とネットワーク理論】Extended Complete Graph

Connectivity and Damage Index Connectivity Connectivity express the reliability of the graph Node Connectivity Cv(G) : Minimum number of nodes to be removed to make a graph unconnected. Branch Connectivity Ce(G) : Minimum number of branche…

サイズNの配列からM個の要素をランダムに取り出す

問題 サイズNの配列からM個の要素を取り出し新たな配列を返すメソッドを実装する。各要素が選ばれる確率は全て等確率になるようにする。 解き方 はじめに元々の配列の先頭からM個取り出して配列を作る。後は、インデックスがm以上の要素と以下の要素を交換す…

Least Recently Used (LRU) cache を実装する

問題 LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。 leetcode.com 解法 HashMapと双方向連結リストを利用することで実装することができる。 リストを用いるこ…

合計の入れ替え Cracking The Coding Interview

問題 2つの整数配列が与えられる。それぞれの配列から1つずつ要素を決め、それらを交換した時に2つの配列の要素の合計値が一致するようなペアを見つける問題。 入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3} 出力: {1, 3} 解法 全列挙の解法 O(A*B) i, jを添…

古い携帯電話 ガラケーのキーボード

問題 ガラケーのキーボードにおいて、入力値としてキーボード上の押した数字が与えられる(連打回数は無視)。 この時に、押した数字によって得られる単語の組合せの内、辞書に乗っているものを出力する問題。辞書は予め与えられ、データ構造は自由に設定でき…

【グラフ理論とネットワーク理論】線形構成法

線形構成法 Linear Design Method 直径最小化問題 Minimizing Diameter Problem (n, d) グラフとは、接点数n, 各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。 また、経路の長さは、経路中の枝の数で…

湖の大きさを列挙する

問題 { {0, 2, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {0, 1, 0, 1} } が与えられる。0の部分が湖で、縦横斜めで0が連なっている所は同じ湖とする。全ての湖のサイズを列挙する問題。 ソースコード

'a'と'b'でパターンマッチ

問題 文字列wordとパターンを表すpatternが入力値として与えれる。patternは'a'と'b'のみで構成されている。wordがpatternにマッチするか否かを求める問題。 例 word = “catcatgocatgo”, pattern = “abbab” a -> cat b -> go とすればwordはpatternにマッチ…

平面上のN個の点を最も多く通る線を見つける

問題 xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題 leetcode.com 解法 HashMapを用いることでO(N2)で解くことができる。forループを2回使い2つの点を全列挙する。2つの点のを結ぶ傾きをキーとして、H…

階乗のゼロ Cracking the Coding the Interview

問題 整数Nが与えら、Nの階乗を計算した時に、末尾に連なる0の数を求める問題。 解き方 どんな時に末尾に0が来るか考える。階乗の計算では足し算はなく掛け算のみなので、10を掛けた時に末尾に0がつく。また、10は2×5なので2と5を掛けた回数分、0が着…

JavaのCollectionsクラスのshuffleメソッドの実装を覗く

はじめに リストをランダムに入れ替える方法を考える時にどのようにするのが実装するのがベストなのか疑問に思い、JavaのCollectionsに定義されているshuffleメソッドの実装を見てみる。 Collections.shuffle 上記のコードで実際にランダム化している箇所は…

LinkedListから重複した要素を除く Hacker Rank

問題 www.hackerrank.com ソースコード