一亩三分地论坛

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

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

12.18 Amazon Onsite

[复制链接] |试试Instant~ |关注本帖
Freetymekiyan 发表于 2014-12-19 15:35:41 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 全职@Amazon - 校园招聘会 - Onsite |Other

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

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

x
今天刚去了Amazon Onsite,总体感觉不怎么样。发下面经给大家参考,顺便攒攒人品!

第一轮,烙印Manager带一个埃及的小弟学习。上来随便扯几句直接LevelOrderZigZagTraversal,LeetCode原题。follow up问我为什么用ArrayList不用Queue等等的问题,感觉烙印太潇洒飘逸了,没怎么hold住…


第二轮,白人高个大胡子geek,连吃Pizza的时候开的玩笑都是找最好吃的口味要O(n)…LRU Cache,不要求直接写代码,一步步讨论实现。会反复问“你觉得自己的代码没有问题了吗”,没看出来就举个example引导,压力略大的…

. From 1point 3acres bbs
第三轮,坑爹的黄眼镜儿白人,不知道哪儿的口音,一进来就问问题,问的题目之前也没见过。给你一个.csv文件,每个entry有employer name, employer ssn, manager name, manager ssn, employer title几个属性,给一个FileIterator来读取每条entry,给一个Person class,里面有String name, String ssn, String title和List<Person> reports(向这个人汇报的所有人),要求用某种数据结构存这些个entry,然后在里面找谁是CEO。哪位大大给分析下这道题具体怎么做?. 鍥磋鎴戜滑@1point 3 acres
.1point3acres缃

第四轮,nice的白人大叔,响应非常及时。题目是简单的给一个Integer Array,返回一个duplicate,加上各种follow up,比如ArrayList的contains怎么实现的,换成什么其他数据结构比较好,hash function怎么实现,hash collision怎么解决,不用extra space怎么办,Array里面有一百万个元素怎么改,返回所有的duplicates怎么写等等。


所有的Interviewer全都来自AWS的各个不同team,基本都在中午吃pizza的地方出现过。吐槽一下,Amazon的Pizza真心是我来美国之后吃过最难吃的,没有之一!今天应该是节前的最后一波,这星期完后再没面试了。祝今天一起Interview的几位都能顺利拿到offer!我算是帮大家踩坑了,不做很大的指望…
. from: 1point3acres.com/bbs
接下来会分享Google OA的两道题目。求人品,求赏米!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


补充内容 (2014-12-19 18:45):
另外补充一下,除了有一个人跟我题目一模样,其他同一天面试的人还碰到了Two Sum,设计停车场的OOD(是妹子),总体感觉简单. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

建议接下来面Amazon的朋友们还是稍稍准备一下OOD

评分

3

查看全部评分

juliusjun 发表于 2015-7-20 09:44:56 | 显示全部楼层
MichaelYC 发表于 2015-7-19 23:19. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
好问题。我觉得这样的话就要和面试官讨论,到底 CEO 的定义是什么?如果 CEO 是接受很多汇报的人,那么这 ...

我已经懂了,其实就是Celebrity Problem。O(n). 论坛里其他人也被问过同样的题目
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-7-20 12:02:13 | 显示全部楼层
CEO那个题和Celebrity很像,但是可能的不同之处在于:Celebrity问题中的所有人都直接认识Celebrity,但是CEO问题中大部分人应该是不直接向CEO汇报的。而且CEO问题的Graph中一般情况下是无环的(一般不会有循环汇报这种情况吧?)。. 1point3acres.com/bbs

我觉得可以这样: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

维护两个HashSet: notCEO, maybeCEO. 其中分别存放“不可能/有可能是CEO的Person对象的引用”.鏈枃鍘熷垱鑷1point3acres璁哄潧

每读一条record,按下列规则执行:
如果Employee在maybeCEO中,那么将其移到notCEO中去。
如果Employee在notCEO中,那么不做任何事;
如果Employee不在任一set中,则将其加入notCEO。

-google 1point3acres如果Manager在maybeCEO中,那么不做任何事;. more info on 1point3acres.com
如果Manager在notCEO中,那么不做任何事;. visit 1point3acres.com for more.
如果Manager不在任一set中,则将其加入maybeCEO..鐣欏璁哄潧-涓浜-涓夊垎鍦
-google 1point3acres
上面的规则可简化为:
1. 把Employee加入notCEO;若Employee也在maybeCEO中,则移除之;//Employee肯定不可能是CEO
2. 如果Manager不在notCEO中,则将其加入maybeCEO中。 // 未被确定为非CEO的Manager可能是CEO

这样处理完所有的record之后,maybeCEO中所剩的就是“所有不向任何人汇报的Person”,也就是CEO.

