楼主前段时间Amazon onsite，遇到了Amazon经典的电梯设计题目，下面是我对这个题目的总结，也是答案不是最好的，欢迎大家来补充。
下面是我的onsite 面经：http://www.1point3acres.com/bbs/ … p;page=1#pid1956961


我感觉对于OOP设计问题，关键要和面试官进行讨论，弄清情景situation ，who will use it,在这个situation都是有哪些对象，他们在干什么，他们之间是什么关系，然后一个对象一个对象的去分析这个对象应有的属性，和行为。多和面试官讨论，越细致越好！如果可以使用什么单例，或者factory method 来设计的话，multi threading, 就尽量的添加上这些东西。

elevator:

First ask the interviewer what kind of elevator? there is only one elevator serving that building or multiple elevators serving the building simultaneously?
this situation is that: there is one elevator serving the building. there are many floors in the buliding. Maybe there are some users in different floor pressing the button simultaneously. This results in some requests to RequestProcessCenter for processing. The RequestProcessCenter figure out the first request that need to be processed in such an algorithm that the distance between target floor and current floor is shortest.

474. Ones and Zeroes

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m0s and n1s respectively. On the other hand, there is an array with strings consisting of only 0sand 1s.

Now your task is to find the maximum number of strings that you can form with given m0s and n1s. Each 0 and 1 can be used at mostonce.

Note:

1. The given numbers of 0s and 1s will both not exceed 100
2. The size of given string array won’t exceed 600.

472. Concatenated Words

Given a list of words, please write a program that returns all concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:

Note:

1. The number of elements of the given array will not exceed 10,000
2. The length sum of elements in the given array will not exceed 600,000.
3. All the input string will only include lower case letters.
4. The returned elements order does not matter.

1.给一个数列和一个目标数， 返回目标数出现的次数，数列已经排序

2.二树， 打印层次顺序的节点 (level order traversal)

3.给一个字符串只由一，零和星组成， 返还一组数， 把星替换成1和2

4.有n个tuple 比如 [“a”,”b”,”c”] [“red”,”blue”]….要求生成 从每个tuple中取一个string构成的所有组合 比如 [“a”,”red”] [“b”,”blue”]…..

5.给一个String的array，问如何移除重复的string (hashmap,bst)

6.binary tree的max height

7.给一个integer的array，按照n1<=n2>=n3<=n4>=n5 的order排序。
A[0]<=A[1]>=A[2]<=A[3] shuffle
coding:
u = [u1, u2, u3, u4, u5, u6, …] (integers)
s = [s1, s2, s3, s4, s5, s5, …]
s1 <= s2, s2 >=s3, s3 <= s4, s4 >= s5,…..

8.fibonacci为啥不用recursive。分别的时间复杂度。空间复杂度，包含函数栈上的

9.sorted array有正有负如何按顺序输出平方值 (binary search,然后两边扫)

10.给一个BST，找第k个元素(inorder traversal or heap)

1.Maximal Rectangle Given a 2D binary matrix filled with 0’s and 1’s,

前言：常看到有人問 system design需不需要準備 new grad會不會考system design 我想給地裡的戰友們建議 當然準備面試刷題是基本中的基本 但當你刷到一定程度後 刷題投資報酬率就開始低了 這時我真心建議可以花些時間讀system design 因為你花在這個的前10-20小時投資報酬率非常高！基本的觀念有了以後可以apply到所有的問題 面試之前不管HR跟你說有沒有system design你都不怕 廢話不多說 直接進入主題

我的所有資料來源都是地裡還有以下連結
https://www.evernote.com/shard/s576/sh/7e58b450-1abe-43a8-bf82-fbf07f1db13c/049802174415b418a2e65f75b744ab72
https://github.com/checkcheckzz/system-design-interview
https://www.interviewbit.com/courses/system-design/

這篇文章主要是把所有手上資源照priority順序加上一些自己的整理 用簡單的方式介紹怎麼Ace system design 依照priority順序分成
明天面 下禮拜面 下個月面 跟明年面

=====明天要面system design=====

迷途書僮:誒jyt0532 我明天就要面試了 沒空讀那麼多你給的文章 該怎麼辦？
jyt0532: 很好 今天幸好你遇到我 我用最少的時間讓你知道明天面試的時候大方向怎麼走
Step1: 先問所有requirement, spec 這個系統需要提供什麼功能
Step2: Constrains: 問他我們需要處理多少traffic, 多少data, latency重不重要 A和C選哪個
Step3: 計算需要多少機器 要用什麼storage
Step4: Abstract design: 先畫出大架構！ 每個會出現的component都要畫出來 再看面試官希望你深入講哪個component
Step5: Scale: 讓你的system有fault tolerance, scale成大公司的系統架構

迷途書僮: 等等step2的A和C是什麼
jyt0532: CAP的A和C 如果你明天要面試你不知道CAP是什麼 那我的建議是你今天早點休息 明天才有精神 地球是很危險的
迷途書僮: 別這樣啦 我幫你加大米拜託給我一個最簡單最好的解釋
jyt0532: 既然你都這麼說了 今天幸好你遇到我 把這個看完你就通透了http://ksat.me/a-plain-english-introduction-to-cap-theorem/
迷途書僮: 喔原來是這個 那這4個step 你這樣講真的很抽象 可不可以舉個例子 我可以apply到所有system design的題目
jyt0532: 光說不練假把戲 我帶你手把手跑一次system design process

來個基本的 假設現在要design一個hash
Step1,

2013(10-12月) 码农类 硕士 实习@Facebook - 校园招聘会 - Onsite 校园招聘会 |Pass

实际上我FB的offer2个多月前就拿了, 当时一直想发个帖分享经验, 但是当时竟然没有发现面经版… .

闲话少说, 当时facebook网申和career fair都投过简历, 后来在career fair一周后收到了on-campus面试通知。入围面试的人实际上并不是很多, 我觉得我能被选中是因为我在career fair上和一个FB的员工聊了一下以前做的项目, 他似乎也对我说的挺感兴趣, 再加上简历也写得不错, 所以我就荣幸地入围面试了吧。所以说, career fair大家还是要重视的, 不要草草地扔了简历就了事, 要尽可能地和展台上的员工沟通一下。

当时on-campus面试是我来美帝的第一面, 觉得特别紧张。他问的题是Dynamic Programming中最经典的问题coin change, 就是给定一个面额(比如100), 以及一些不同面额的硬币(2,3,5), 求所有的硬币组合, 使得他们的面额之和为100. 当时我还不懂DP, 所以就只提供了一个brute-force的解法, 就是假设100 = 2i+ 3j +5k, 先遍历所有的j和k, 然后看剩下的100-3j-5k是不是偶数。正确的解法应该是用DP, 大家可以去google一下, 结果很多。当时是一个45分钟的面试, 按理说应该要做两道题, 我却只做了一道, 当时觉得估计跪了, 不过老天保佑, 我竟然又庆幸地进入了on-site面试。

on-site面试题觉得更简单, 有两道题, 不过我现在就记得后一道了。问的就是给你一个字符串的list, 把它们重新排序一下, 使得互为anagram的词放在一块。对于anagram的题, 一般情况下只要把所有字符串按字母表顺序重新排列一下就成了, 这题也不例外, 如果是Java写的话, 只用自己写一个判断两个词是否为anagram的comparator就行了。

on-site之后的第四天我就收到了offer，能在那么早的时候收到facebook这么好的offer, 我只能说我这肯定是我上半辈子积下的德。facebook是一个效率超高的公司, 从我第一轮面试到最终收到offer, 只花了不到一个月的时间, 非常符合它的”Move fast and Break things”的理念。并且从面试过程中, 我能感觉到facebook的员工之间的交流成本肯定很低, 所有的邮件都是简洁到极致, 不像我面Google的时候邮件里面各种rules, tips写一大堆(作为一个被Google拒的人, 我觉得我没有资格黑它..)。

