脸书系统设计面经资料整理汇总

回馈地里，攒一攒RP，分享一下自己搜集整理的2017脸书系统设计题目归纳分类，方便大家复习。
在这里也感谢前人分享的所有MJ资料，资料全部来自地里。


我把同样或者类似的题目都归到了一起，序号链接是该题目相关的面经贴子，对应的每个段落的文字也出自相关的讨论。
我的建议是不要错过原贴下面的回复和讨论，有时候思路或者得分点也许就包含在里面，当然自己思考加理解才是最重要的，多看一些相关的video，文档或者blog会很有帮助。


顺便求大米=）


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


设计是 news API design, 也是面经了。   注意 pagination. 看看twitter 的 API developer's guide 会有帮助


一个music app，选出 top 10 songs


[url=](3)[/url] 类似翻译系统，但是要写具体接口函数，讨论很多很细节的问题，答得不好，所以就不说了




[url=](4)[/url] 设计轮：网页event售票系统， 随便聊聊画画conponent图和数据表，讲讲哪里容易failure，说说API，信用卡信息谁处理，遇到大流量怎么分流，俄国哥们儿进来的时候脸绷得挺吓人，聊完了出去的时候挺开心的，估计还可以


[url=](5)[/url] 设计一个“脸书上消耗时间”的功能，记录每天每个用户在脸书上消耗的时间，要求尽可能的在客户端计算量少，要求设计相应数据库以及api的输入以及输出. 计算每隔多久向服务器发

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

"2">[url=](12.3)[/url]
设计太噗呃head，然后还有时间剩下，大哥问，还能怎么优化。然后我说：应该可以按照用户习惯优化吧。然后刚好大哥就是做matrix根据指标返回这个功能好不好，这里挖坟了。（我其实没做过matrix的东西）我只想出用了可track：response time，用户有没有多用我们的系统，有没有新用户增加之类的。然后根据这些信息来改善系统


过几天收到消息，要加面一轮设计，然后前两天去面了设计，一个在搜索组做了5年的，问了typeAhead，虽然之前准备过，大的架构答得还行，但是问了几个具体的问题，答得很不好所以估计要挂。这些具体的问题还是值得思考一下的，我给大家列一下，希望能帮到后面的人：1. top n hot key word怎么生成，问了下map reduce的东西 2. typeAhead这里的hot key words考虑多久的时效性，比如你是按照1 month，1 week，1 day 还是1 hour的数据给出hot key words。3. 大家都知道要用Trie去存数据，并且Trie是放在cache里的，那么这个cache什么时候去更新？怎么更新？要不要加TTL？你更新的这个cache的频率会对用户query的时效性产生很大的影响，并且你更新也会对数据库和服务器造成额外的负担，你怎么去平衡。最后加了一个问题说如果这个服务是面向多个国家的，过了一段时间你发现你的推荐在某些国家点击率很高，有些国家点击率很低，你要怎么优化。总之都和你之前的一系列答案有关。问得相当的细


typeahead也算是各个公司面试的高频题了，试着回答一下，大家一起讨论讨论吧 鏉ユ簮涓


1. top n hot key word怎么生成，问了下map reduce的东西. 鐗涗汉浜戦泦,涓

审核花了3天。。。 也因为没有权限，没法发布带大量链接的贴子。回头有空的时候我重新整理一份发到G drive或者dropbox上，希望对大家有帮助

typeAhead 的话基本就是用trie， 生成方法就是每次用户search 或者选中一个suggestion ， 就把对应的leaf count++， 然后用这个新的count更新所有parent node的hot word list。 感觉和map reduce 没关系。。。
2. typeAhead这里的hot key words考虑多久的时效性，比如你是按照1 month，1 week，1 day 还是1 hour的数据给出hot key words。
思路：如果按1 day来那么就无法展现1个月的情况，如果按1个月的来，那么无法展现新的热词
方法一：可以按 每天/每小时 平均值来算
方法二：根据不同的场景选不同的， 比如google search 可以按一年来，新鲜事搜索可以按1个月来，新闻搜索可以按一天算
3. 大家都知道要用Trie去存数据，并且Trie是放在cache里的，那么这个cache什么时候去更新？
每次用户搜索后就更新
怎么更新？
因为只是往trie里加分支，所以可以直接加，不用锁
要不要加TTL？
为了防止cache过大可以加， 可以每隔一段时间对trie清理剪枝

