Insert Delete GetRandom O(1) - Duplicates allowed

問題

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

leetcode.com

ソースコード

Insert Delete GetRandom O(1)

問題

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

leetcode.com

解法

HashMapとArrayListを用いることで解くことができる。問題はノードを削除する時だが、ArrayListからIndexを指定して要素を削除する場合、削除した分だけ要素をシフトさせる必要があるため、O(1)を実現できない。そこで以下の方法を取る。

  1. 削除したい要素のIndexを取得
  2. ArrayList内で最後の要素とIndexの要素をSwap
  3. ArrayListの最後の要素を削除(シフトさせる必要が無くなる)

ソースコード

Add One Row to Tree

問題

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

leetcode.com

ソースコード

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

結果

僕の環境では以下の値となった。言語はJava

  • 空間計算量O(N)とすると実際の使用容量はN byte程度
  • 時間計算量O(10x) とすると、10-1*(9-x) 秒程度

※オーダーの値が小さいと誤差は出る

Javaのメモリーサイズ

Javaのメモリーサイズはメソッドによって取得することができる。

Runtime (Java Platform SE 6)

maxMemoryとは、使用メモリーがtotalMemoryに近づいた時に、更にメモリーの使用を試みる値となる。

maxMemoryは大体2GBであることが分る。

空間計算量

Int型の整数1つのバイト数は1バイトとなる。つまり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 → 2秒弱
  • 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 62101018. 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

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

問題

2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。

leetcode.com

解法

以下のステップで解く

  1. 2分探索でkeyを見つける
  2. 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。
  3. 右側のサブツリーから最小値のノードを削除する
  4. (削除するノードのleft, rightのどちらかがnullの場合はnullではない方のサブツリーを削除するノードと置き換える)

f:id:atiek1121:20170613091118p:plain

ソースコード

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

問題

leetcode.com

解法

単純にfor文を用いた解法だとO(√N)となり間に合わない。 2文探索を用いることでO(logN)で解くことができる。

ソースコード