一亩三分地论坛

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

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

新鲜的AmazonFeb17电面

[复制链接] |试试Instant~ |关注本帖
luofeidream 发表于 2016-2-18 04:57:25 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Other其他

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

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

x
刚刚面完Amazon的intern,来分享面经攒人品。自从上次因为自己的失误错失facebook,心情一直低沉,半个多月没有写过算法题,心里有点方方的。。。
楼主1初就找人内推了,结果中间出了点问题,内推人把职位推错了,导致今天才电面。-google 1point3acres
先按照国际惯例介绍自己,介绍做过的project,这段就一直cool, awesome之类的,大家都懂的,然后问了数据结构 linkedlist和array,虽然这些东西在本科就烂熟于心,但是口语拙计导致表达的时候可能自己不太满意。
然后出了一道貌似design其实是算法的算法题:
Amazon wants to run a marketing campaign sending messages to
its customers according to their spending profiles.

This campaign has 3 messages:
. visit 1point3acres.com for more.
Message 1: targets the 25% of customers who spent the most
Message 2: targets the 25% of customers who spent the least. more info on 1point3acres.com
Message 3: targets the rest of the customers.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
Given the list of all purchases made in a period of time. From 1point 3acres bbs
write a program that correctly sends the messages to the customers.

Tip: assume there's a method/function .鏈枃鍘熷垱鑷1point3acres璁哄潧

sendMessage(customers, messageId) . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

available that actually sends the message to the collection
of customers passed in as parameter.



一开始楼主一看见题目,先读了5分钟,然后和面试官沟通了题目的意思,做了一些assumption,然后问了具体每个元素的结构,上手就头脑一热开始用heap来做,结果10分钟后做完,面试官说感觉有点麻烦,其实可以更简单,于是我冷静一下头脑,发现其实就是特么的一道排序题。。。
然后很快地用排序的方法写了一遍,面试官说这样看起来简单多了,然后follow up就是怎么提高方法的scalability,假设有很多的customer group,我就说弄一个level的数组,对于每个level,对结果切片然后SendMessage,然后面试官说cool,问了一下复杂度,最后问问题环节,聊了聊一些技术性的问题比如AWS Dynamo,还有一些非技术性的比如西雅图之生活与工作。。。面试官很开心地说西雅图的夏天万里无云简直awesome。。。然后就拜拜了。
攒人品求offer,攒人品求offer,攒人品求offer,说三遍!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴



补充内容 (2016-3-2 07:00):
Update一下,美中时间Mar 1,下午5点收到offer
七七要加油 发表于 2016-2-18 05:15:12 | 显示全部楼层
楼主聊了dynamo, 感觉刁刁的,offer稳稳的
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 05:17:06 | 显示全部楼层
七七要加油 发表于 2016-2-18 05:15. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主聊了dynamo, 感觉刁刁的,offer稳稳的
. visit 1point3acres.com for more.
借你吉言啊,希望能Seattle见!dynamo是以前看过paper于是强行扯一扯。。
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-18 06:03:05 | 显示全部楼层
楼主你好,能不能问一下传入的参数是不是 company的list. 然后company 有一个field which is cost?
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 06:14:31 | 显示全部楼层
a598165394 发表于 2016-2-18 06:03
楼主你好,能不能问一下传入的参数是不是 company的list. 然后company 有一个field which is cost?
. Waral 鍗氬鏈夋洿澶氭枃绔,
参数是一个list,每个元素是purchase,purchase里面包含了这次purchase的customerId和花费的amount
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-18 06:18:22 | 显示全部楼层
luofeidream 发表于 2016-2-18 06:14
参数是一个list,每个元素是purchase,purchase里面包含了这次purchase的customerId和花费的amount
.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢楼主。这题首先得算出每个公司的total cost吧?然后这是一个unsorted array,普通的排序和heap sort的time complexity应该都是Nlog(N)吧?能不能问一下为什么普通排序会更简单?因为是用了quick select嘛?
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-18 06:19:53 | 显示全部楼层
luofeidream 发表于 2016-2-18 06:14
参数是一个list,每个元素是purchase,purchase里面包含了这次purchase的customerId和花费的amount