你更新的这个cache的频率会对用户query的时效性产生很大的影响，并且你更新也会对数据库和服务器造成额外的负担，你怎么去平衡。
multithread scheduling, Trie updating thread has lower priority

4. 如果这个服务是面向多个国家的，过了一段时间你发现你的推荐在某些国家点击率很高，有些国家点击率很低，你要怎么优化。总之都和你之前的一系列答案有关。问得相当的细
方法一 不同的国家不同的Trie,但这样人们无法看到别的国家的人的热搜
方法二 考虑各国人口，比如 count = count in country A/ population of country A
方法三 有一些common的 hot word 还有一些country specific 的hot words

最后我觉得这种题要想在45分钟内想清楚说清楚别人用5年时间做出来的东西是不可能的，重要的是展示思路吧，这种思路既要有一定发散性，又要有一定合理性，但是也不要太在意是否以及如何实现的问题

最后吐槽一句，我当时靠系统设计也考了翻译系统，然后因为唯独那一轮不好就直接给我挂了。。。。关键是翻译系统我在工作中还是做过的。。。。事后想可能需求没问清楚吧，看到是做过的太兴奋了就直接说了解法，但是忘记交代工作中一些特殊需求。。。。所以切记要问清需求啊。。。。

design type a head, 这个就是正常的data collection和data query, data query用in memory trie 從如何boostrap trie到trie sharding, 到end-to-end operation

(13)
Design a simple message system.  是个国男大哥，很严肃，但估计也没有刁难我。就是基本的怎么发信息，怎么收信息，然后怎么通知receiver，如果有新的消息了

(14)
design: design fb inbox search    —> just focus the post

(15)
设计一个 hack pokemon go的 app。 用户不用出门就能抓到pokemon

(16)
(16.1)
一个找最近朋友系统

设计推荐好友的service end to end. design的问题比如算一下这个service read和write的throughput，database partitioning，怎么存好友推荐要用到的数据，怎么更新权重（比如有些被推荐的好友从来不被点击，那下次就不应该在排在前列），粗略的讲讲如何进行好友推荐的排序（哪些因素可以影响推荐的权重）

(17)
(17.1)
(17.2)
(17.3)
设计个类似yelp的东西

设计 poi

我当时答geohash是可以的，剩下的就是sql存，找公共前缀，然后再是算空间，机器数，再就是怎么sharding 分布式，建index找，pre/cache result，底层怎么存。 整个flow差不多就是这样，中间有些细节和面试官讨论了下

我答得应该不算好，因为比较糊涂面试官到底想看啥。
基本idea就是geohash。把地表分成小的rectangle，比如10 square ft。里面存这块区域的point of interest比如商店，邮局等等。区域构成树的结构，大的区域下面子节点是小的区域。按区域shard。这样由client发的request得到position，然后找到对应的rectangle，再从这个rectangle 向周围BFS一定量的步数找到所有POI按远近排，然后同样距离内按其他的criteria如用户preference排。返回数量由client端决定。比如web端可以返回多一些，比如100个，mobile端返回少点，比如20个
这个感觉没那么好因为面试官喜怒不形于色，反馈比较少，让我不清楚他想要什么，或者该往哪方面展开

被问道的题目是POI。其实这个题目我是准备过的，但是面试中不同的是，不可以用exsiting lib like google s2 or geohash，需要自己给出hash的方式。在这个地方纠结了很久，导致之后很不顺畅，一直在围绕我hash的方式问问题。最后结束的时候，面试官说this works，我觉得是挂了，但还是希望面试官抬一手，feedback不要写太差.
Update: 听了某位同学的意见，因为觉得过于focus在geohash algorithm design，导致完全没有时间来进行真正的system design  (use quadtree instead of geohash)

设计一个系统可以查询10 miles之内的建筑物。我就说用geohash，将建筑物存在key-value类的NoSQL中。查询时查prefix。面试官并没有质疑什么，然而feedback却不好。现在回想起来，可能是我分析column familar NoSQL和Key Value NoSQL的tradeoff的时候没有讲清楚。我也不是很清楚到底应该用哪种更适合，如果大神们看见了请解释解释

