Facebook Interview Misc Part 2


http://www.1point3acres.com/bbs/thread-191077-1-1.html
FB家对new grad 或者毕业后工作短于一年的同学是可以不考design的。

对phd 毕业或者毕业超过一年的童鞋是要考desig.鏈枃鍘熷垱鑷�1point3acres璁哄潧
phone interview 只考coding。
onsite 经典4轮 Coding/"Ninja" (2)  Design/"Pirate" (1)  Conversation/Career Background & Trajectory/"Jedi" (1)-google 1point3acres
根据面试情况可能会加试一轮。

算法 & coding : 个人感觉 leetcode 刷透做熟悉就够了。 fb 家不是以难度取胜。
他家一般都是leetcode medium level的题目,一般是原题或者小变种。-google 1point3acres
他家coding的难点是bug free, 细节和追问。
比如说给你一个 binary tree, 每个节点存一个整数值,让你求每个layer的平均数。
这个题目看上去很简单, 但是要注意输出, 3和4 平均是3.5, 如何你用java 解,输出是整数,那么你的结果就不准确。. 鍥磋鎴戜滑@1point 3 acres
这些细节点一点要问清楚,如果考官让你自己定,那就选保险一些的。
另外就是bug free, 这里bug free指的是没有逻辑和算法错误,变量名啥的写错了也没啥。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
另外coding 轮最重要的一点还是communication, 考官问完问题以后,
一定要clearfy 一下题目的意思和输入输出然后把你的思路和考官说一下,之后考官同意,再写code。 他家很注重交流,如何你听完题目,就直接写code。
就算是最优解,你也会fail,因为没有交流的过程。 coding 轮不光考算法,也会看你的交流能力如何。

design: 他家的design 有难有易。  基本部分另外一帖子说过了直接贴过来。
能准备的准备好了,剩下的就是放宽心态,好好发挥了。实力到了,那么胜率自然高。
fb家大牛很多,design比较看运气。

design 轮是有技巧性的。
一般过程是 
1 问清 requirement 5~10 分钟
2 high level design(设计flow 相关api 和数据存储)
3 细节设计,详谈flow, api

一定要按顺序来。不要直接跳到第三步。
下面几段话感觉很有用。lz是实战后得出的这些总结。
ab和fb都跪在design,之后调整策略,胜率就上升了。

准备design主要是参考了这个网站:
http://www.hiredintech.com/system-design/
感觉还是挺有用的。其他就是mitbbs上那位大牛给的一些资源
http://www.mitbbs.com/article_t/JobHunting/32777529.html


Conversation/Career Background : 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
自己的工作经验和project要准备好,这个没啥好说的。
下面几个是常见的 behavious question:

1 First, ask some questions about Facebook, do you use Facebook?2 Why you like it? 
3 Which part of it should be improved? 
4 What challenge you face in your pre project and how you result it?
5 Why facebook 
6 My current project and how I scale our applications.
7 包括以前的成就,怎么说服别人做design的修改,说服不通怎么办。
8 FB specifically (vs. other companies)


附录FB 常见design 问题=============================
1 Design a web crawler with fixed set of resources.

2 Design a real-time type-ahead search-phrase predictor which presents the top-10 ranked search strings that begin with a given prefix. 3 Design timeline的group权限,比如说user发一条status可以选择对某个group的好
友可见。题目很简单,但是会讨论到facebook用户规模的估算,服务器估算,social  graph的存储。
感觉system design只要讲个大概思路就行,面试官不会去纠结太细节的东西。
4 design偏向设计存储结构
5 system design: 设计key-value store,直接列了一大堆从client到server的要求,
基本处处陷阱,经验这里比较重要,光按面试准备基本没效果。
6 搜索栏的自动完成功能7 那个给你一个点, 然后有几个million的POI, 找出最近的20个。。。- geoHash我说那个Z distance。。 two dimension变成一个dimension, 那个面试官说, 没听说过Zdistance, 不行。。。
8 find close coordinates9 上来讨论了20分钟的如何设计data structure表示fb的friend和follower两种关系,各种结构的tradeoff。我边讨论边猜是不是要我clone graph,然后默念怎么还不让
我写code。果然,deep copy。不过最后讨论的data structure 和lc上有点不同,dfs
思路是一样的。整个过程很愉快,abc男也是好多positive feedback。面试结束了还和
我激动的说了半天来fb的种种好处(工资,休假之类的)
10 deadlock设计11 问为什么Facebook,对Facebook的哪个feature最喜欢,为什么喜欢,然后这个feature还有什么不足。
12 之后让给他一个非常specific的例子说当你和同事出现技术上的冲突的时候,应该怎么解决,问的特别细,
特别深入。
13 从头到尾面无表情,口音也很难懂,我当时就觉得不妙,
果真就跪在这轮。design news feed API, 这题我准备过,但是按pull/push model准
备的,还准备了pub/sub model,就是给每一个friend都建一个queue,推送一份news,
算准备过的题。但他不考这些,根本不让我说关于aggregator tier或者database tier
的东西,主要focus API怎么写,input/output, feed里图片怎么存,想mention 
friends怎么存,怎么做multi device sync。我觉得他的考点似乎在data 
serialization/deserialization这边
?感觉和他交流就是隔着窗户喊话,一直在猜,所
以差评也是必然的。。。

