https://gist.github.com/gcrfelix/b84e173c83d4f79068a4
设计一个电话本系统，实现三个功能：
查找号码 boolean isTaken()，
添加号码 void takeNumber()，
返回一个不在电话本里的没人用的号码 number giveMeANumber()。
==> random, reservoir sampling
用的是Trie and boolean array, 不用Hashmap是因为 map的initial size是256，对于这种只需要存0-9十个数的情况就很不划算了
用trie只需要存每层0-9十个boolean,如果这个数已用就把相应的index set一下
用boolean array更省地方，arrays of booleans use 1 byte per element
Search Time Complexity: O(length of phone number)
Insert Time Complexity: O(length of phone number)
public class Numbers{
Node root;
public Numbers(){
root=new Node();
}
}
class Node{
boolean[] children;
public Node(){
children=new boolean[10];
}
}
http://sudhansu-codezone.blogspot.com/2012/09/phone-book-data-structure.html
Using a Trie can help you on that and the time will be O(L) where L is the string length.
1) input name and find phone number
-- Trie structure for name (string), phone number as assocaited value.
-- Or hashtable (name as hash key), and link list as chaining (for name duplicatiion)
2) input phone number and find name
-- hash table
(phone number is unique, so use as hash key)
The great thing about a trie is that it would provide functionality to easily facilitate partial searches, you type in the start of the persons name or phone number and you could return all leaf nodes that match that that prefix. Insertion and search will take O(length of phone number). To display the numbers starting with one or more digits, then the complexity will be the O(prefix length)+O(number of children for the immediate prefix node * length of the remaining number from child nodes).
https://instant.1point3acres.com/thread/131215/posts?ps=
Use too much space.
维护一个HashSet taken，其中是已被占用的号码；另外维护一个LinkedHashMap untaken。其中是未被占用的号码，它由两部分组成：
Doubly Linked List： (num1) <-> (num2) <-> (num3) <-> … <-> (numN)
HashMap: {num1: &(num1), num2: &(num2), …}即将数字映射成到链表节点的指针。
isTaken(): 可以简单地通过查询taken得到。O(1)
takeNumber(n): 可以从HashMap中找到n，和其对应的链表节点Node，从链表和HashMap中分别删除Node和n，以上都是O(1)操作。然后将n加入taken，这步也是O(1)。总时间O(1)。另一方面，如果n不在untaken中，也可以用O(1)时间获知。
giveMeANumber(); pop出List的第一个即可。同样是O(1)
https://codingarms.wordpress.com/2015/05/01/design-a-data-structure-to-implement-a-phone-book-can-search-by-name-or-number/
设计一个电话本系统，实现三个功能：
查找号码 boolean isTaken()，
添加号码 void takeNumber()，
返回一个不在电话本里的没人用的号码 number giveMeANumber()。
==> random, reservoir sampling
用的是Trie and boolean array, 不用Hashmap是因为 map的initial size是256，对于这种只需要存0-9十个数的情况就很不划算了
用trie只需要存每层0-9十个boolean,如果这个数已用就把相应的index set一下
用boolean array更省地方，arrays of booleans use 1 byte per element
Search Time Complexity: O(length of phone number)
Insert Time Complexity: O(length of phone number)
public class Numbers{
Node root;
public Numbers(){
root=new Node();
}
}
class Node{
boolean[] children;
public Node(){
children=new boolean[10];
}
}
http://sudhansu-codezone.blogspot.com/2012/09/phone-book-data-structure.html
Using a Trie can help you on that and the time will be O(L) where L is the string length.
1) input name and find phone number
-- Trie structure for name (string), phone number as assocaited value.
-- Or hashtable (name as hash key), and link list as chaining (for name duplicatiion)
2) input phone number and find name
-- hash table
(phone number is unique, so use as hash key)
The great thing about a trie is that it would provide functionality to easily facilitate partial searches, you type in the start of the persons name or phone number and you could return all leaf nodes that match that that prefix. Insertion and search will take O(length of phone number). To display the numbers starting with one or more digits, then the complexity will be the O(prefix length)+O(number of children for the immediate prefix node * length of the remaining number from child nodes).
https://instant.1point3acres.com/thread/131215/posts?ps=
Use too much space.
维护一个HashSet taken，其中是已被占用的号码；另外维护一个LinkedHashMap untaken。其中是未被占用的号码，它由两部分组成：
Doubly Linked List： (num1) <-> (num2) <-> (num3) <-> … <-> (numN)
HashMap: {num1: &(num1), num2: &(num2), …}即将数字映射成到链表节点的指针。
isTaken(): 可以简单地通过查询taken得到。O(1)
takeNumber(n): 可以从HashMap中找到n，和其对应的链表节点Node，从链表和HashMap中分别删除Node和n，以上都是O(1)操作。然后将n加入taken，这步也是O(1)。总时间O(1)。另一方面，如果n不在untaken中，也可以用O(1)时间获知。
giveMeANumber(); pop出List的第一个即可。同样是O(1)
https://codingarms.wordpress.com/2015/05/01/design-a-data-structure-to-implement-a-phone-book-can-search-by-name-or-number/
