亚马逊面试题

1.算法题：一个股价序列，告诉每个时间点的股价，问什么时候买什么时候卖获利最大？时间复杂度O(n) 2.（1）有0，1，2到99这100个正整数，中间丢失了一个，剩余的99个数打乱顺序放在一个数组里， 问怎样找到丢失的那个数。

直接说了一个时间空间复杂度都为O(n)的算法（瞬秒），能把空间复杂度优化到O(1)的

（2）有一个有序的环形数列，从小到大排好了，比如：4，5，6，1，2，3，从第四个位置开始当成环形看， 就是一个有序数列1，2，3，4，5，6。问题是在这个数列中找到给定的关键字。

我想到了用二分找到这个环形的开头位置i，那么[0，i]，[i+1，n-1]就是有序的，再次做二分即可。 对方说能想到lgn的复杂度很好，但是希望能够只要一次二分就完成。

1.英文自我介绍加一个英文问答：Why Amazon？ 2.基础知识：数组、链表、map的区别和用法

3.最长公共子序列（动态规划，时空复杂度都是O(n^2)）可以把空间复杂度降到O(n)，后缀数组（数据结构） 4.电影院售票系统设计：面向对象思想设计 5.股价题，空间复杂度优化到O(1)

6.给一个n行m列的矩阵框，每个格点放着若干大米，小鸡从左下角点出发，只能往右或者往上走，

问小鸡最多能吃掉多少大米。很简单的动态规划，瞬秒。然后他又和我讨论了优化空间复杂度的问题，我说可以从O(n^2)优化到O(n)的，对方表示满意。

第三轮是面试官和我讨论一个open question，这个题目感觉很有意思：给一个图片，这个图片是由n*m个小图片拼成的，

它的色调是左上角最浅，越往右下角色调越深。问我有没有什么办法做出这样的图片。 我的想法是对这n*m个小图片的色调从浅到深排序，然后斜着从小到大填充这个大矩形。 1 2 4 3 5 7 6 8 9

对色调排序是把每个小图片的RGB三个值（范围0~255）做统计，最后去掉个数过少的然后做加权平均， 哈希出每个小图片的色调值然后再排序即可（没有标答，你可以自己定义规则，只要合理就行）。 一边讨论一边让我把自己定义的数据结构、怎样找每个小图片的哈希值、怎样填充大矩形的代码写了下来。

////////////////////////////////////////////////////////////////

1、有一个2G的文件，如果只有300m内存，应该怎么反置文件？ 2、如何在内存中快速从2亿QQ用户中通过号码快速得到用户的信息？ 3、很多用户进行查询和更新用户信息的操作怎么办？ 4、同时有10W个连接请求，该如何处理？

答案： 一、 1、我觉得: 1、NIO内存映射

2、Cache，哈希表（Map接口） 3、缓存，事务处理

3、线程池+I/O多路复用+集群均衡负载

二、分机器。qq我觉得其实是最容易扩容的，按照qq号分就可以了。每10万个号进入一组，分组处理，硬件几乎可以无限增加，毫无性能问题可言。

三、1、NIO内存映射

2、Cache，哈希表（Map接口） 3、缓存，事务处理

3、线程池+I/O多路复用+集群均衡负载

这个回答基本是靠谱的，如果你面试的普通程序员， 应该是很优秀的回答了。 但是， 对于一个架构师级别的面试， 这个回答， 可能是不满意的。

如果使用一个不存在的QQ号码进行冲击系统， 这个是很严重的问题， 去看看BloomFilter. 对于问题3， 事务一般不会使用，可以考虑使用日志类事务检查， 或者使用事务规范， 自己完成分布式事务。

同时有10W个连接请求，该如何处理？ 这是个10K问题， 不是问你怎么做， 而是问你系统对于大规模连接， 对于单一机器的处理办法， 以及规模扩展的办法。

实际上， 这些问题都是目前QQ在大规模环境下真实问题。 这些问题不是回答的来就成的， 关键是是否一定的某些问题的实际操作解决能力。