一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1794|回复: 25
收起左侧

google 电话本问题讨论

[复制链接] |试试Instant~ |关注本帖
bobzhang2004 发表于 2016-3-6 13:07:28 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - HR筛选 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
google 一道常考的电话本问题,希望开贴能够将这个题一起解决"要求实现一个北美电话号码的分配系统,即10位的电话号码的注册、注销和查询。有如下的API:. 1point 3acres 璁哄潧

void registerNumber(String number); // 注册一个电话号码. from: 1point3acres.com/bbs
void unregisterNumber(String number); // 注销一个电话号码. 鍥磋鎴戜滑@1point 3 acres
boolean isNumberRegistered(String number); // 查询一个电话号码的注册状态
String getAvailableNumber(); // 返回任意一个可用号码"
我觉得应该用Hashmap比较直接。如果用trie的话,随机产生会比较麻烦,还有就是注销也比较麻烦。

评分

1

查看全部评分

kittycerry 发表于 2016-3-6 17:20:02 | 显示全部楼层
应该不是用hash map吧?用hash map的话,你还用特意拿出来说么?
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-7 02:02:14 | 显示全部楼层
kittycerry 发表于 2016-3-6 17:20.1point3acres缃
应该不是用hash map吧?用hash map的话,你还用特意拿出来说么?

是啊,应该不是,hashmap只是开始可以说说而已
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-3-7 02:40:13 | 显示全部楼层
要考虑区号么?如果考虑,我觉得可以用map<string, List<string>> 结构, key是3位区号,List是sorted,但是随机产生不知道怎么做。。期待大牛解答。
回复 支持 反对

使用道具 举报

liuyifly06 发表于 2016-3-7 02:50:15 | 显示全部楼层
Can we do with two HashMap?

补充内容 (2016-3-7 02:51):
The first HashMap record registered numbers. The second HashMap record unregistered numbers. Such that all these four function can be implemented in O(1)
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-7 02:56:50 | 显示全部楼层
liuyifly06 发表于 2016-3-7 02:50.鏈枃鍘熷垱鑷1point3acres璁哄潧
Can we do with two HashMap?

补充内容 (2016-3-7 02:51):
. 1point 3acres 璁哄潧
hashmap应该可以做成,但是不知道有没有更好的办法
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-7 03:27:51 | 显示全部楼层
我是没看出来有什么特殊的地方,难道不是hashmap么?为什么要讨论?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-8 02:32:06 | 显示全部楼层
liuyifly06 发表于 2016-3-7 02:50. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Can we do with two HashMap?

补充内容 (2016-3-7 02:51):

"The second HashMap record unregistered numbers."

如何record unregistered numbers?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-8 02:32:59 | 显示全部楼层
liuyifly06 发表于 2016-3-7 02:50-google 1point3acres
Can we do with two HashMap?. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-3-7 02:51):

"The second HashMap record unregistered numbers."

如何record unregistered numbers?
回复 支持 反对

使用道具 举报

matata 发表于 2016-3-8 02:55:48 | 显示全部楼层
可以用HashSet<String>吗?  返回任意可用号码,对号码有要求吗? 随机生成一个十位数,看在HashSet里存不存在,这样可以吗?
回复 支持 反对

使用道具 举报

liuyifly06 发表于 2016-3-8 03:23:42 | 显示全部楼层
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).
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-8 05:26:24 | 显示全部楼层
liuyifly06 发表于 2016-3-8 03:23
What I was saying is that initialize second Hash Map (unregistered numbers) with 000-000-0000 to 9 ...

这样的话,内存会不会太大了?
回复 支持 反对

使用道具 举报

liuyifly06 发表于 2016-3-8 06:10:50 | 显示全部楼层
googlerr 发表于 2016-3-8 05:26
这样的话,内存会不会太大了?

yes~ indeed. A lot of memory ...
回复 支持 反对

使用道具 举报

say543 发表于 2016-3-8 15:50:31 | 显示全部楼层
Inspired by two-hashMap solution,  maybe two-tries solution  is possible since it can reduce memory usage?.鏈枃鍘熷垱鑷1point3acres璁哄潧
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.



回复 支持 反对

使用道具 举报

say543 发表于 2016-3-8 15:50:47 | 显示全部楼层
liuyifly06 发表于 2016-3-8 06:10. from: 1point3acres.com/bbs
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. From 1point 3acres bbs
Repeating the same procedure then you you get a phone number.
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-8 23:11:41 | 显示全部楼层
题目没有说要randomly 产生电话表,trie可以省内存,返回时任意返回一个即可
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-9 00:21:49 | 显示全部楼层
bobzhang2004 发表于 2016-3-8 23:11
题目没有说要randomly 产生电话表,trie可以省内存,返回时任意返回一个即可

getAvailable就相当于产生一个random的电话号码吧
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-9 02:57:34 | 显示全部楼层
googlerr 发表于 2016-3-9 00:21
getAvailable就相当于产生一个random的电话号码吧

请问这个google刷题小组是微信号还是QQ号啊
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-9 04:59:31 | 显示全部楼层
bobzhang2004 发表于 2016-3-9 02:57
请问这个google刷题小组是微信号还是QQ号啊
. 1point3acres.com/bbs
QQ群号~~~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 19:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表