一亩三分地论坛

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

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

Yelp 电面

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

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

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

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

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 會變). 1point3acres.com/bbs
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 裏面有一個
1) 一個 Array —— 用於 random generate in ...

请问有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]}
刪除第二個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. 增加就直接加到末尾。 其实有点像稠密索引。
随机就直接 table.keys()里边做random再查找值。 不会出现用array的时候删除前边的,后边的index不对的问题
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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