竭诚为您提供优质文档/双击可除
亚马逊,大老板面试
篇一：亚马逊面试题目 亚马逊面试题
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 页 共 9 页
1.英文自我介绍加一个英文问答：whyamazon？ 2.基础知识：数组、链表、map的区别和用法
3.最长公共子序列（动态规划，时空复杂度都是o(n^2)）可以把空间复杂度降到o(n)，后缀数组（数据结构） 4.电影院售票系统设计：面向对象思想设计 5.股价题，空间复杂度优化到o(1)
6.给一个n行m列的矩阵框，每个格点放着若干大米，小鸡从左下角点出发，只能往右或者往上走，
问小鸡最多能吃掉多少大米。很简单的动态规划，瞬秒。然后他又和我讨论了优化空间复杂度的问题，我说可以从o(n^2)优化到o(n)的，对方表示满意。
第三轮是面试官和我讨论一个openquestion，这个题目感觉很有意思：给一个图片，这个图片是由n*m个小图片拼成的，
它的色调是左上角最浅，越往右下角色调越深。问我有没有什么办法做出这样的图片。
我的想法是对这n*m个小图片的色调从浅到深排序，然后斜着从小到大填充这个大矩形。 124 357 689
对色调排序是把每个小图片的Rgb三个值（范围0~255）
第 2 页 共 9 页
做统计，最后去掉个数过少的然后做加权平均，哈希出每个小图片的色调值然后再排序即可（没有标答，你可以自己定义规则，只要合理就行）。
一边讨论一边让我把自己定义的数据结构、怎样找每个小图片的哈希值、怎样填充大矩形的代码写了下来。////////////////////////////////////////////////////////////////
1、有一个2g的文件，如果只有300m内存，应该怎么反置文件？
2、如何在内存中快速从2亿qq用户中通过号码快速得到用户的信息？
3、很多用户进行查询和更新用户信息的操作怎么办？ 4、同时有10w个连接请求，该如何处理？ 答案： 一、 1、我觉得: 1、nio内存映射
2、cache，哈希表（map接口） 3、缓存，事务处理
3、线程池+i/o多路复用+集群均衡负载
二、分机器。qq我觉得其实是最容易扩容的，按照qq号分就可以了。每10万个号进入一组，分组处理，硬件几
第 3 页 共 9 页