一亩三分地论坛

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

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

Amazon 极品面经,貌似又被阿三黑了

[复制链接] |试试Instant~ |关注本帖
tianchijushi 发表于 2016-3-9 08:26:07 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Amazon - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
楼主刚刚结束了Amazon的第二轮电面,运气不好这次面试官是个印度经理。前两道题中规中矩,要实现intersection of two array, 和Find all the numbers which appear odd number of times. 第二题面试官要求用O(1)的space找到所有出现odd次数的数值,楼主说如果只要找到一个可以用异或,但面试官坚持要用O(1)实现。最后楼主说没有这样的方法,面试官似乎同意了问了我mapreduce怎么样,我说mapreduce的worst case也是O(N), 面试官似乎同意了。
最极品的来了,面试官要我实现一个data structure,要求get,add, delete, getrandom的时间都是O(1), 楼主写了一个hashmap的实现方法,arraylist of linkedlist, 面试官说这个是平均时间,不是worst cast。然后要求我实现一个如果所有元素的hashcode都相同,也要O(1)的时间实现。楼主觉得没有这样一种数据结构能够worst case也是O(1)时间实行这些操作,然后三哥坚持说有,最后时间到了就面试结束了,楼主问了一下面试官这个该怎么实现,三哥不说,楼主又问了他确认有这种方法吗,印度小哥确定说有。个人觉得是被黑了,不知道地里同学们怎么觉得。lz在想要不要给hr发个邮件反映下情况,即使不行也得做点什么,求意见,求安慰

评分

2

查看全部评分

snakefly 发表于 2016-3-9 09:52:14 | 显示全部楼层
hashcode相同不就回归到链表了吗。。。。怎么O(1)

占个位听大神解读
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2016-3-9 10:29:36 | 显示全部楼层
snakefly 发表于 2016-3-9 09:52. visit 1point3acres.com for more.
hashcode相同不就回归到链表了吗。。。。怎么O(1)

占个位听大神解读

就是不行,印度面试官让设计一种所有hashcode都相同情况还能O(1)时间的结构,就无语了
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-3-9 11:03:01 | 显示全部楼层
这道题是经典题,LZ刷题刷的不够啊。。。这个是hashtable + arrayList . 1point3acres.com/bbs
参见这个
http://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-3-9 11:23:05 | 显示全部楼层
第二题sort就可以o1 space吧,不过时间复杂度就上去了
回复 支持 反对

使用道具 举报

jixiang719 发表于 2016-3-9 11:48:42 | 显示全部楼层
zxl9171 发表于 2016-3-9 11:03. from: 1point3acres.com/bbs
这道题是经典题,LZ刷题刷的不够啊。。。这个是hashtable + arrayList
参见这个
http://stackoverflow.c ...

层主见多识广,请收下我的膝盖。。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-3-9 11:58:21 | 显示全部楼层
zxl9171 发表于 2016-3-9 11:03
这道题是经典题,LZ刷题刷的不够啊。。。这个是hashtable + arrayList
参见这个
http://stackoverflow.c ...

我不太懂,这个能实现如果所有元素的hashcode都相同,也要O(1)的时间实现么?
回复 支持 反对

使用道具 举报

aloncgo 发表于 2016-3-9 12:08:32 | 显示全部楼层
zxl9171 发表于 2016-3-9 11:03
这道题是经典题,LZ刷题刷的不够啊。。。这个是hashtable + arrayList .1point3acres缃
参见这个
http://stackoverflow.c ...

但要是所有元素hashcode都相同这也太奇葩了。。。   所有元素hashcode都相同的话  hashtable自身就不是O(n)了啊

补充内容 (2016-3-9 12:08):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
打错了。。。不是O1
回复 支持 反对

使用道具 举报

ruokua 发表于 2016-3-9 12:20:34 | 显示全部楼层
这个是可以做到amortize O(1)的
但是讲真 即使Hashcode 都不一样 如果hashtable到了load factor的时候resize 那时候也就不是O(1)了. From 1point 3acres bbs

被黑了argue也没什么用 我还被问过O(1)find max in an array呢 还是一个中国人问的?

补充内容 (2016-3-9 12:35):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个是可以做到amortize O(1)的 就像楼主想的那个方法一样
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-3-9 12:28:40 | 显示全部楼层
感觉是被坑了......再怎么也不敢说worst case o(1)啊,hashmap lookup的worst case都不是o(1)
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2016-3-9 13:15:30 | 显示全部楼层
william_gong 发表于 2016-3-9 11:23
第二题sort就可以o1 space吧,不过时间复杂度就上去了

不可以sort啊,sort最早说了,面试官貌似想问map reduce,然后我解释了map reduce也不能O(1)
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-9 14:11:03 | 显示全部楼层
tianchijushi 发表于 2016-3-9 13:15
不可以sort啊,sort最早说了,面试官貌似想问map reduce,然后我解释了map reduce也不能O(1)

这题能具体说说吗?谢谢啊
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2016-3-9 15:58:53 | 显示全部楼层
Sendoh2015 发表于 2016-3-9 14:11
这题能具体说说吗?谢谢啊

给你一串array的int,找出所有出现奇数次的元素,要求O(N)时间基础上用O(1)space实现,至今没想出方法
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2016-3-10 15:31:51 | 显示全部楼层
lz给hr发了邮件,没有回复,应该是被黑了
回复 支持 反对

使用道具 举报

xiaohui5319 发表于 2016-10-19 03:18:35 | 显示全部楼层
三哥太恶心了,绝逼被黑了
回复 支持 反对

使用道具 举报

nicholaszys 发表于 2016-10-19 05:49:15 | 显示全部楼层
LC381,LZ可以看一下。这题虽然经典但是其实没做过的感觉超级难。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 19:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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