Chapter 65 Amazon

65.1 How to prepare Amazon Behavior Question?

http://www.1point3acres.com/bbs/thread-285290-1-1.html

ftfotroy 发表于 5 小时前 | 只看该作者
我来现身说法吧,我就跪在这上面了.首先,你要包装好自己的经历,所有的答案必须是包
装过的.
把十四条内化.没包装过的大实话绝对是不可以的.
然后准备一些这样的经历:
1, 作为掌握真理的少数,你怎么让别人信服
2, 跪舔customer的经历.根据customer的feedback来改进产品的经历.
3, 自己当大腿挑大梁的经历
4, 失败的经历.(你要把失败说的和成功一样才行)

切记!十四条不可违反!十四条以外的优点在他们看来不是优点,至少说不算作面试加分项,
如果十四条以外的优点和十四条冲突也不行. 十四条互相也会有冲突,说的时候也要注意.

----

再加一句,他们家的技术面试不难,behavior在评估是占得比例极高,按recruiter的原话
是half half. 所以建议你们如果只有在准备amazon一家面试的话,一定要在behavior上下
大工夫,别不舍得花时间. 以前上学写作文不好的同学,多和朋友讨论讨论,如何包装自
己.

十四条内化是指,在准备每一个问题的答案的时候,事例都要尽可能多的cover这十四条,并且一定不能有违反这十四条的例子出现.

发过一个面经包…..里面的BQ你自己写一遍,对照着亚麻14条,感觉就差不多了

http://www.1point3acres.com/bbs/thread-273331-1-1.html

2017(1-3月) 码农类 硕士 全职 Amazon - 猎头 - Onsite |Other在职跳槽 on site完接近一个礼拜都没回音.不敢去问怕来拒信.顺便发一下楼主收集到的在职社招on site的面经集合造福后人. 非technical的问题真的要好好准备.提前写一遍然后自己读读,不亚于刷题刷设计的重要性.

面经来源地里,感谢各位的贡献,如果有人觉得侵犯版权或者隐私的,请DM我我去删除.括号里是具体帖子里比较重要一点思路或者重要的follow up question,楼主只是做一个微小的贡献

System Design:

  1. Design a Uber 设计一个简单的Uber,包括检测周围空闲的车,用户打车付账流程和到目的地时间估计. (将城市化成许多个矩形block(区),可以借鉴二维k-d tree那个思想.每个车实时更新当前位置坐标和是否available,找用户最近八个区的空闲的车,然后时间就是车速和距离的关系,这个没错.地图api这种你需要什么和interviewr说就好了,如果不是考察项目的话一般都会说可以默认给出的.)

2.TinyURL (Write heavy? improve Security? 怎么scale? 一个region上的服务出问题了怎么处理?)

  1. Repository system, design commit fuction and branch function.

  2. Video/Movie System (given a list of videos, return top 5 rated videos)

  3. Sotre the livestreaming video and watch it later function

  4. CC150 JukeBox

  5. Amazon gift card printing machine. (实就是general的说一下你对一个application architecture的理解,面试官会引导你,比如用啥样的db,用rest/soap,某一步失败了怎么办,data consistency一类的随便扯一扯)

  6. One hour delivery system.

  7. Explain Agile, Waterfall, Pro & Cons.

  8. Predict User purchase. (先分析什么因素判断用户买不买这个商品,浏览记录,购买记录,在页面停留时间,浏览这类商品的次数,现在火的top 100商品等等.然后分析架构, 给的答案是首先master slave避免single point failure,用户点击商品后先通过dymanic dns look up找到距离最近的CDN,然后http request传过来给那个cluster的master server, mater本身有cache看看这个请求的结果是不是已经cache过了有的话直接返回(这里cache的是这个请求对应的购物车html页面),没有的话master做负载均衡下传给空闲slave server(rmi call), slave有自己的local cache因为对这个预测结果每个slave cache可以不consistent, 可以不用时刻recon每个不同的server cache.所有的数据存储都用in memory database并设置time to live, 因为这个是一个读取大于写的系统数据也不需要持久化不用支持transaction, scale也更容易.master如果挂了重启就可以,因为都是预测数据丢失了也无所谓.如果要更优化可以在浏览器端也做一层cache,如果用户反复点击同样的商品,就不用每次都make http call了)

  9. Card game , and write shuffle method.

  10. Amazon Locker 就是Amazon买东西可以运到一个Locker然后pick up的那个. (仔细想一下你就会发现就是一个Parking Lot.Package有Small,Medium,Large.一个Location的 Lockers也有Small,Medium, Large.面试官主要想知道一个送货小哥去的时候怎么分配给他个大小合适的Locker.要写那个method.我就按照Parking Lot做的.我觉得一模一样.恩恩,我那时侯一开始考虑也想是不是Order生成的时候就匹配了一个Locker,还有挑选哪个Location,但跟面试观官交流以后,他就说假设只有一个Location然后主要想知道送货小哥去的时候怎么分配,别的先不考虑.)

  11. Reader System

  12. Parking Lot, Airport etc…

  13. Amazon address book

    1. What’s in web server
    2. What’s the API for address service
    3. What’s in the storage
    4. How to improve the performance

