一亩三分地论坛

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

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

Amazon 1月12日onsite

[复制链接] |试试Instant~ |关注本帖
majiaofdaye 发表于 2016-2-12 10:32:24 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
Amazon 联系我,不是统招,而是跟一个特定的组面试。感觉个别team自己招聘的话bar高一点,而且名额太有限。挂了还得让你等6个月再来。还不如参加统招。


以下是onsite 面试题。

Round 1 三哥
问:一个百万行record的数据库表,有员工名字,manager名字,工资三中信息。 问要想载入内存,共查询,该用什么datastructre ?语言用java。
List,HashMap等等。 只要能说出search 和insert的时间复杂度就行。 说出hashmap做不了range search更好。

follow up: 实现一个简单地hashmap吧。用java 的generics。. Waral 鍗氬鏈夋洿澶氭枃绔,
这个看看JDK里的hashmap怎么实现的。 自己模仿写一下就能理解。-google 1point3acres

Round 2 加拿大人. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
问: phone number=>string的转换。例如2对应abc,3对应def(参考手机里的拨号软件UI)。给个号码,找出所有对应的string。bfs和dfs都要求写。问时间复杂度是多少,各自的优缺点是啥。
空间 =>构建过程中bfs比较耗内存,因为要保存一堆中间状态的string;dfs则相对少用些内存。
时间 => 算清楚string+string和stringbuilder构建新的string时间复杂度有啥区别。
问behavior questoin :需要做一个决定,但时间不够,信息不足,怎么办?. from: 1point3acres.com/bbs
本人答得也不好,也不知道怎么回答。还请各位指点。。

Round 3 hiring manager 三叔
问:在集群的web log中找连续访问两天的user ID。 假设log只有day1 和day2, 但log非常大,装不进内存。. from: 1point3acres.com/bbs
如果能装进内存,直接做set intersection。对于超大文件,思路是先做partition,在做set intersection。
问:那如何设计partition函数?
如果是user id,应该是有含义的。例如section1-sectoin2-sectoin3, 一个section可以是geo location, membership, 等等。用这些信息做partition。

.鐣欏璁哄潧-涓浜-涓夊垎鍦
问:假设已经做好了partition,写个函数实现set intersection。.鏈枃鍘熷垱鑷1point3acres璁哄潧
直接用了java set 的retainAll。但看到三叔不大满意,自己手写了retainAll的逻辑。


behavior 问题: 之前工作里有没有遇到过deadline没法交差的情况? 怎么解决的?
答得不好。遇到此类问题不知该如何回答。 -google 1point3acres
请教各位看官这类怎么回答才算好?

Round 4 老美
问:设计short URL service。 先从数据库表设计开始。
用提问的方式排出了security, authentication和privacy之类的case。
设计了只有两个字段的数据库 :key 和original url。 哈希算法提议用MD5,取前面的7个字节(类似git commit的hash,2的 7*8= 56次方,够大了)。.1point3acres缃

问:冲突怎么解决?-google 1point3acres
如果一个key存在的话就用8字节作为key(小概率),还冲突的话就用9字节(此类service的life cycle中不会出现)。

问:假设有了数据库访问跟hashing的api,写出read url和create short url的代码。
很简单。无非是read的时候做些error handling,create的时候检查冲突。

问:如果service火了,上述代码中那一段可能会成为瓶颈? 怎么解决? (scaling怎么做)
数据库读写部分。 说道mysql read replica, master slave,再不行就用nosql之类的。 但没说caching,估计这是我的扣分项。
问:了解哪些nosql 产品? 比较下优缺点?
说了Hbase和Cassandra (其实不大懂)。

总的来说,这一轮思路展开是没问题,不足之处是没用数字做推算(例如每月访问量是多少,需要多少storage)。

. Waral 鍗氬鏈夋洿澶氭枃绔,
最终还是挂了,但也不遗憾。


评分

2

查看全部评分

 楼主| majiaofdaye 发表于 2016-2-12 10:35:25 | 显示全部楼层
behavior还问了之前老板对你的看法是啥?对此你怎么想? (太难回答)
回复 支持 反对

使用道具 举报

 楼主| majiaofdaye 发表于 2016-2-12 10:38:08 | 显示全部楼层
http://www.hiredintech.com/system-design  这是个很好的学习资料。
回复 支持 反对

使用道具 举报

269644943 发表于 2016-2-12 15:14:21 | 显示全部楼层
楼主面的什么组
回复 支持 反对

使用道具 举报

269644943 发表于 2016-2-12 15:15:10 | 显示全部楼层
各种设计题,这么残暴
回复 支持 反对

使用道具 举报

zsuyu0629 发表于 2016-2-13 02:37:04 | 显示全部楼层
这面试感觉有点凶残!祝楼主好运了
回复 支持 反对

使用道具 举报

beforelost 发表于 2016-2-13 03:14:26 | 显示全部楼层
第三轮,我有个不同想法,创建一个hashmap<userid, integer> value表示day1访问为1,day2访问为2,both为3。对于每个sever上的log一行一行的读,如果这一行有用户访问信息,那把userid和访问日期代表的数字写入hashmap. 想快点的话,可以用hashtable多个server同时读log. 这样所有log读完,就知道那个用户访问的天数了。不知这样行的通不,或者我误解题意了?
回复 支持 反对