这样做的好处是:1. 能够处理多个CEO的情况(尽管可能没多大的现实意义). 2. 不需修改Person类.
回复 支持 1 反对 0

使用道具 举报

MichaelYC 发表于 2015-7-17 05:24:38 | 显示全部楼层
第三轮,CEO 的问题。我的想法是用 B-tree。
. 1point3acres.com/bbs
1. 算法:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对于 csv file,边遍历边建 B-tree。
建法是:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
当前的正在遍历的这个人(设为 A 吧)是一个 Node, 那么根据 List,所有向他汇报的人都是他的子。此时 Root 为 A。也就是 CEO candidate 就是 A。

接着iterate,iterate,iterate。。。
后面便利到一个人(叫他 S),如果 S 的 list 里面 有 A, 那么 A 就是 S 的子,此时 Root 为 S。

那么最终的 Root 就是 CEO。
. From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres

2. 复杂度:
Suppose "n" is the total number of employee.
时间 O( n^2 ) 找 Node 插入点,最快的情况就是 把当前在 B-tree 里面的人全扫一遍。这样 1 + 2 + 3 + ... + n = O(n^2)
如果把每一个Node 的子,按照 字母顺序排列的话,那么就可以用 Binary Search 来查。这样会好一些。

空间 O( n ) 所有的员工都要塞到树里。

. visit 1point3acres.com for more.
看到题目前就是这个思路,不知道可以不可以。

补充内容 (2015-7-16 16:25):
时间 O( n^2 ) 找 Node 插入点,最快...(打错了,应该是最 ** 坏 **的情况)

评分

1

查看全部评分

回复 支持 0 反对 1

使用道具 举报

iceberg 发表于 2014-12-20 12:24:32 | 显示全部楼层
楼主能把第三轮讲的更详细些吗?每个entry里employer和manager之间是什么关系,谁向谁report?这道题目的目的是不是把这个文件load进来存到由person组成的树里?CEO就是树的根吧。
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-12-20 13:00:36 | 显示全部楼层
iceberg 发表于 2014-12-19 23:24
楼主能把第三轮讲的更详细些吗?每个entry里employer和manager之间是什么关系,谁向谁report?这道题目的目 ...
. 1point3acres.com/bbs
当然是employer向manager report,entry就是一个cvs的一个条目.1point3acres缃

是树还是graph都无所谓,关键是用什么data structure来表示。我当时是用map,key是ssn保证一一对应,value是Person类

然后就实现一个方法把.csv读到map里
回复 支持 反对

使用道具 举报

iceberg 发表于 2014-12-20 15:05:26 | 显示全部楼层
Freetymekiyan 发表于 2014-12-20 13:00
当然是employer向manager report,entry就是一个cvs的一个条目

是树还是graph都无所谓,关键是用什么d ...

我猜楼主应该拼错了,应该是employee吧。
楼主把每个Person构建起来以后,这个graph就自动建立起来了。有节点,有连接,是个完整的graph。. 1point3acres.com/bbs
如何找到CEO?如果在Person里面加上一个manager变量,随便从哪个Person开始,只要trace back,就可以找到CEO了,CEO没有老板。
回复 支持 反对

使用道具 举报

iceberg 发表于 2014-12-20 15:05:33 | 显示全部楼层
Freetymekiyan 发表于 2014-12-20 13:00
当然是employer向manager report,entry就是一个cvs的一个条目

是树还是graph都无所谓,关键是用什么d ...
. 1point3acres.com/bbs
我猜楼主应该拼错了,应该是employee吧。
楼主把每个Person构建起来以后,这个graph就自动建立起来了。有节点,有连接,是个完整的graph。
如何找到CEO?如果在Person里面加上一个manager变量,随便从哪个Person开始,只要trace back,就可以找到CEO了,CEO没有老板。
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-12-21 00:11:05 | 显示全部楼层
iceberg 发表于 2014-12-20 02:05. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我猜楼主应该拼错了,应该是employee吧。
楼主把每个Person构建起来以后,这个graph就自动建立起来了。 ...

嗯,是employee,不好意思

关键是怎么把每个Person构建起来,Person里面也没有manager的变量
回复 支持 反对

使用道具 举报

hongke 发表于 2014-12-21 16:48:06 | 显示全部楼层
topological sort on directed acyclic graph, 用DFS实现,只需要求得graph上面的reversePostorder后返回第一个item
回复 支持 反对

使用道具 举报

iceberg 发表于 2014-12-22 01:03:32 | 显示全部楼层
用一个map,key是ssn,value是Person object。每读入一条,构建两个Person Object,一个是Employee,一个是manager,(如果已经在map里了,就不需要重建了)。把这个employee放到manager的report表里。一个有向图就建成了。
如果能在Person里放Manager,找到CEO很容易;如果不能,就像楼上所说用拓扑排序也可以找到,不过相对麻烦。
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-12-22 01:57:15 | 显示全部楼层
iceberg 发表于 2014-12-21 12:03
用一个map,key是ssn,value是Person object。每读入一条,构建两个Person Object,一个是Employee,一个是 ...