(user 发送与address 相关的请求到web server,　然后web server 获取／更新相关的记录.大概说了下DNS根据user ip访问临近的web server, 问到了web server 里头有哪些与address 相关的function 以及参数,具体说了下getAddressLists. 期间提了下cache 面试官表情不对了.后边问了有多少个表,怎么设计,怎么提高profermance. 楼主提到说作no sql 做sharding.面试官说时间到了没有给反馈,多半是设计太狗血)

  1. Design system to store user info and address info. Address info changes frequently. Need to notify address change..

  2. Design a Log application. (就是开发从上面获取 bug log 信息,用户可以往上提交.开始我并不知道log application怎么工作的,是程序员往上提bug 还是test人员往上提.跟面试官一步步讨论的,然后写了些前后端的 process.中间很多问题,他们会顺着你的思路往下问)

  3. 给了一堆 商品,每个有不同的分类tag 比如 book, music, sports… 然后按顺序输出,就是输出这里他描述的特别不清楚,于是开始先按tag sort了,然后顺着输出.他说不行,想要控制每行的个数,然后就控制个数输出.然后他比较满意,follow up 了随意更改每行的个数,不要求写代码,也写上去了

  4. OOD.设计一个SQL parser(不是compiler,这里强调如何解析SQL语句中的变量,比如table name,和关键字, 比如select 语句),关键在于怎么用好interface

  5. 设计一个big integer类.实现其中的add和multiply.先是讨论了要使用的数据结构(数组和链表)并对比优缺点,然后用数组实现(非高效压缩那种的,一个数组元素是大数里的一位数).multiply只要写伪代码,出了错,不过他不介意

  6. 设计个API,满足两个function,一个是往list里面丢string,还有一个是统计top k frequent element. 对于API实现scalability.

  7. Design pattern: strategy, observer 设计模式那个就是duck/toyduck的变形.Observer那个也是比较教科书的东西

  8. 如果有一个service, 要求设计方法支持query,比如最后一秒的访问数,最后一分钟的访问数,….最后一小时的访问数…

1.把timestamp 写到磁盘上,然后用hadoop 来算.面试官问pros and cons

  1. 为了改善读的速度,我说把这些timestamp存到in-memory buckets里面,最后还是 hadoop

根据我的buckets排序思路提示我,可以不用存timestamp….我有点惊呆了,但是转念一想,你这些query的时间段是last second/minute/hour.我觉得就可以只有这三个buckets,每次call 这个service的同时,检查当前的timestamp,如果超过1秒,我说就去aggregate/update last minute和last hour的总数就好了… 到最后我脑子里有点捣浆糊了,但是面试官看到我最后的思路解释说可以work

  1. 手机公司的bill系统,手机计划有免费时段,比如晚7点到第二天早7点和周末免费.短信和数据有各自的价格,用超过计划允许的数量怎么办.最后完成的感觉还算不错.这一轮也问了oo的一些基础知识,比如inheritance 和 composition的区别,什么时候用哪种?

Algo: 亚麻很少出原题,但经常出变型,感觉挺灵活的.难度比较上属于中等和偏简单,偶尔有些hard属于经典题或者bar raiser吧.仅供大家参考.