使用道具 举报

269644943 发表于 2016-2-13 05:34:11 | 显示全部楼层
beforelost 发表于 2016-2-13 03:14
第三轮,我有个不同想法,创建一个hashmap value表示day1访问为1,day2访问为2,both为3。对于每个sever上 ...

内存装不下了,你就没法用一台机器,只能先partition,然后多台机器一起
回复 支持 反对

使用道具 举报

beforelost 发表于 2016-2-13 07:23:33 | 显示全部楼层
269644943 发表于 2016-2-13 05:34
内存装不下了,你就没法用一台机器,只能先partition,然后多台机器一起

一行一行的处理log内容不需要一次把全部log读到内存里的,参考这个解答: http://stackoverflow.com/questio ... e-file-line-by-line. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

269644943 发表于 2016-2-13 08:06:20 | 显示全部楼层
beforelost 发表于 2016-2-13 07:23. from: 1point3acres.com/bbs
一行一行的处理log内容不需要一次把全部log读到内存里的,参考这个解答: http://stackoverflow.com/ques ...

一行一行读,最后还是都会读到hashmap里, hashmap 存在内存里(heap).如果你内存不够大,如何装的下这个hashmap呢? 除非你一边读进来,一边处理完再从hashmap里面删掉。  这题考察的点就是分布式系统的东西吧
回复 支持 反对

使用道具 举报

 楼主| majiaofdaye 发表于 2016-2-13 19:01:26 | 显示全部楼层
269644943 发表于 2016-2-13 08:06
一行一行读,最后还是都会读到hashmap里, hashmap 存在内存里(heap).如果你内存不够大,如何装的下这个 ...

对, 是我没说清楚。考点就是分布式处理算法应用。
回复 支持 反对

使用道具 举报

 楼主| majiaofdaye 发表于 2016-2-13 19:10:53 | 显示全部楼层
beforelost 发表于 2016-2-13 03:14
第三轮,我有个不同想法,创建一个hashmap value表示day1访问为1,day2访问为2,both为3。对于每个sever上 ...

这方法挺好,数据小的话做个统计答案就出来了。
但那一轮考点是大数据处理.
回复 支持 反对

使用道具 举报

attractor 发表于 2016-2-14 05:09:08 | 显示全部楼层
同想问楼主面的什么组,这难度难道招的是SDE2?
回复 支持 反对

使用道具 举报

beforelost 发表于 2016-2-14 08:58:39 | 显示全部楼层
269644943 发表于 2016-2-13 08:06
一行一行读,最后还是都会读到hashmap里, hashmap 存在内存里(heap).如果你内存不够大,如何装的下这个 ...

我开始想的是一个hashmap不够就用多个hash,再多的话就每台机器上维护一些这样的maping,存到文件中。一边处理一边删这个想法也挺好,不过只适合一次性调用。个人觉得实际场景中,log是每天大量生成的东西,然后查看user登陆情况是很常用的方法,没可能每天生产新的log都要做partition预处理(当然要根据实际需求而定)。所以就这样按生成时间一行行的处理log,把需要的用户登陆信息更新到相应的maping中去。这样每次想要查看用户登陆情况,只需要处理这些mapping文件就可以了。
回复 支持 反对

使用道具 举报

beforelost 发表于 2016-2-14 09:08:23 | 显示全部楼层
关于那个到dealline没有完成的任务的问题,根据个人经验,通常的做法就是跟manager商量,然后推到下一次release。 因为发布了有问题的代码比什么都不发布要好得多。当然一般情况下平时要跟manager不断回报工作进度,这样manager对每个task的进度有把握,并且发布代码之前会有code freeze,code review 和testing的时间,code freeze之前还没有完成就推到下一次发布了,平时沟通到位,不是临时出现surprise的情况。
回复 支持 反对

使用道具 举报

ningtaohaha 发表于 2016-2-18 12:44:32 | 显示全部楼层
beforelost 发表于 2016-2-14 09:08. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
关于那个到dealline没有完成的任务的问题,根据个人经验,通常的做法就是跟manager商量,然后推到下一次rel ...

好到位,谢谢分享
回复 支持 反对

使用道具 举报

yijingzeng 发表于 2016-4-2 12:14:46 | 显示全部楼层
请问楼主面的什么组? SDE I 还是SDE II?
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-12 12:28:50 | 显示全部楼层
感觉问题都好需要工作经验。。
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-5-13 00:15:42 | 显示全部楼层
beforelost 发表于 2016-2-14 09:08
关于那个到dealline没有完成的任务的问题,根据个人经验,通常的做法就是跟manager商量,然后推到下一次rel ...

说反了吧 什么都不发布比发布有问题的要好得多
回复 支持 反对

使用道具 举报

 楼主| majiaofdaye 发表于 2016-6-16 14:15:05 | 显示全部楼层
Round 3 要是能提到“这是常用操作的话就写个小的service”就更好了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 02:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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