亚马逊面试题目.docx

《亚马逊面试题目.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、亚马逊面试题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]就是有序的，再次做二分即可

2、。对方说能想到lgn的复杂度很好，但是希望能够只要一次二分就完成。1.英文自我介绍加一个英文问答：WhyAmazon？2.基础知识：数组、链表、map的区别和用法3.最长公共子序列（动态规划，时空复杂度都是O(n^2)）可以把空间复杂度降到O(n)，后缀数组（数据结构）4.电影院售票系统设计：面向对象思想设计5.股价题，空间复杂度优化到O(1)6.给一个n行m列的矩阵框，每个格点放着若干大米，小鸡从左下角点出发，只能往右或者往上走，问小鸡最多能吃掉多少大米。很简单的动态规划，瞬秒。然后他又和我讨论了优化空间复杂度的问题，我说可以从O(n^2)优化到O(n)的，对方表示满意。第三轮是面试官和

3、我讨论一个openquestion，这个题目感觉很有意思：给一个图片，这个图片是由n*m个小图片拼成的，它的色调是左上角最浅，越往右下角色调越深。问我有没有什么办法做出这样的图片。我的想法是对这n*m个小图片的色调从浅到深排序，然后斜着从小到大填充这个大矩形。124357689对色调排序是把每个小图片的RGB三个值（范围0~255）做统计，最后去掉个数过少的然后做加权平均，哈希出每个小图片的色调值然后再排序即可（没有标答，你可以自己定义规则，只要合理就行）。一边讨论一边让我把自己定义的数据结构、怎样找每个小图片的哈希值、怎样填充大矩形的代码写了下来。////////////////////

4、////////////////////////////////////////////  1、有一个2G的文件，如果只有300m内存，应该怎么反置文件？2、如何在内存中快速从2亿QQ用户中通过号码快速得到用户的信息？3、很多用户进行查询和更新用户信息的操作怎么办？4、同时有10W个连接请求，该如何处理？   答案：一、1、我觉得:1、NIO内存映射 2、Cache，哈希表（Map接口） 3、缓存，事务处理 3、线程池+I/O多路复用+集群均衡负载 二、分机器。qq我觉得其实是最容易扩容的，按照qq号分就可以了。每10万个号进入一组，分组处理，硬件几乎可以无限增加，毫无性能问题可言。 三、

5、1、NIO内存映射2、Cache，哈希表（Map接口）3、缓存，事务处理3、线程池+I/O多路复用+集群均衡负载 这个回答基本是靠谱的，如果你面试的普通程序员，应该是很优秀的回答了。但是，对于一个架构师级别的面试，这个回答，可能是不满意的。 如果使用一个不存在的QQ号码进行冲击系统，这个是很严重的问题，去看看BloomFilter.对于问题3，事务一般不会使用，可以考虑使用日志类事务检查，或者使用事务规范，自己完成分布式事务。 同时有10W个连接请求，该如何处理？这是个10K问题，不是问你怎么做，而是问你系统对于大规模连接，对于单一机器的处理办法，以及规模扩展的办法。实际上，这些问题都是目

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