因为我们并不知道25% most 和25%least这两个点的具体值是多少吧?
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 06:22:06 | 显示全部楼层
a598165394 发表于 2016-2-18 06:18
谢谢楼主。这题首先得算出每个公司的total cost吧?然后这是一个unsorted array,普通的排序和heap sort ...
. 1point 3acres 璁哄潧
首先算出每个customer的总cost(不是company- -囧),然后放到一个列表里按照cost进行排序,然后切分就好了,我一开始是用了大小为总customer数的25%的heap然后往进push的。。
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-18 06:24:54 | 显示全部楼层
luofeidream 发表于 2016-2-18 06:22. 鍥磋鎴戜滑@1point 3 acres
首先算出每个customer的总cost(不是company- -囧),然后放到一个列表里按照cost进行排序,然后切分就好 ...
. visit 1point3acres.com for more.
谢楼主。。sorry -_-   所以算出cost for each customer后。面试官让直接用 Arrays.sort(nums)来切分?。。。。我一开始想到也是用两个heap来分割。。。
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 06:26:56 | 显示全部楼层
a598165394 发表于 2016-2-18 06:24
谢楼主。。sorry -_-   所以算出cost for each customer后。面试官让直接用 Arrays.sort(nums)来切分?。 ...

面试官就静静地看着你做,并没有规定要怎么做,我上午看面经的时候看到好多heap题,然后脑子一热就用heap了。。其实就是直接sort
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-18 06:36:07 | 显示全部楼层
luofeidream 发表于 2016-2-18 06:26
面试官就静静地看着你做,并没有规定要怎么做,我上午看面经的时候看到好多heap题,然后脑子一热就用heap ...

Papa...祝楼主早日拿到offer~
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 06:40:33 | 显示全部楼层
a598165394 发表于 2016-2-18 06:36
Papa...祝楼主早日拿到offer~
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
谢谢,祝你也是~
回复 支持 反对

使用道具 举报

usa521 发表于 2016-2-18 06:46:30 | 显示全部楼层
首先感觉楼主肯定没问题的整体感觉很好.1point3acres缃

我有个小疑问:
1. 算出每个customer的总cost后,怎么放到待排序的list里呢?list只能存一种数据类型,那存了cost排序了以后怎么跟各自的customerId对应起来呢?
2. 给的那个sendMessage里的第二个参数mesageId是干什么用的啊
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 07:02:01 | 显示全部楼层
usa521 发表于 2016-2-18 06:46
首先感觉楼主肯定没问题的整体感觉很好

我有个小疑问:

谢谢鼓励啊. from: 1point3acres.com/bbs
1: 因为我用的是python,所以list里面是可以存一个tuple的,也就是[(id,cost),()]这种形式,如果你用Java或C++或其他语言,你可以自己定义class或者struct,再放进list里面就可以啦。. 鍥磋鎴戜滑@1point 3 acres
2: messageId没有什么卵用,在你group完之后,对每个group调用send message就可以啦,面试官当时就随便给我写了比如说sendMessage(first_group,1),sendMessage(second_group,2)之类的
回复 支持 反对

使用道具 举报

YJ_Li 发表于 2016-2-18 07:07:18 | 显示全部楼层
楼主如何准备Amazon实习面试,有面经资料总结分享吗
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 07:10:04 | 显示全部楼层
YJ_Li 发表于 2016-2-18 07:07
楼主如何准备Amazon实习面试,有面经资料总结分享吗

没有准备,就是今天上午看了看Amazon相关的面经= =论坛应该有人总结吧,可以找找
回复 支持 反对

使用道具 举报

YJ_Li 发表于 2016-2-18 07:13:17 | 显示全部楼层
有的话求发 :yijin.li.jack@gmail.com
回复 支持 反对

使用道具 举报

usa521 发表于 2016-2-18 08:20:39 | 显示全部楼层
luofeidream 发表于 2016-2-18 07:02
谢谢鼓励啊
1: 因为我用的是python,所以list里面是可以存一个tuple的,也就是[(id,cost),()]这种形式 ...

谢谢你的回复……我一直不大理解你说的group是什么意思 是说排序完以后 前25%是单独装进group1 中间的装进group2 后25%装进group3吗?  
那样的话follow up 里的 "有很多group"和level是一种什么思路呢?
回复 支持 反对

使用道具 举报

 楼主| luofeidream 发表于 2016-2-18 08:45:29 | 显示全部楼层
usa521 发表于 2016-2-18 08:20
谢谢你的回复……我一直不大理解你说的group是什么意思 是说排序完以后 前25%是单独装进group1  ...

是的,就是按照顾客的消费数额分成几个group,对每个group发送不同的消息(ps:亚麻竟然差别对待客户),因为一开始是分了3个group吗,follow up就是可能有很多group,比如消费前10%的10%~20%的,etc……
回复 支持 反对

使用道具 举报

usa521 发表于 2016-2-18 14:36:31 | 显示全部楼层
luofeidream 发表于 2016-2-18 08:45
是的,就是按照顾客的消费数额分成几个group,对每个group发送不同的消息(ps:亚麻竟然差别对待客户), ...

楼主讲的很明白!!!

最后1个小问题,我就是不太明白你说的follow up里提高scalability的时候,怎么构建level的数组呢? 为什么分成level以后就能提高scalability了..
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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