10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2579|回复: 25
收起左侧

google 电话本问题讨论

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

void registerNumber(String number); // 注册一个电话号码
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
应该不是用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?-google 1point3acres

补充内容 (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
Can we do with two HashMap?

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

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."
.鏈枃鍘熷垱鑷1point3acres璁哄潧
如何record unregistered numbers?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-8 02:32:59 | 显示全部楼层
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?
回复 支持 反对

使用道具 举报

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?
Even using  tries,  i think you can still randomly generate a new available phone number.鏈枃鍘熷垱鑷1point3acres璁哄潧
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
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.
回复 支持 反对

使用道具 举报

 楼主| 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. visit 1point3acres.com for more.
getAvailable就相当于产生一个random的电话号码吧

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

使用道具 举报

googlerr 发表于 2016-3-9 04:59:31 | 显示全部楼层
bobzhang2004 发表于 2016-3-9 02:57
请问这个google刷题小组是微信号还是QQ号啊

QQ群号~~~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-20 19:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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