新鲜的AmazonFeb17电面

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

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

复杂度，最后问问题环节，聊了聊一些技术性的问题比如AWS Dynamo，还有一些非技术性的比如西雅图之生活与工作。。。面试官很开心地说西雅图的夏天万里无云简直awesome。。。然后就拜拜了。
攒人品求offer，攒人品求offer，攒人品求offer，说三遍！



补充内容 (2016-3-2 07:00):
Update一下，美中时间Mar 1，下午5点收到offer

usa521 发表于 2016-2-18 06:46
首先感觉楼主肯定没问题的整体感觉很好

我有个小疑问：

谢谢鼓励啊
1： 因为我用的是python，所以list里面是可以存一个tuple的，也就是[(id,cost),()]这种形式，如果你用Java或C++或其他语言，你可以自己定义class或者struct，再放进list里面就可以啦。
2： messageId没有什么卵用，在你group完之后，对每个group调用send message就可以啦，面试官当时就随便给我写了比如说sendMessage（first_group,1），sendMessage（second_group,2）之类的

usa521 发表于 2016-2-18 14:36
楼主讲的很明白！！！

最后1个小问题，我就是不太明白你说的follow up里提高scalability的时候，怎么 ...

就是一开始的时候给的例子是3个group，然后我就用了3个list来存，面试官的意思我理解就是万一有很多group，那你这个程序岂不是要有这么多个list来存，然后我就说弄个level的数组每个元素表示的是对应的level,比如levels = [10%, 20%....]这种，然后做个循环把消息按level发送

luofeidream 发表于 2016-2-18 07:02
谢谢鼓励啊
1： 因为我用的是python，所以list里面是可以存一个tuple的，也就是[(id,cost),()]这种形式 ...

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

楼主聊了dynamo, 感觉刁刁的，offer稳稳的

七七要加油 发表于 2016-2-18 05:15
楼主聊了dynamo, 感觉刁刁的，offer稳稳的

借你吉言啊，希望能Seattle见！dynamo是以前看过paper于是强行扯一扯。。

楼主你好，能不能问一下传入的参数是不是 company的list. 然后company 有一个field which is cost?

a598165394 发表于 2016-2-18 06:03
楼主你好，能不能问一下传入的参数是不是 company的list. 然后company 有一个field which is cost?

参数是一个list，每个元素是purchase，purchase里面包含了这次purchase的customerId和花费的amount

luofeidream 发表于 2016-2-18 06:14
参数是一个list，每个元素是purchase，purchase里面包含了这次purchase的customerId和花费的amount

谢谢楼主。这题首先得算出每个公司的total cost吧？然后这是一个unsorted array，普通的排序和heap sort的time complexity应该都是Nlog(N)吧？能不能问一下为什么普通排序会更简单？因为是用了quick select嘛？

luofeidream 发表于 2016-2-18 06:14
参数是一个list，每个元素是purchase，purchase里面包含了这次purchase的customerId和花费的amount

因为我们并不知道25% most 和25%least这两个点的具体值是多少吧？

a598165394 发表于 2016-2-18 06:18
谢谢楼主。这题首先得算出每个公司的total cost吧？然后这是一个unsorted array，普通的排序和heap sort ...

首先算出每个customer的总cost（不是company- -囧），然后放到一个列表里按照cost进行排序，然后切分就好了，我一开始是用了大小为总customer数的25%的heap然后往进push的。。

luofeidream 发表于 2016-2-18 06:22
首先算出每个customer的总cost（不是company- -囧），然后放到一个列表里按照cost进行排序，然后切分就好 ...

谢楼主。。sorry -_-   所以算出cost for each customer后。面试官让直接用 Arrays.sort(nums)来切分？。。。。我一开始想到也是用两个heap来分割。。。

a598165394 发表于 2016-2-18 06:24
谢楼主。。sorry -_-   所以算出cost for each customer后。面试官让直接用 Arrays.sort(nums)来切分？。 ...

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