这里有一些细节,比如说每读入一条就创建两个Person,肯定有manager已经被创建过了,所以要先check这个employee的ssn是不是已经在map的key set里。另外创建manager的时候,manager是没有title的。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
总结起来思路是,读取entry e,map.containsKey(e.empl_ssn),如果返回true,从map里面获取这个Person,设置他的title;如果返回false,先创建Person p,存到map里,再看map.containsKey(e.man_ssn)。如果存在,把p加到他的reports list中,如果不存在,创建manager,把p加到reports里,存入map-google 1point3acres

需要写test进一步验证
回复 支持 反对

使用道具 举报

iceberg 发表于 2014-12-23 11:45:36 | 显示全部楼层
Freetymekiyan 发表于 2014-12-22 01:57
这里有一些细节,比如说每读入一条就创建两个Person,肯定有manager已经被创建过了,所以要先check这个em ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这样清楚多了。
感谢楼主分享。
回复 支持 反对

使用道具 举报

z3581640 发表于 2015-1-5 07:25:43 | 显示全部楼层
如果我理解的没错的话, CEO 那题应该是这么做的, 所有人都要对CEO report, 但是CEO 不需要对所有人 report, 但是employee之间可能存在report

用List 存 person 即可

然后两个指针  p1, p2

初始化的时候都在head, . visit 1point3acres.com for more.
如果 p2 给 p1 report, 那么 p2++. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
否则:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
p1 = p2,p2++;. more info on 1point3acres.com
最后, p1就是 CEO

O(n)的时间 , O(1)的空间
回复 支持 反对

使用道具 举报

limingli1991 发表于 2015-7-11 05:06:04 | 显示全部楼层
请问楼主第四轮里面 有100万个元素怎么弄。。。
回复 支持 反对

使用道具 举报

mrno5zzz 发表于 2015-7-11 23:19:09 | 显示全部楼层
iceberg 发表于 2014-12-20 15:05
我猜楼主应该拼错了,应该是employee吧。
楼主把每个Person构建起来以后,这个graph就自动建立起来了。 ...

对于ceo这个题不大理解啊,每个entry读取的时候不就知道有没有manager了么?那建立person的同时不是就可以找出没有manager的那个人了吗
回复 支持 反对

使用道具 举报

juliusjun 发表于 2015-7-19 07:13:03 | 显示全部楼层
MichaelYC 发表于 2015-7-17 05:24.鐣欏璁哄潧-涓浜-涓夊垎鍦
第三轮,CEO 的问题。我的想法是用 B-tree。

1. 算法:

假设某些entry之间没有任何关联,怎么record?建立N个b-tree?
回复 支持 反对

使用道具 举报

juliusjun 发表于 2015-7-19 07:15:38 | 显示全部楼层
iceberg 发表于 2014-12-20 15:05
我猜楼主应该拼错了,应该是employee吧。
楼主把每个Person构建起来以后,这个graph就自动建立起来了。 ...
. visit 1point3acres.com for more.
trace back?楼主的题目里说的list是向当前node汇报children,怎么从当前node跳到他的上一级呢?
回复 支持 反对

使用道具 举报

MichaelYC 发表于 2015-7-19 23:19:30 | 显示全部楼层
juliusjun 发表于 2015-7-18 18:13
假设某些entry之间没有任何关联,怎么record?建立N个b-tree?

好问题。我觉得这样的话就要和面试官讨论,到底 CEO 的定义是什么?如果 CEO 是接受很多汇报的人,那么这 N个 B-tree 中,子最多的明显就是 CEO。我觉得,如果算法结果是很多棵 B-tree,那么那些接受了汇报又不往上级汇报的人,到底概算什么呢?自己把问题处理了?譬如结果是5个B-tree,然后每个 B-tree 下面都是简单的两个子,那这样的话,恐怕就很难说谁是 CEO 了吧?所以我觉得 CEO 的定义很重要。
回复 支持 反对

使用道具 举报

MichaelYC 发表于 2015-7-20 10:55:25 | 显示全部楼层
juliusjun 发表于 2015-7-19 20:44. 鍥磋鎴戜滑@1point 3 acres
我已经懂了,其实就是Celebrity Problem。O(n). 论坛里其他人也被问过同样的题目
-google 1point3acres
这样啊。孤陋寡闻了,好的,我也学习一下。看帖的小伙伴,关于 Celebrity Problem,这里有解答:http://www.geeksforgeeks.org/the-celebrity-problem/
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 02:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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