google 电话本问题讨论

googlerr 发表于 2016-3-8 02:32
"The second HashMap record unregistered numbers."

如何record unregistered numbers？

What I was saying is that initialize second Hash Map (unregistered numbers) with 000-000-0000 to 999-999-9999. Whenever you add a number to the first Hash Map(registered numbers), delete the corresponding key in the second Hash Map.

Without second Hashmap, I just have no idea how you can find an unregistered number in O(1).

liuyifly06 发表于 2016-3-8 03:23
What I was saying is that initialize second Hash Map (unregistered numbers) with 000-000-0000 to 9 ...

这样的话，内存会不会太大了？

googlerr 发表于 2016-3-8 05:26
这样的话，内存会不会太大了？

yes~ indeed. A lot of memory ...

Inspired by two-hashMap solution,  maybe two-tries solution  is possible since it can reduce memory usage?
Even using  tries,  i think you can still randomly generate a new available phone number
with tries, you can know how many available digits for one number
Repeating the same procedure then you you get a phone number.

liuyifly06 发表于 2016-3-8 06:10
yes~ indeed. A lot of memory ...

Inspired by two-hashMap solution,  maybe two-tries solution  is possible since it can reduce memory usage?
Even using  tries,  i think you can still randomly generate a new available phone number
with tries, you can know how many available digits for one number
Repeating the same procedure then you you get a phone number.

题目没有说要randomly 产生电话表，trie可以省内存，返回时任意返回一个即可

bobzhang2004 发表于 2016-3-8 23:11
题目没有说要randomly 产生电话表，trie可以省内存，返回时任意返回一个即可

getAvailable就相当于产生一个random的电话号码吧

googlerr 发表于 2016-3-9 00:21
getAvailable就相当于产生一个random的电话号码吧

请问这个google刷题小组是微信号还是QQ号啊

bitmap?

bobzhang2004 发表于 2016-3-9 02:57
请问这个google刷题小组是微信号还是QQ号啊

QQ群号~~~