一亩三分地论坛

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

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

G家电面

[复制链接] |试试Instant~ |关注本帖
refurbish 发表于 2015-3-4 03:05:31 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 博士 全职@Google - 内推 - 技术电面 |Other

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

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

x
感觉稀里糊涂的,问了一个现在工作的问题,就接着问了一个coding的题目:
实现一个Map,带有getRandomValue的方法,要求所有put,get,remove,getRandomValue都必须是O(1)

在其中一个关键细节上卡了将近20分钟,中间面试官各种提示都没点醒问我,最后25分钟左右搞定,但是好像和面试官的思路还是不一样。面试官没有再问其他问题,不知道是不是因为我太慢了。




.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-3-4 15:10):
刚收到消息,pass了

评分

1

查看全部评分

tonywen2014 发表于 2015-3-4 03:07:55 | 显示全部楼层
楼主请问,getRandomValue 是取Value set里面的任意一个值?
回复 支持 反对

使用道具 举报

 楼主| refurbish 发表于 2015-3-4 03:09:32 | 显示全部楼层
tonywen2014 发表于 2015-3-4 03:07
楼主请问,getRandomValue 是取Value set里面的任意一个值?

对的,比如:
(1, "a")
(2, "b"). 1point3acres.com/bbs
(3, "c")
. more info on 1point3acres.com
要随机的返回a, b, c中一个
回复 支持 反对

使用道具 举报

fsc111 发表于 2015-3-7 12:41:19 | 显示全部楼层
refurbish 发表于 2015-3-4 03:09
对的,比如:
(1, "a")
(2, "b")

楼主 请问你后来想出来O(1)的解法了吗,能提示下吗?
回复 支持 反对

使用道具 举报

dsq704136 发表于 2015-3-7 15:10:33 | 显示全部楼层
可以直接用HashMap实现Get, Put, Remove。用一个额外的Array去实现getRandom。
回复 支持 反对

使用道具 举报

 楼主| refurbish 发表于 2015-3-7 17:13:18 | 显示全部楼层
fsc111 发表于 2015-3-7 12:41
楼主 请问你后来想出来O(1)的解法了吗,能提示下吗?

楼上的回复是很好的提示,我的做法略有不同,因为我当时想着要不受固定大小的限制,我多用了两个hash table来保存int和key之间的映射关系,另外用了一个counter来记录当前最后一个插入的key。不过最tricky的地方是remove的实现,因为会导致使用的int序列不连续。
回复 支持 反对

使用道具 举报

fsc111 发表于 2015-3-9 03:33:02 | 显示全部楼层
refurbish 发表于 2015-3-7 17:13
楼上的回复是很好的提示,我的做法略有不同,因为我当时想着要不受固定大小的限制,我多用了两个hash tab ...

果然index不连续的话,怎么实现随机呢?
回复 支持 反对

使用道具 举报

timtam85 发表于 2015-3-9 11:35:50 | 显示全部楼层
career cup有人讨论这题. 1point 3acres 璁哄潧
http://www.careercup.com/question?id=11353907. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

 楼主| refurbish 发表于 2015-3-9 12:37:39 | 显示全部楼层
fsc111 发表于 2015-3-9 03:33
果然index不连续的话,怎么实现随机呢?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
删除的时候,把对应的整数索引和最大的索引所映射的key对换,然后最大的整数索引减一保存
回复 支持 反对

使用道具 举报

smallsimple 发表于 2015-3-9 23:08:36 | 显示全部楼层
refurbish 发表于 2015-3-9 12:37. more info on 1point3acres.com
删除的时候,把对应的整数索引和最大的索引所映射的key对换,然后最大的整数索引减一保存
. Waral 鍗氬鏈夋洿澶氭枃绔,
请教楼主,对换key之前要先找到要删除的key的索引,这个找的过程是O(n)吧?不知道是怎么实现的?我假设楼用了array保存key?
回复 支持 反对

使用道具 举报

 楼主| refurbish 发表于 2015-3-9 23:10:56 | 显示全部楼层
smallsimple 发表于 2015-3-9 23:08
请教楼主,对换key之前要先找到要删除的key的索引,这个找的过程是O(n)吧?不知道是怎么实现的?我假设楼 ...

所以我用了两个hash table来保存<int, key>和<key, int>,我没用数组
回复 支持 反对

使用道具 举报

smallsimple 发表于 2015-3-9 23:46:43 | 显示全部楼层
refurbish 发表于 2015-3-9 23:10
所以我用了两个hash table来保存和,我没用数组

哦,原来如此。多谢楼主。
回复 支持 反对

使用道具 举报

suonan 发表于 2015-3-10 04:28:31 | 显示全部楼层
不受固定大小的限制指的是什么呢?楼主的方法用了三个hashmap感觉空间开销已经不小了吧。。
回复 支持 反对

使用道具 举报

 楼主| refurbish 发表于 2015-3-10 16:10:31 | 显示全部楼层
suonan 发表于 2015-3-10 04:28
不受固定大小的限制指的是什么呢?楼主的方法用了三个hashmap感觉空间开销已经不小了吧。。

如果用array来保存key的话,当key数目超过初始申请的array的大小后,就得新申请空间吧,如果自己写这部分代码,无疑增加了复杂度。我是为了避免这个,采用hash table的,另外用array还得用另一个hash table,因为需要根据key找到对应的整数索引,否则就是O(n)的查找。三个hash table的空间开销也是O(n),不是这个问题的重点吧。
回复 支持 反对

使用道具 举报

daniel.kong 发表于 2015-4-13 14:32:40 | 显示全部楼层
厉害!         
回复 支持 反对

使用道具 举报

独孤辰涛 发表于 2015-4-14 11:36:26 | 显示全部楼层
refurbish 发表于 2015-3-4 03:09
对的,比如:
(1, "a")
(2, "b")

请教lz,如果某些vaule出现的次数比较多呢?那么这个value是否有更高的概率出现在你的返回值里?比如说(1:“a”), (2,"a") (3,"a"), (4,"b"),那么a的概率是3/4还是1/2呢?
回复 支持 反对

使用道具 举报

独孤辰涛 发表于 2015-4-14 11:56:21 | 显示全部楼层
refurbish 发表于 2015-3-10 16:10. Waral 鍗氬鏈夋洿澶氭枃绔,
如果用array来保存key的话,当key数目超过初始申请的array的大小后,就得新申请空间吧,如果自己写这部分 ...

有一个小优化不知道能不能算。可否通过把id 也存入 key:value 对中来减少space开销,这样就可以少用一个hashmap. 用一个wrapper class 把user data 和 id包在一起。
回复 支持 反对

使用道具 举报

cedar 发表于 2015-4-15 23:00:58 | 显示全部楼层
dsq704136 发表于 2015-3-7 15:10
可以直接用HashMap实现Get, Put, Remove。用一个额外的Array去实现getRandom。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
用额外array的话 remove 就会受影响 怎么做到remove from Map and array 都是O(1)呢
回复 支持 反对

使用道具 举报

shou3301 发表于 2015-4-16 00:18:24 | 显示全部楼层
恭喜lz,再接再厉啊!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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