没结婚也能买房啊!大波士顿地区买房小tips

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 1932|回复: 11
收起左侧

Yelp 电面

[复制链接] |试试Instant~ |关注本帖
Primer 发表于 2014-11-26 10:39:16 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 本科 全职@ - 网上海投 - 技术电面  | Other |

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

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

x
刚面完,攒个rp发下面经,感觉没答好
设计一个数据结构,要求支持插入,删除和random返回一个元素这三种操作,每种操作的复杂度都要是O(1)

followup是如果要支持duplicate数据怎么办(这个想复杂了没写完),求bless

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Yelp|主题: 11, 订阅: 4
rwei 发表于 2015-1-9 16:02:58 | 显示全部楼层
這個題我 Twitter 的電面考過,可以建一個 class 裏面有一個
1) 一個 Array —— 用於 random generate index 後 O(1) access element
2) HashTable(dict in Python),key 是要添加的 element,value 是那個 element 在 Array 裏面的 Index —— 用於通過 object 來 O(1) 作刪除操作。

put:
將 object 添加到 HashTable 中,同時 append 到 Array 的最後
delete:
通過 passed in 的 object 找到它在 Array 中的位置,將 Array 的最後一個 element 移到剛 delete 的 Index 然後把 object 從 HashTable 刪除,並 update HashTable 裏面剛改動過的 Index (被 move 的 Array 最後那個 element 的 Index 會變). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
get_random:
index = int(random() * len(hash_table)) # random function 是 Python 自帶的,返回 [0, 1) 之間的小數
return array[index]

以上所有操作都是 O(1) 的

p.s. 前天剛面完 Yelp 的 full time onsite,求人品中
回复 支持 反对

使用道具 举报

harry528 发表于 2015-1-12 15:37:03 | 显示全部楼层
楼上回答的不错,不知出现duplicate如果处理?
回复 支持 反对

使用道具 举报

harry528 发表于 2015-1-12 15:37:27 | 显示全部楼层
rwei 发表于 2015-1-9 16:02
這個題我 Twitter 的電面考過,可以建一個 class 裏面有一個.鏈枃鍘熷垱鑷1point3acres璁哄潧
1) 一個 Array —— 用於 random generate in ...
. 1point3acres.com/bbs
请问有duplicate如何处理?
回复 支持 反对

使用道具 举报

ycsung 发表于 2015-2-3 10:51:30 | 显示全部楼层
duplicate的數據insert的時候可以把HashTable的value建成list O(1), 但delete的時候要維護這個HashTable中的list似乎是要O(logn)
回复 支持 反对

使用道具 举报

brian8759 发表于 2015-2-3 11:24:48 | 显示全部楼层
ycsung 发表于 2015-2-3 10:51
duplicate的數據insert的時候可以把HashTable的value建成list O(1), 但delete的時候要維護這個HashTable中 ...

如果有 duplicate,那删除的时候,是随机删一个 duplicate 么?
delete 操作为什么是 O(log n)?
回复 支持 反对

使用道具 举报

brian8759 发表于 2015-2-3 11:25:01 | 显示全部楼层
ycsung 发表于 2015-2-3 10:51
duplicate的數據insert的時候可以把HashTable的value建成list O(1), 但delete的時候要維護這個HashTable中 ...

如果有 duplicate,那删除的时候,是随机删一个 duplicate 么?
delete 操作为什么是 O(log n)?
回复 支持 反对

使用道具 举报

ycsung 发表于 2015-2-4 05:44:05 | 显示全部楼层
我不確定是要隨機一個還是全部的
但是刪除的時候, 要update dic中的list, 應該需要挑最大的index去update, 做這個動作需要O(logn). 我目前只想到這個方法, 有更好的解麻煩告知一下.

Data: [3, 3, 4, 4] {3: [0, 1], 4: [2, 3]}
刪除第一個3: [3, 4, 4] {3: [0], 4: [2, 1]}. Waral 鍗氬鏈夋洿澶氭枃绔,
刪除第二個3: [4, 4] {4: [0, 1]}
假設沒有挑4最大的index, 而只是pop()最後一個的話
會錯誤: [4, 4] {4: [2, 0]}
回复 支持 反对

使用道具 举报

shuofeng11 发表于 2016-6-17 09:56:13 | 显示全部楼层
rwei 发表于 2015-1-9 16:02
這個題我 Twitter 的電面考過,可以建一個 class 裏面有一個
1) 一個 Array —— 用於 random generate in ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求问为什么不能只用一个hashMap?
回复 支持 反对

使用道具 举报

penenda 发表于 2016-6-23 21:15:26 | 显示全部楼层
用一个 hashmap加一个双向链表解决吧,,hashmap存 obj:node.
查找: obj->node。 删除 obj->node. remove. 增加就直接加到末尾。 其实有点像稠密索引。-google 1point3acres
随机就直接 table.keys()里边做random再查找值。 不会出现用array的时候删除前边的,后边的index不对的问题
回复 支持 反对

使用道具 举报

shuofeng11 发表于 2016-6-24 11:48:21 | 显示全部楼层
penenda 发表于 2016-6-23 21:15
用一个 hashmap加一个双向链表解决吧,,hashmap存 obj:node..1point3acres缃
查找: obj->node。 删除 obj->node. remov ...

只用一个hashTable不用linkedList也可以实现insert, search,random access都是O(1)的复杂度吗?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-388663-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-21 02:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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