design POI, geoHash解之。要求先估算需要多少machine，再说geohash。白板画需要几部分和之间关系，写backend POI meta data，算需要多少machine来存。最后有拍照

(18)
设计谷歌搜索，涉及 表， 文件系统，缓存，脸书专用缓存论文，分片，备份

(19)
(19.1)
设计一个单机的KV缓存
Design memcache. 答LRU应该可以, 但问了很多bottleneck和threadsafe

首先给了一堆数据：机器72G内存，16个core，10T硬盘.
需要实现的API是：get(key), put(key, value), delete(key)
key max size 1k, average 100bytes, value max size 1M, average size 1k.
考虑用啥protocol，locking，memory management。如何lock，如何减少lock提高performance
如何保证顺序

(20)
短url，全程我在说，他也没问什么问题

(21)
Design twitter feed system

news feed就是问 - 比如这些是用户写的一条post，有用户基本信息，内容，图片，时间等等（当时还画了一下基本ui），如何拿到这些信息，如何存储. 还问了如果有新的feature，比如加了一个button，如何让没有update app的人仍然流畅使用他们现有的。scale倒是没细问。时间有点长了也记不起来剩下问了什么了。。

(22)
设计一个上传video, 可以看自己或者朋友的video的. 说实话, 整个过程, 不是特别清楚, 他到底想看什么...所以就是他想看哪块, 我就细讲一下那块. 我自己感觉沟通不是太畅, 最后, 时间到了. 系统设计这种东西, 本身就是开放型的讨论, 运气, 人缘很重要, 这也不是我能把握的

(23)
设计一个在线游戏的排名系统。游戏是回合制的，每一回合结束后都会获得一个分数。玩家可以在游戏中添加好友，每个玩家有任意个好友。在每一回合结束后，游戏界面需要弹出两个排序的表格：（1）玩家及其所有好友的最高分数排序top 10；（2）玩家的分数在所有用户（million级别）最高分数中的排名，以及该排名的前十位、后十位的玩家及分数

(24)
design ETF arbitrage system: 每一个ETF由许多不同的stock组成， ETF有两个价格， 一个是underlying asset price, 就是所有stock加起来的价格， 一个是市场目前报价， 也就是
class ETF{
     double market_price;
     double underlying_asset_price;
     vector<pair<ticker, qty>> underlying_asset
}
有feed不断提供所有ETF的报价和每个stock的报价， 寻找arbitrage的机会（当underlying_asset_price 不等于market_price的时候就可以arbitrage ）
这道题没见过还按照之前的正常想法设计不同的service group， 面试官不太满意， 后来才反应过来这个是要设计一个ultra low latency system， 而不是设计分布式系统

(25)
Design 一个 status post 系统，支持存储status和搜索包含某一个string或者某几个string的所有statuses

(26)
design是设计post和friend的搜索 支持多个关键词

(27)
Desgin an Advertisement (AD) statistic system. 每次用户登录的时候，系统都会show几个广告给他。广告总共有K种类别，可以认为K<=10。用户看到广告可能会点击，Click Through Ratio (CTR) = 用户点的广告数量/给用户看的广告数量。注意若同一个广告被用户点击了多次，只算一个click。设计一个系统，answer the following two types of queries:
1. Given a user, return his CTR for all types of ADs.
2. Given an AD type, return its average CTR ovre all the users.
Follow ups:
a. What if K becomes very large? for example, we consider each product as one type, thus K  can be as large as 10000.
b. New query type:  Given an AD type, return the top-X users with highest CTR. 1< X < 100
个人感觉这个题似乎更偏向数据库设计？我当时其实有点懵，花了很多时间解释如何设计relationalDB, 处理这些query,以及可能的优化，e.g., 这个application明显是write-heavy的，所以caching(delayed write)会很有用。答完没有什么感觉，但面试官表示满意"Looks your design works well". 但是面无表情所以不知道是不是套话

太厉害了感谢楼主连米都不用！！！

flgt2014 发表于 2017-8-17 08:40
审核花了3天。。。 也因为没有权限，没法发布带大量链接的贴子。回头有空的时候我重新整理一份发到G drive ...

楼主辛苦，楼主拿到fb的offer了吗？

多谢楼主！！ 厉害了

这个帖子应该置顶，加精华：） 赞楼主！