稍微总结一下

入门级的news feed

一般的followup question是估算需要多少server

另外这个帖子有讨论

http://www.mitbbs.ca/article\_t/JobHunting/32463885.html

这篇文章稍微提到要怎么approach这种题，可以稍微看看

http://book.douban.com/reading/23757677/

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

typeahead search/search suggestion，这个也常见

https://www.facebook.com/video/video.php?v=432864835468

问题在这个帖子里被讨论到，基本上每个问题，在视频里都有回答

http://www.mitbbs.com/article\_t/JobHunting/32438927.html

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

任给一个手机的位置信号(经纬度)，需要返回附近5mile 的POI

这个这里有讨论，这题貌似nyc很爱考...

http://www.mitbbs.ca/article0/JobHunting/32476139\_0.html

Implement second/minute/hour/day counters

这题真不觉得是system design，但万一问道，还是要有准备，貌似在总部面试会被问

道....

这个帖子有讨论

http://www.mitbbs.com/article\_t/JobHunting/32458451.html

facebook photo storage，这个不太会被问起，但是知道也不错

https://www.usenix.org/legacy/event/osdi10/tech/full\_papers/Beaver.pdf

https://www.facebook.com/note.php?note\_id=76191543919

facebook timeline,这个也不太是个考题，看看就行了

https://www.facebook.com/note.php?note\_id=10150468255628920

http://highscalability.com/blog/2012/1/23/facebook-timeline-bro

除了这些，准备一下这些题目

implement memcache

http://www.adayinthelifeof.nl/2011/02/06/memcache-internals/

implement tinyurl（以及distribute across multiple servers)

http://stackoverflow.com/questions/742013/how-to-code-a-url-sho

determine trending topics(twitter)

http://www.americanscientist.org/issues/pub/the-britney-spears-

http://www.michael-noll.com/blog/2013/01/18/implementing-real-t

copy one file to multiple servers

http://vimeo.com/11280885

稍微知道一下dynamo key value store，以及google的gfs和big table

这个high scalability上有很多讲system design的东西，不光是facebook的，没空的

话，就光看你要面试的那家就好了..

facebook engineering blog

http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc

http://stackoverflow.com/questions/3533948/facebook-architectur

其他家的

http://www.quora.com/What-are-the-top-startup-engineering-blogs

==================================================================

首先如果你连availability/scalability/consistency/partition之类的都不是太有概

念的话，我建议先去wikipedia或者找一个某个大学讲这门课的网站稍微看一下，别一

点都不知道

这个链接也不错

http://www.aosabook.org/en/distsys.html

再有就是面试的时候应该怎么去approach这种题，我说说我的做法

product spec/usage scenario 和面试者confirm这个东西到底是做什么的

可以先列出来几个major functionality，然后有时间的话，再补充一些不重要的

把你想的都写下来

define some major components

就是画几个圈圈框框的，每个发表一番您的高见....然后讲他们之间怎么interact

以上是question specific的东西，

这个讲完了，我们可以讲一些每道题都是用的，比如说

怎么scale/怎么partition/怎么实现consistency，这些东西，可以套用到任何题上

F家：

电面：

 华人大哥: 一个数组里有多个最大值，等概率随机返回其中一个最大值的index，

要求one pass。LC 的 permutations

Onsite：

 1 国人大哥（人很好，放我的水）： merge k sorted lists, best time to buy

and sell stock。

 2 印度经理： 背景+behavior+一个编程：code base在某个版本开始有bug，找到

这个版本。

 3 老美： LC 的 minimum window substring, decode ways。

 4 中东人： LC的valid palindrome。 给1， 2， 5面值的纸币，有多少种组合凑

出100 块钱。

 5 三哥：设计题，传输10G的data到5个data center，每个data center 有1000的

节点。三哥从问背景就开始找茬，面试过程中要求解gossip protocol的微分方程，被

黑。

 面试完，立刻投诉三哥，因为所有其他面试官都给了strong recommend，于是加

面设计题

 6. 老美（高级别，大牛人）：设计iPhone Find Friends 的后端。Geohashing +

DHT解之

F家的面试官水平都很高，都很乐意和你讨论他们的project，当然如果你很恰当的给

