新鲜Amazon面经

下午刚面完，趁着没忘赶集发出来

上来就是个阿三，先问我最近在做啥project上啥课，然后问了list, set和map分别都是啥，完了问你知道哪些sorting algorithm。

然后开始做题了。第一题说给你一个500 million个元素的数组

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

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

问OOD，只有做题。

两面的最后都让我问问题，我就问了你们组是做什么的。实话说，俩阿三说的我都一个字没听懂。这以后能一起工作么???

500 million 也不大吧

楼主是女生吗？

阿三面试官口音有这么恐怖= =

第一题怎么sort这么大的数据量啊？

kelvinzhong 发表于 2014-2-16 11:13
第一题怎么sort这么大的数据量啊？

每个元素才10bit，开10bit个桶，也就是2^10=1024个桶，然后用桶排序就行了，时间复杂度O(n)

我面的时候也是三哥，80%听不懂，但他还是很耐心地给我重复三四遍。。。

alex2013 发表于 2014-2-17 01:04
阿三面试官口音有这么恐怖= =

说面试题还能凑活听一听，说起一长串话的时候就真成希腊语了

kelvinzhong 发表于 2014-2-17 01:13
第一题怎么sort这么大的数据量啊？

写错了，不是500 million,是5 million
不过做法就如上面那位所说，bucket sort

RickyYe 发表于 2014-2-16 13:01
每个元素才10bit，开10bit个桶，也就是2^10=1024个桶，然后用桶排序就行了，时间复杂度O(n)

桶牌利用的是n^2排序（比如insertion sort）对base case很快。 但是这里每个桶平均有500个， 也不见得能多块。这题也是1024*(500^2)

既然是2^10为什么不直接counting sort？

今天面试碰阿三，很负责任地说，阿三口音真的很恐怖……

500 million个元素的数组，元素都是10bit的整数 radix sort??
但是每一层输出的顺序和上一层是相反的。比如第二层从左到右print，第三层就从右到左print。 leetcode 原题？？