14 设计题,传输10G的data到5个data center,每个data center 有1000的
节点
。三哥从问背景就开始找茬,面试过程中要求解gossip protocol的微分方程, 被
黑。
15 设计iPhone Find Friends 的后端。Geohashing + DHT解之16 设计题问得很细,比如DHT如何实现,单机的Hash table如何实现能节省内存, 如何做
concurrency control,如何实现mutex之类的。

17 system design: 每个record有个很大field,比如年龄,性别,爱好等。给一个field的组合,
比如小于25岁,爱好体育,query满足这些组合条件的用户个数
18 设计一个facebook的搜索引擎,这个引擎能搜索出包含关键字的facebook动态。没有讨
论太多前端的,主要在讨论架构和存储。
给出了倒排索引来存储index,以及讨论了下如何存储facebook的动态(key-value 存储
)如何handle hot keyword。面试官人很好,引导我的思路。
19 system design白人大叔, 有个function是List<id> getNearest(int x, int y
){}, 假设从mobile上在地图上点一下,然后返回改点附近的所有建筑location。怎么
设计data structure以及data scheme
20 System design设计手机上读取photo feeds的app。
    功能: 读取好友的最近图片
               阅览好友的相册
    要求: 满足功能的同时减少对手机的能耗。
21 design:tiny url。
22 System design: instgram
23 Culture fit:
有200M个用户,现在让你进行分组,将他们分成大概20个组,每个
组里大概有10M的用户,尽量让用户interaction多的在一起
24 design看了下几篇文章,知道个大意,google的mapreduce, file system, big table,. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
fb的memcache, unicorn。其他看到过的觉得还不错的design资料,最后一个常见题目. from: 1point3acres.com/bbs 
汇总可以过过看,很有帮助:. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
http://blog.csdn.net/v_july_v/article/details/7382693
https://www.youtube.com/watch?v=-W9F__D3oY4 
http://www.mitbbs.com/article_t/JobHunting/32741713.html
另外建议稍微准备下常见数据类的写法(包括generic programming), 我倒是没碰到其.1point3acres缃�
他一些concurrency, database, NP-hard之类的题目..
25 设计一个facebook功能:在一个post下面,如果有了新的comment,可以自动显示
不需要刷新后再显示。
27 design facebook chat
28 写一个sequential 多线程pool。实现f(Runable r)要求caller不可以block,但是
在pool里面要一个跟这一个的运行。
29 设计类似gogle地图系统,从A点到B点的算法已经有了。整个地图大概有好几亿条线
段组成,这个系统的市场占有大概30%。要求在小于1妙的时间里算出结果。估算需要多
少台机?要怎么样保存地图,怎么cache
30 然后面试中有个印度人问了个问题,就是如果系统出问题了,有个size很大的log如何
从里面找出相关的信息,同学说直接search关键字,但是面试官不满意也没给提示,所
以不知道怎么回答。
31 国人面试官面出的 design:Shorten Url。面试官人非常nice,可是自己答的一般
,在此谢谢他。

32 google的mapreduce, file system, big table,
fb的memcache, unicorn。其他看到过的觉得还不错的design资料,最后一个常见题目
汇总可以过过看,很有帮助:
http://blog.csdn.net/v_july_v/article/details/7382693
https://www.youtube.com/watch?v=-W9F__D3oY4 
http://www.mitbbs.com/article_t/JobHunting/32741713.html
另外建议稍微准备下常见数据类的写法(包括generic programming), 我倒是没碰到其
他一些concurrency, database, NP-hard之类的题目.. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
33 设计一个SparseVector (就是一个超长的vector,大部分elements都是0)的
class,实现dot product的操作。follow-up1:如果一个vector很长(millionsof non-
zeros), 另一个vector很短(hundredsof  non-zeros),如何优化。
follow-up2:如何利用index之间的关系(比如设计class的时候规定按照递增的原则存non-
zeroelements的index)进一步优化。
34 system Design:设计一个K recent contact 的service,就是当用户把鼠标点到
chat对话框的时候,自动弹出K个最近的联系人。follow-up是如果要弹出K个最熟悉的
人怎么设计,以及资源估计(需要多少台机器来做数据存储,多少个处理request等等
)。

