Insert Delete GetRandom O(1)
オーダー計算量と実際の処理時間と使用容量を比較する
結果
僕の環境では以下の値となった。言語はJava。
- 空間計算量O(N)とすると実際の使用容量はN byte程度
- 時間計算量O(10x) とすると、10-1*(9-x) 秒程度
※オーダーの値が小さいと誤差は出る
Javaのメモリーサイズ
Javaのメモリーサイズはメソッドによって取得することができる。
maxMemoryとは、使用メモリーがtotalMemoryに近づいた時に、更にメモリーの使用を試みる値となる。
maxMemoryは大体2GBであることが分る。
空間計算量
Int型の整数１つのバイト数は１バイトとなる。つまりO(106)だと106バイトとなり、1MBとなる。 109個の場合は、1GBとなり、out of memory errorが発生する。
107の場合、10MBとなる。
実際に図ってみても使用メモリーは40MBと妥当な値を出している。
まとめると、空間計算量O(N)とすると実際の使用容量はN byte程になった。
時間計算量
処理時間はSystem.nanoTime()によってナノセカンドを得る事ができる。
O(107)だと13msで10^-2秒程となる。
- O(109) : 1703ms → ２秒弱
- O(108) : 127ms → 0.1秒 (10^-1秒)
- O(107) : 13ms → 0.01秒 (10^-2秒)
- O(106) : 6ms → (10^-3秒)
まとめると 時間計算量O(10x) の場合、10-1*(9-x) 秒かかる。
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 to store short URL and original url. One is for storing short url as a key and original url as a value. Another is for the reverse. Next, how I create tiny url from original url. In my case, I create tiny url by random characters, such as 0-9, a-z, A-Z. And the size of tiny url is 10. If tiny url which I create is duplicate, I create it until the url is not duplicate.
Source Code
How to design
In this problem of leet code, some additional questions is prepared. I pick up some questions of them.
How many unique identifiers possible?
In my case, I set that the size of tiny url is 10. And the number of characters is 26 + 26 + 10 = 62 because the letters of tiny url are alphabet (both uppercase and lowercase) and numbers. So the number of unique tiny urls is 6210 ≒ 1018. One billion is 109 and the population of the world is about 7 billion.
Estimate the maximum number of URLs a single machine can store.
The capacity depends on memory and disk size of the machine. I think about the capacity to store the urls. I assume the each number blow.
- The number of urls I have to store is
one million (10^6) - The size of each url is
100 (10^2)
In this case, since the size of one character is about one byte, the size of url is about 100 byte. And there are one million urls, so the size is 108 byte = 100MB.
Java has 2GB memory so that there are enough capacity to store one million urls.
Estimate the maximum number of queries per second (QPS) for decoding a shortened URL in a single machine.
When we decode a shorted URL, split method and containsKey are executed. If the size of url is 100, this process takes O(102) time. In my java environment, O(102) process takes 102 nano time. Therefore one decode process takes 0.1 ms. So in a second, QPS is 107. (System.nanoTime())
How would you scale the service?
There are some solutions how to scale. When we use some machine to store data, we have to consider how would we distribute the data. If this service is used in all over the world, it’s effective to distribute each data by user location.
If you can enable caching, what would you cache and what’s the expiry time?
- Least Recently Used
- Least Frequently Used
２分探索木からノードを削除する Delete Node in a BST in LeetCode
問題
2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。
解法
以下のステップで解く
- 2分探索でkeyを見つける
- 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。
- 右側のサブツリーから最小値のノードを削除する
- (削除するノードのleft, rightのどちらかがnullの場合はnullではない方のサブツリーを削除するノードと置き換える)
ソースコード
【グラフ理論とネットワーク理論】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 branches to be removed to make a graph unconnected.
- Node connectivity = d → d - 1 node failures OK
- Branch connectivity = d → d - 1 branch failures OK
Theorem1
Cv(G) ≦ Ce(G) ≦ δ(G) : δ = degree (the number of branches of one node)
Damage index
Damage index is an index of the increase of hops to connect in case of failure.
α-Node(Branch) Damage Index Iα(G) (Jα(G)) is defined as blow
Maximum diameter of a graph without α nodes(branches)-Diameter of the original graph G
Design Method of Extended Complete Graph
Extended Complete Graph : Complete graph Gd → Line conversion, m times → Extended complete graph.
Lm(Gd) = L(L(…(L(G))…)) (m times)
Ex. 1
| Number of nodes | Number of branched | |
|---|---|---|
| Gd | d+1 | (d+1)d |
| L(Gd) | (d+1)d | (d+1)d2 |
| L2(Gd) | (d+1)d2 | (d+1)d3 |
Comparison
| Complete graph | Extended Complete Graph | |
|---|---|---|
| 正則性 Regularity | d-Regular | d-Regular |
Number of nodes V |
d + 1 | (d + 1)dm |
Number of branches E |
(d + 1)d | (d+1)dm+1 |
| 直径 Diameter k(G) | 1 | m+1 |
| Node connectivity Cv(G) | d | d |
| Branch connectivity Ce(G) | d | d |
| 次数 Degree δ(G) | d | d |
| 節点罹障度 Node damage index Iα(G) | 0 | ≦ m |
| 枝罹障度 Branch damage index Jα(G) | 1 | ≦ m+1 |
Throughput ratio in case of failure
k(G)/(Jα(G) + k(G)) → 0.5 for both Gd and Lm(Gd)
