亚马逊面试题目.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(n^2)）可以把空间复杂度降到O(n)，后缀数组（数据结构）4.电影院售票系统设计：面向对象思想设计5.股价题，空间复杂度优化到O(1)6.给一个n行m列的矩阵框，每个格点放着若干大米，小鸡从左下角点出发，只能往右或者往上走，问小鸡最多能吃掉多少大米。

很简单的动态规划，瞬秒然后他又和我讨论了优化空间复杂度的问题，我说可以从O(n^2)优化到O(n)的，对方表示满意第三轮是面试官和我讨论一个open question，这个题目感觉很有意思：给一个图片，这个图片是由n*m个小图片拼成的，它的色调是左上角最浅，越往右下角色调越深问我有没有什么办法做出这样的图片我的想法是对这n*m个小图片的色调从浅到深排序，然后斜着从小到大填充这个大矩形1 2 43 5 76 8 9对色调排序是把每个小图片的RGB三个值（范围0~255）做统计，最后去掉个数过少的然后做加权平均，哈希出每个小图片的色调值然后再排序即可（没有标答，你可以自己定义规则，只要合理就行）一边讨论一边让我把自己定义的数据结构、怎样找每个小图片的哈希值、怎样填充大矩形的代码写了下来////////////////////////////////////////////////////////////////  1、有一个2G的文件，如果只有300m内存，应该怎么反置文件？2、如何在内存中快速从2亿用户中通过号码快速得到用户的信息？3、很多用户进行查询和更新用户信息的操作怎么办？4、同时有10W个连接请求，该如何处理？   答案：一、1、我觉得:1、NIO内存映射 2、Cache，哈希表（Map接口） 3、缓存，事务处理 3、线程池+I/O多路复用+集群均衡负载 二、分机器。

我觉得其实是最容易扩容的，按照号分就可以了每10万个号进入一组，分组处理，硬件几乎可以无限增加，毫无性能问题可言 三、1、NIO内存映射2、Cache，哈希表（Map接口）3、缓存，事务处理3、线程池+I/O多路复用+集群均衡负载 这个回答基本是靠谱的，如果你面试的普通程序员， 应该是很优秀的回答了 但是， 对于一个架构师级别的面试， 这个回答， 可能是不满意的 如果使用一个不存在的号码进行冲击系统， 这个是很严重的问题， 去看看BloomFilter. 对于问题3， 事务一般不会使用，可以考虑使用日志类事务检查， 或者使用事务规范， 自己完成分布式事务 同时有10W个连接请求，该如何处理？ 这是个10K问题， 不是问你怎么做， 而是问你系统对于大规模连接， 对于单一机器的处理办法， 以及规模扩展的办法实际上， 这些问题都是目前在大规模环境下真实问题 这些问题不是回答的来就成的， 关键是是否一定的某些问题的实际操作解决能力。