35 design准备:板上有几个design总结贴,非常管用。我就是照着 flamingos和beidapig
的两个总结贴,大概看了看,学习了不少知识。
http://www.mitbbs.com/article_t/JobHunting/32777529.html
http://www.mitbbs.com/article_t/JobHunting/32984309.html
补充内容 (2016-5-20 02:51):
面试经验谈(facebook,airbnb,google,linkedin,amazon
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

FB 面经 phone & onsite  攻略 附录题库呦 
http://www.1point3acres.com/bbs/thread-1910...
. 1point3acres.com/bbs
补充内容 (2016-5-20 02:52):.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
airbnb 面经 phone interview & onsite 附录题库呦  http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

补充内容 (2016-5-20 02:52):. visit 1point3acres.com for more.
lz的刷题攻略。。 http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

补充内容 (2016-5-20 02:53):
补充的几个帖子里 有高频的机经(design & 算法)

http://yaozonggao.com/blog/?p=73

1. How would add new Facebook members to the database of members, and code their relationships to others in the database?
2. If you were an animal what kind would you be and why?
3. What is the difference between Facebook ads and Google Ads?
4. Should Facebook be available in China?
5. What do you see as Facebook’s biggest challenge in the next five years?
6. What is the limitation of certain facebook features? How do you improve them?
http://www.1point3acres.com/bbs/thread-137068-1-1.html
5/11/2015 Phone Screen: 
很水的两道题:1) move all non-zero elements to left. 2) find first buggy version 面完HR通知我总部没坑了,就把我扔给seattle office的HR了。。
JEDI,这轮没什么好说的,瞎扯淡,给的算法题是给一个string由一堆单词加上不等的空格分隔而成,让做一下处理使得最后输出每个单词间只相隔一个空格。. 1point 3acres 璁哄潧
第二轮:
NINJA,这轮就开始坑爹了,是个三哥面的,上来就一副冷漠+蛋疼的表情,给了个copy random list的题,我一看我嚓原题啊,肯定是拿来warm up的,快速给三哥讲一遍用hashmap的解法,准备开写呢,只见三哥蛋蛋的看着我,来了一句:“恩,很好,但是有木有更好的解法?“我一听,整个内心就顿时是崩溃的。。这是要我写O(1) space解法的节奏啊。。。我虽然leetcode刷了好几遍,但是这题的O(1) space解法早就忘得一干二净。。原因在于之前面试也遇到过几次这道题,但是面试官都是只要hashmap的解法,我后来准备的时候也觉得O(1) space的解法也算是一种比较tricky的解法,实际面试的时候上来就写这种解法很明显就是背题啊。。也就再没写过这种解法了。。所以当时我很想给面试官做出一种”你特么是在逗我么“的表情,但是还是忍住了。。最后还是自己YY出了一个解法,但是是那种不能处理random pointer指向之前的结点的解法。也把代码写出来了,三哥看了看觉得木有BUG,然后就蛋蛋的跟我说恩挺好,时间到了,你下去再好好想想能完全解决这个问题的O(1) space的算法吧,有啥问题要问我?不问我闪啦。 我也就蛋蛋的看着他装模作样的问了个bootcamp的问题。。。
这轮又是坑爹,按照HR的说法这轮应该是system design,但是三哥进来又给我出了道算法题。。。我当时有点疑惑,但是还以为FB看我经验没满一年,把我的design面换成coding了。。也就没表示什么,算法题是吧,写!题目是给一个string,一个set of string, 问string里面是否包含一个substring,使得这个substring的任意一个prefix + suffix能组合成set里面的任意一个string,能就返回true,否则返回false。写到最后写出了个小BUG,而且三哥提醒后找了半天没找出来。。。最后发现是有个substring()没给end index。。。


是这样,我少说了个条件,输入除了一个string和一个set of string,还有个整形变量len表示set里面每个string的长度(也就是说set里的string长度都是一样的)。比如input string is "whoisyourdaddy", input set 包含两个 string "whu" and "ddy",那么function应该返回true,因为给的input string里面的substring "whoisyou" 的 prefix "wh" 和 suffix "u" 组成了 "whu",而另一个substring "daddy" or "ddy" 的 prefix "d" 和 suffix "dy" 组成了 "ddy",因此这个例子里set里面所有的string都可以在input string里面找到一个substring的一个prefix+suffix组合构成。

第四轮:-google 1point3acres
这轮是个国人大哥,进来给我说好这轮是pirate,也就是system design!我当时就有点懵了,然后问他是不是面试换顺序了?他跟我说木有啊。然后我问他那这一轮是最后一轮?他跟我说不是啊,这一轮完了还有一轮ninja呐。我当时心里就有无数草泥马奔腾而过。。国人大哥也是不留情面,问了道large scale下怎么设计一个根据关键词查询status的service。我自然又是一顿瞎扯,神马invert index, consistent hashing, 想到什么扯什么。然而这并没有什么卵用。。不论扯到什么大哥都要刨根问底,我到最后就完全招架不住了。。大哥的表情也就越来越蛋疼了。。这轮结束后我觉得基本就没戏了,design面这么烂基本是硬伤,弥补不了了。
第五轮:
上轮被虐的奄奄一息,马上就又来了两个geek大叔补刀了。。一道determine if there is a subarray in the given array that sum up to a given target,一道trie上面的regex search。。。我第一道写得其实还挺快,但是举例test case给geek大叔讲通代码花了不少时间,最后第二道题只剩15分钟,真是风一般的速度把第二题写了个差不多。。geek大叔看上去态度模棱两可,也是一副冷冷+蛋蛋的表情。。。



Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts