:一个股价序列,告诉每个时间点的股价,问什么时候买什么时候卖获利最大?时间复杂度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的复杂度很好,但是希望能够只要一次二分就完成。:WhyAmazon?:数组、链表、(动态规划,时空复杂度都是O(n^2))可以把空间复杂度降到O(n),后缀数组(数据结构):,空间复杂度优化到O(1),每个格点放着若干大米,小鸡从左下角点出发,只能往右或者往上走,问小鸡最多能吃掉多少大米。很简单的动态规划,瞬秒。然后他又和我讨论了优化空间复杂度的问题,我说可以从O(n^2)优化到O(n)的,对方表示满意。第三轮是面试官和我讨论一个openquestion,这个题目感觉很有意思:给一个图片,这个图片是由n*m个小图片拼成的,它的色调是左上角最浅,越往右下角色调越深。问我有没有什么办法做出这样的图片。我的想法是对这n*m个小图片的色调从浅到深排序,然后斜着从小到大填充这个大矩形。124357689对色调排序是把每个小图片的RGB三个值(范围0~255)做统计,最后去掉个数过少的然后做加权平均,哈希出每个小图片的色调值然后再排序即可(没有标答,你可以自己定义规则,只要合理就行)。一边讨论一边让我把自己定义的数据结构、怎样找每个小图片的哈希值、怎样填充大矩形的代码写了下来。//////////////////////////////////////////////////////////////// 1、有一个2G的文件,如果只有300m内存,应该怎么反置文件?2、如何在内存中快速从2亿QQ用户中通过号码快速得到用户的信息?3、很多用户进行查询和更新用户信息的操作怎么办?4、同时有10W个连接请求,该如何处理? 答案:一、1、我觉得:1、NIO内存映射 2、Cache,
亚马逊面试题目 来自淘豆网m.daumloan.com转载请标明出处.