出comment，会给你加分不少。

设计题问得很细，比如DHT如何实现，单机的Hash table如何实现能节省内存，如何做

concurrency control，如何实现mutex之类的。

// Mutex is basically mutual exclusion. Only one thread can acquire the resource at once. When one thread acquires the resource, no other thread is allowed to acquire the resource until the thread owning the resource releases. All threads waiting for acquiring resource would be blocked.

Semaphore is used to control the number of threads executing. There will be fixed set of resources. The resource count will gets decremented every time when a thread owns the same. When the semaphore count reaches 0 then no other threads are allowed to acquire the resource. The threads get blocked till other threads owning resource releases.

In short, the main difference is how many threads are allowed to acquire the resource at once ?

Mutex --its ONE.

Semaphore -- its DEFINED_COUNT, ( as many as semaphore count)

面试准备：

========

F家的算法：

1. F家的题基本上都是Leetcode 的原题和变种。把leetcode的题研究透就OK了。

2. 跟F家的HR 聊过， 如果你想拿到面试官的strong recommendation, 需要在一

轮面试中做完两道题。每题15-17分钟完成，包括和面试官讨论，写代码，以及写test

case 的时间，同时尽量bug free，不一定要optimal solution。

3. 时间很紧，所以要多练习白板码，多练习在白板上跑test case。写多了就会发

现，白板码上写出bug的概率比用电脑写低很多，因为白板上可以通过图表的形式很直

观的跑test case，很容易发现bug。

4. 面试的时候，自己带fine tip marker， 比粗的笔写代码快很多。

G家的算法：

复习经典算法，推荐看一下Sedgewick 教授的算法书。http://algs4.cs.princeton.edu/home/

相比算法导论，我更推荐这本书，因为这本书的算法是用Java而不是伪代码实

现的，而且代码写的非常简洁而优雅。

    Sedgewick教授的书里没有 DP专门的章节，看看算法导论作为补充。

3. G家喜欢考各种tree：prefix tree，augmented binary search tree \(with

rank and select APIs), segment tree，binary index tree （1D and 2D),

interval tree, kd tree, quad tree.

4. G家喜欢考几何题，推荐：

       topcoder的教程：http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/

       Sedgwick的介绍几何算法（sweep line之类）的video：https://www.

youtube.com/watch?v=Igr6yONkpIQ

5. G家关于设计棋类游戏的AI的题，基本上都可以用MinMax 算法解决: http://neverstopbuilding.com/minimax

6. G家和F家都会考 Thread-Safe data structure和 Threading Pool，推荐阅读C

++ concurrency in action的第六章和第九章 http://www.manning.com/williams/

系统设计：

 1. 我基本没有web development的经验。和我一样0经验的同学可以先上一门课，

推荐Reddit Cofounder 开的web development

的课( 讲义和课程project都非常好）：https://www.udacity.com/course/viewer\#!/c

-cs253/

 2. 对于distributed system不了解的同学，推荐coursera上的Cloud Computing

Concept：https://www.coursera.org/course/cloudcomputing

 3. 系统设计里边，最重要的部分是Data Storage和Data processing。

     Data storage包含：

          a. Distributed File System: 推荐看一下GFS的paper和FB Haystack

Photo storage的paper

          b. NoSQL Data storage: 推荐看一下Big Table的paper，了解一下

Cassandra 的架构：Cloud Computing Concept的课有讲

          c. Memcache

     Data processing：

          看一下Map-Reduce的paper。了解一下Map-Reduce能解决什么问题。如

何做job scheduling等等。

 4. 板上大牛收集的题库：https://www.evernote.com/shard/s21/sh/c2035c38-

1a80-4fd4-8c93-8ca0ad9ffb48/35079ac1bf5ae3ea

     大多数题，解题的时候，按三步走：

           a. 如果数据量小，如何在单机上实现。

           b. 如果数据量大，如何sharding data，如何实现scalability

           c. Fault tolerance，考虑有node failure和message loss的时候这

么处理。

这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要

是design scalable distributed systems 这里只讨论如何准备这种题目

== 入门 ==

对于0基础的同学们下面的资料可以按顺序开始看