另外, 我觉得面试的时候要注意以下两个方面:
1) 多和面试官沟通, 边写代码的时候边说自己的想法, 不要只自顾自地写代码而把面试官晾在一边。说完想法的时候, 问一下:”Does it make sense to you?”,

Numbers Everyone Should Know

When you’re designing a performance-sensitive computer system, it is important to have an intuition for the relative costs of different operations. How much does a network I/O cost, compared to a disk I/O, a load from DRAM, or an L2 cache hit? How much computation does it make sense to trade for a reduction in I/O? What is the relative cost of random vs. sequential I/O? For a given workload, what is the bottleneck resource?

When designing a system, you rarely have enough time to completely build two alternative designs to compare their performance.

Algorithms

• https://www.hackerrank.com/domains
• https://oj.leetcode.com/problemset/algorithms/ LeetCode至少要刷三遍，付费部分的题建议花点钱看一下，舍不得孩子套不着狼
• http://lintcode.com/
• http://www.ninechapter.com/solutions/
• http://www.geeksforgeeks.org/about/interview-corner/
• TopCoder Algorithm Tutorial: http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/ 其中几何算法的教程要仔细看，Google特爱出几何题
• CC150: Cracking the Code Interview: http://www.valleytalk.org/wp-content/uploads/2012/10/CrackCode.pdf

OO Design

http://blog.csdn.net/longyulu/article/details/9159589

System Design

Here are some articles about system design related topics.

• How to Rock a Systems Design Interview
• System Interview
• Scalability for Dummies
• Scalable Web Architecture and Distributed Systems
• Numbers Everyone Should Know
• Scalable System Design Patterns
• Introduction to Architecting Systems for Scale
• Transactions Across Datacenters
• A Plain English Introduction to CAP Theorem
• The CAP FAQ
• Paxos Made Simple
• Consistent Hashing
• NOSQL Patterns
• Scalability,

POI-GeoHash

https://dzone.com/articles/designing-spacial-index
Geographic Information Systems (GIS) is an interesting area of exploration because it poses two significant challenges: latency at scale and modeling spatial locality.
Let’s say you’re visiting NYC and need an Internet connection. Where’s the nearest Wi-Fi hotspot?How might an HBase application help you answer that question? What kind of design decisions go into solving that problem, and how can it be solved in a scalable way?
You know you want fast access to a relevant subset of the data. To achieve that, let’s start with two simple and related goals:

1. You want to store location points on disk such that points close to each other in space are close to each other on disk.

这里原帖地址: http://www.mitbbs.com/article_t/JobHunting/32492515.html

以下为转载内容

===========================我是分割线==================

稍微总结一下

1. 入门级的news feed
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.infoq.com/presentations/Scale-at-Facebook
http://www.infoq.com/presentations/Facebook-Software-Stack
一般的followup question是估算需要多少server
另外这个帖子有讨论
http://www.mitbbs.ca/article_t/JobHunting/32463885.html
这篇文章稍微提到要怎么approach这种题，可以稍微看看
http://book.douban.com/reading/23757677/

2. facebook chat,这个也算是挺常问的
http://www.erlang-factory.com/upload/presentations/31/EugeneLet
https://www.facebook.com/note.PHP?note_id=14218138919
http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
http://essay.utwente.nl/59204/1/scriptie_J_Schipers.pdf

3. typeahead search/search suggestion，这个也常见
https://www.facebook.com/video/video.php?v=432864835468
问题在这个帖子里被讨论到，基本上每个问题，在视频里都有回答
http://www.mitbbs.com/article_t/JobHunting/32438927.html

4. Facebook Messaging System(有提到inbox search, which has been asked before）
messaging system就是一个把所有chat/sms/email之类的都结合起来的一个系统
http://www.infoq.com/presentations/HBase-at-Facebook
http://sites.computer.org/debull/A12june/facebook.pdf
http://www.slideshare.net/brizzzdotcom/facebook-messages-hbase/
https://www.youtube.com/watch?v=UaGINWPK068

5.