[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1952|回复: 11
收起左侧

Yelp 电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
Primer 发表于 2014-11-26 10:39:16 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

评分

参与人数 4大米 +19 收起 理由
neomiracle + 3 感谢分享!
ycsung + 3 感谢分享!
yabay91 + 3 感谢分享!
豌豆开心果 + 10

查看全部评分


上一篇:Liveramp 电面
下一篇:Epic 电面+OA

本帖被以下淘专辑推荐:

  • · Yelp|主题: 11, 订阅: 4
我的人缘0
rwei 发表于 2015-1-9 16:02:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
這個題我 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,求人品中
回复 支持 反对

使用道具 举报

我的人缘0
harry528 发表于 2015-1-12 15:37:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼上回答的不错,不知出现duplicate如果处理?
回复 支持 反对

使用道具 举报

我的人缘0
harry528 发表于 2015-1-12 15:37:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
rwei 发表于 2015-1-9 16:02
這個題我 Twitter 的電面考過,可以建一個 class 裏面有一個
1) 一個 Array —— 用於 random generate in ...

请问有duplicate如何处理?
回复 支持 反对

使用道具 举报

我的人缘0
ycsung 发表于 2015-2-3 10:51:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
duplicate的數據insert的時候可以把HashTable的value建成list O(1), 但delete的時候要維護這個HashTable中的list似乎是要O(logn)
回复 支持 反对

使用道具 举报

我的人缘0
brian8759 发表于 2015-2-3 11:24:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ycsung 发表于 2015-2-3 10:51
duplicate的數據insert的時候可以把HashTable的value建成list O(1), 但delete的時候要維護這個HashTable中 ...

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

使用道具 举报

我的人缘0
brian8759 发表于 2015-2-3 11:25:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ycsung 发表于 2015-2-3 10:51
duplicate的數據insert的時候可以把HashTable的value建成list O(1), 但delete的時候要維護這個HashTable中 ...

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

使用道具 举报

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

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]}
回复 支持 反对

使用道具 举报

我的人缘0
shuofeng11 发表于 2016-6-17 09:56:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
rwei 发表于 2015-1-9 16:02
.1point3acres网這個題我 Twitter 的電面考過,可以建一個 class 裏面有一個
1) 一個 Array —— 用於 random generate in ...

求问为什么不能只用一个hashMap?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
shuofeng11 发表于 2016-6-24 11:48:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
penenda 发表于 2016-6-23 21:15
用一个 hashmap加一个双向链表解决吧,,hashmap存 obj:node..留学论坛-一亩-三分地
查找: 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-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-6-19 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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