1. Unique Path 变形(可以上下左右,可否回溯,不可return false且原地不动)
2. lc239  
3. Max Subtree Sum.
4. Longest Substring without duplicate char
5. Find leftmost node of the lowest level
6. Two sum
7. Merge qua-tree
color: black, white, misc. 
class Qua-tree
{. 
    Que-Tree[] children; //0 or 4 children
        int color;
        ....
}
Merge two tree, black is dominate color: black vs anything -> black;

  1. 围棋判断一个子被capture与否,被capture的定义就是这子或这子属于的整块同色子区域被另外颜色子包围.
    (解法也很简单, dfs. 每次recusive call返回是否被capture, 遇到异色子或者出界都是true, 遇到同色子就recursively去call它)
    (那假设只有同色的子(没有对手的子),也算是被capture么?(这个点很好!! 可以当作edge case处理单独处理.)

  2. Latgest rectangle area

  3. Search word in Trie

11.Lowest LCA

12.Top k nearest point

13.给出的是一个目标文件名,自己提出假设定出file class 和 directory class,找出所有符合目标文件名的文件的path

14.job failure root search. (相当于一颗倒的树,root fail了,找导致这个failure的最高的ancestor.DFS, 顺着fail的path往上找)

15.多米诺骨牌,找出最少数量的能推倒所有牌的牌 (大概思路就是循环把入度为0的点当作起点dfs,把能traverse的点mark as visited,把起点加入result,然后如果还剩下没有visited的点,就说明有环,所以就再loop剩下点,每一个dfs,mark能traverse到的点as visited,把起点加入result,如果碰到了之前visited的起点,就把这个起点从result里面删掉,加入当前的起点.)

  1. Shorest Path

17.Find heavier ball in ball array

  1. Word Break

  2. Word Ladder II(原题是变一个字母,这里是去掉一个字母)

  3. string to int

  4. int to roman

  5. There is list of price at each day,and only one selling window is allowed. The selling price is the minimum price of start day and end day of that selling window, and price is flat during the selling window. The selling amount is constant per day. Find out the selling window gives maximum profit, output max profit.

  6. Graph. graph. 实现画板的brush功能: 一个画板上面已经有一些图案,用户在画板上点任意一点,画板会自动paint包含该点的封闭的多边形.实现这个功能.

24.Merge Interval

  1. Matrix原题

  2. 有一个Task clas包括两个int, start and end; 有个list有很多个Task, 计算需要多少Thread 来run这些task.

  3. Serialize and Deserialized Binary Tree
    (中间穿插了多线程的问题,以及 abstract class 等知识. Follow up :
    1. What if the TreeNode class value is string (instead of int) which may include newline, space, comma
    2. 如果不是二叉树,是多叉树怎么办? 正确的方法是在序列化的时候 存孩子的数目,存数据的长度,再存数据.需要一个结构化的序列化操作

new line, space 这些只是给你增加难度,你可以把数据当成binary来存; 我的想法是可以存字符串的ASCII码或者UNICODE编码,然后用space或者newline隔开存到文件里

  1. 一个matrix,里面有一些锁(1表示)和空白(0表示),问每个空白到最近的锁的距离.简单bfs

  2. 算法+search suggestion设计,算法:给个word,给个dict判断给定的word是不是anagram

  3. numbers of islands ( follow up:有多少个形状不同的岛? 这个Follow up是经典 number of distinct islands. 比之前的明显要难些. 需要用到hashing得思想. 每一个岛将遍历完的点id(每个cell 可以分配一个id, id = i*m+j) 组合起来, 返回字符串,比如 “1/2/3/5” 这个岛有四个点.如果另一个岛是 “11/12/13/15” 只要把它offset下, 第一位归1, 它也变成“1/2/3/5”, 所以这2个岛的shape是一样的. 将这些第一位归1的字符串往set里丢.自然就除重了 中心思想: 将CELL ID组合来表示一个岛(hash to string),然后变形string, 最后往set里丢. done )

  4. kth largest number in array,quick selection

  5. LRU cache

  6. Number to English words.

  7. Valid Parenthesis

  8. given n pairs of numbers (1122…nn) and arrange them so that the each number x is x spaces apart from another number x. (数字必须紧挨着,思路就是DFS)

  9. Given a dictionary of words and a word, return the word if it exists in dict, else return the top 5 words in the dict that are closest to the given word;

  10. 2D array is immutable. Give 2D array of 1s and 0s, 1 is island and 0 is sea. Return the maximum island size

  11. 给了一棵树,让给每个node 加一个pointer 指向sibling. (用了queue level order traverse 加了.然后follow up 让优化,no extra space)

  12. Reconstuct itinerary.

  13. 一个non-negative integer array里找subarray sum (followup: 数字可以为负).

  14. 有一堆时间连续的purchase records (id, timestamp, userId, productId),找出最常被同一个用户连续购买的三个商品

  15. 找出数组中唯一出现奇数次的数字,保证只有一个,(hashset解决)

  16. reverse linkedlist

  17. Kindle界面是黑白的,黑色区域是一个shape,然后输入一个界面且可修改,返回shape的个数. (这里我用了二维数组作为输入,0是空白,1是用pixel.然后dfs即可. 其实就是Number of island.)

  18. Intersection of two linked list

  19. Group anagrams

  20. Convert binary tree to double linked list. In-order order

  21. 写一个class要求push/pop和get minimum都是O(1)

  22. 给一个数组的object,用里面的key来sort,keys 只有有限的几个

(这个题我先用的priority queue,让我继续优化,我用了bucket sort,到O(n), 让我继续优化用in-place,我用了两个pointer; 我最后用2个pointer排序的,但是一个while loop 下面嵌套了四个sub while loop.比如,这些objects的key 只有 X, Y, Z. 排序的要求是把这三组按照XYZ的顺序排好

前两个sub while loop 对调X 和 Y或Z; 这轮结束后,X的位置应该都是在正确的位置上了 后两个 sub while loop 对调 Y 和 Z.)

  1. wiggle sort 2 (给一个数组,里面有负数和正数,让输出负数／正数间隔的数组,我用了两个pointer从头到尾／从尾到头同时扫一遍.估计这题没法做成in-place,最后没时间写完code,只是大概说了一下,最后面试官觉得可以work)

  2. find number of distinct islands in 0-1 matrix. .