亚马逊面试题目.docx

亚马逊面试题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(n2)）可以把空间复杂度降到O(n)，后缀数组（数据结构）4.电影院售票系统设计：面向对象思想设计5.股价题，空间复杂度优化到O(1)6.给一个n行m列的矩阵框，每个格点放着若干大米，小鸡从左下角点出发，只能往右或者往上走，问小鸡最多能吃掉多少大米。很简单的动态规划，瞬秒。然后他又和我讨论了优化空间复杂度的问题，我说可以从O(n2)优化到O(n)的，对方表示满意。第三轮是面试官和我讨论一个open question，这个题目感觉很有意思：给一个图片，这个图片是由n*m个小图片拼成的，它的色调是左上角最浅，越往右下角色调越深。问我有没有什么办法做出这样的图片。我的想法是对这n*m个小图片的色调从浅到深排序，然后斜着从小到大填充这个大矩形。1 2 43 5 76 8 9对色调排序是把每个小图片的RGB三个值（范围0255）做统计，最后去掉个数过少的然后做加权平均，哈希出每个小图片的色调值然后再排序即可（没有标答，你可以自己定义规则，只要合理就行）。一边讨论一边让我把自己定义的数据结构、怎样找每个小图片的哈希值、怎样填充大矩形的代码写了下来。/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问题， 不是问你怎么做， 而是问你系统对于大规模连接， 对于单一机器的处理办法， 以