一亩三分地论坛

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

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

Google 电面 7.9

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
zxy4159526 发表于 2015-7-10 05:35:49 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽
dmsehuang 发表于 2015-7-10 05:56:01 | 显示全部楼层
谢谢楼主分享。我觉得第三题用trie也可以。
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-10 05:58:44 | 显示全部楼层
谢谢楼主分享,请问楼主,什么是”返回一个不在电话本里的没人用的号码 number giveMeANumber()“ ? 给你所有电话号码的范围了吗?
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-10 06:09:05 | 显示全部楼层
LZ 能够讲讲1.2 general是改什么? 是希望code condense 还是?
回复 支持 反对

使用道具 举报

mhwkanon 发表于 2015-7-10 06:21:30 | 显示全部楼层
楼主能解释下第三题吗?如果没规定电话号码范围giveMeANumber() 只要返回hashset里最后一个值+1是不是就可以了?
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zxy4159526 发表于 2015-7-10 07:36:16 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zxy4159526 发表于 2015-7-10 07:37:11 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zxy4159526 发表于 2015-7-10 07:40:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zxy4159526 发表于 2015-7-10 07:42:12 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-10 08:30:22 | 显示全部楼层
感谢回应用BST 找vailable node >0 照LZ的方法你可以确定哪个node有valid 但要怎么决定你要选哪个? 如果brute force 找感觉o(logn) 似乎不太行? 另外这个n表示什么?
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zxy4159526 发表于 2015-7-10 09:08:54 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-10 11:17:20 | 显示全部楼层
感谢楼主分享。第三题我觉得也可以用Trie做。时间复杂度是O(L),其中L是一个电话号码的长度,其实也就是O(lgN)。这样做的好处是在号码占用率较高的情况下,会比HashMap稍微节省一点内存。

回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-10 11:43:14 | 显示全部楼层
stellari 发表于 2015-7-10 11:17
. 1point 3acres 璁哄潧感谢楼主分享。第三题我觉得也可以用Trie做。时间复杂度是O(L),其中L是一个电话号码的长度,其实也就是O(l ...

如果用trie做的话,对于第三个function  number giveMeANumber(),我们应该怎么做呢?从root开始检查任意一条路径,然后从0 到9 开始搜索,如果没有出现的数字就可以返回?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-10 12:47:02 | 显示全部楼层
UmassJin 发表于 2015-7-10 11:43
如果用trie做的话,对于第三个function  number giveMeANumber(),我们应该怎么做呢?从root开始检查任意 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我是这样想的:在每个Trie节点中,记录“从当前节点开始可使用的号码个数”nAvail:
class TrieNode{
    int nAvail;
    int curDepth;
    TrieNode* next[10];
};. 1point3acres.com/bbs
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如现在进行在搜索当中,我们已经决定了前5位号码是313-12(也就是当前所在的节点为“2”)。那么我顺次查看next[0]~next[9]。

如果这其中第next[ k ]为空,说明第6位号码只要是 k 的话,第7位以后是什么都没关系。那么我们新建一个next[ k ]节点。然后随机生成一个3位数(10-7=3),插入到next[ k ]之后;

如果所有的next都不为空,那么我们可以从中那些nAvail不为0的next中随便选一个节点。然后进入这个节点并重复之前的步骤即可。

因为next的长度恒为10,所以在这个数组上进行的线性操作都可看做O(1)时间。因此搜索完L位号码的时间是O(L)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不过回头看看,这种方法可能不如BST。一是检查每位数字虽是常数时间,但是常系数可能会较大;二是上面的这种用数组的implementation不仅没有省内存,而且还费了不少内存,因为最后一层总共有10^10个节点,每个节点有10个next,这些全为空值的next占据了10^11量级的内存。
. 1point3acres.com/bbs
另外就算是用BST存的话,每个节点处也需要储存号码(32位整数)+左右指针(假设各32位)= 12 byte。最后总共需要12 x 10^10 = 120G内存,很可能放不到一台机器里。如果再跟面试官扯扯这时候如何处理的话,说不定会有加分。
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-10 13:00:40 | 显示全部楼层
stellari 发表于 2015-7-10 12:47. from: 1point3acres.com/bbs
我是这样想的:在每个Trie节点中,记录“从当前节点开始可使用的号码个数”nAvail:
class TrieNode{
   ...

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 谢谢大神的分析!想的好全面! 有一点,在建立每个Trie的Node的时候,如果我们不是用 TrieNode* next[10], 我们仅仅保存已经用的数字,比如用一个hashmap保存用过的数字{'1': TrieNode(1), '2': TrieNode(2)...} 这样我们是不是可以节省一些内存空间?求指教。
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-10 13:17:36 | 显示全部楼层
stellari 发表于 2015-7-10 12:47
我是这样想的:在每个Trie节点中,记录“从当前节点开始可使用的号码个数”nAvail:
class TrieNode{. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   ...

-0- judy array难道是你写的...
回复 支持 反对

使用道具 举报

Nevermindeaf 发表于 2015-7-10 13:21:39 | 显示全部楼层
第三题我也被面过,用的是Trie w/ boolean array, 不用Hashmap是因为 map的initial size是256,对于这种只需要存0-9十个数的情况就很不划算了, 用trie只需要存每层0-9十个boolean,如果这个数已用就把 相应的index set一下

补充内容 (2015-7-10 13:44):. more info on 1point3acres.com
用boolean array更省地方,因为boolean 只是一个bit,int 是8个
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-10 13:47:44 | 显示全部楼层
UmassJin 发表于 2015-7-10 13:00
谢谢大神的分析!想的好全面! 有一点,在建立每个Trie的Node的时候,如果我们不是用 TrieNode* next[10] ...

用hash map估计耗内存更多。比如创建一个空hash map,里面看起来好像没有东西,但是底层其实有一个数组存在,而且大小并不是0。如果hash map中有10个元素,那么底层数组通常都大于10。这样反而比array更费内存了。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
------------------------------------------------------

刚刚想到是不是还可以这样:

维护一个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)

*这个Map到LinkedList的技巧比较类似于LRU Cache那道题。
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-10 13:47:51 | 显示全部楼层
Nevermindeaf 发表于 2015-7-10 13:21
第三题我也被面过,用的是Trie w/ boolean array, 不用Hashmap是因为 map的initial size是256,对于这种只 ...

java boolean多大???? 请google...
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-10 13:48:34 | 显示全部楼层
stellari 发表于 2015-7-10 13:47
用hash map估计耗内存更多。比如创建一个空hash map,里面看起来好像没有东西,但是底层其实有一个数组存 ...

overhead 更大....
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 18:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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