f design question 总结

同主题阅读：f design question 总结

分类： 面经2013-08-06 13:05 29679人阅读 评论(1) 收藏 举报

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. 任给一个手机的位置信号(经纬度)，需要返回附近5mile 的POI
这个这里有讨论，这题貌似nyc很爱考...
http://www.mitbbs.ca/article0/JobHunting/32476139_0.html


6. Implement second/minute/hour/day counters
这题真不觉得是system design，但万一问道，还是要有准备，貌似在总部面试会被问
道....
这个帖子有讨论
http://www.mitbbs.com/article_t/JobHunting/32458451.html


7. facebook photo storage，这个不太会被问起，但是知道也不错
https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919


8. 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


另外推荐一些网站
http://highscalability.com/blog/category/facebook
这个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

如果你这些基本的东西都还知道，那么我觉得你就和大部分毫无实际经验的人差不多一
个水平...
能做的就是一点一点去准备，如果你还有充足的时间的话，建议从你面试的那家公司的
engineering blog看起，把人家用的technology stack/product都搞清楚，然后在把能
找到的面试题都做一遍呗....我们做coding题说白了不也是题海战术...而且你如果坚
持看下去，真的会看出心得，你会发现很多地方都有相同之处，看多了就也能照葫芦画
瓢了...

再有就是面试的时候应该怎么去approach这种题，我说说我的做法
1. product spec/usage scenario 和面试者confirm这个东西到底是做什么的
可以先列出来几个major functionality，然后有时间的话，再补充一些不重要的
把你想的都写下来

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

以上是question specific的东西，
这个讲完了，我们可以讲一些每道题都是用的，比如说
怎么scale/怎么partition/怎么实现consistency，这些东西，可以套用到任何题上



当然了，我们遇到的题和解题的方法可能都有些出入，不见得每道题有一个路数下来，
最重要的是，讲题的时候要有条理，画图要清楚，保持和面试官的交流，随时问一下人
家的意见。

我能想到的就这么多，欢迎大家交流，希望大家都能找到理想的工作.

block Objective C 用法

首先，block是objective C的object, 可以装在NSArray和NSDictionary里面。

我们可以define一个block like this

void (^simpleBlock)(void);
block is just like a variable, and you can provide a value to it later. block就像一个class的变量
simpleBlock = ^{
        NSLog(@"This is a block");
    };
我们也可以定义像这样，就如同一个局部变量
void (^simpleBlock)(void) = ^{
        NSLog(@"This is a block");
    }

Block也可以带有返回值和参数

  double (^multiplyTwoValues)(double, double) =
                              ^(double firstValue, double secondValue) {
                                  return firstValue * secondValue;
                              };

    double result = multiplyTwoValues(2,4);

    NSLog(@"The result is %f", result);

onsite
F：1.find bad version, 比如isgood(version 1) = true, isgood(version 30) =
false, 找出第一个出错的version
   2.BST inorder tranverse
   3. 把string转化成floating number(stof)
behavior question的最后烙印来了一道按列打印tree，follow up是不用hashmap存
node的水平距离，用vector存，如何做，onepass，不准先求树的width
   4. system design: 每个record有个很大field，比如年龄，性别，爱好等。给一个
field的组合，比如小于25岁，爱好体育，query满足这些组合条件的用户个数

L:
1.max point on line/ (如何不是整数坐标如何处理，需要改写hashmap的compare）
2.special container add/remove/removeRandom at O(1): array + hashmap

3.k-way sort given a stream iterator, vector,
4.product of other elements; 考虑1个0 和2个0 的情况
5.实现movemem( void* src, void* dest)

6.system design: tiny url
7.host manager那轮最后问了一个，如何在不影响功能的情况下，把一个data center
的数据复制到另外一个新的data center去。

G：
1. find all rotation symmetric numbers less than N digits,  16891 -> 16891,
2. give integer, 12345, 返回 32154
    give a target  string and list of strings, find the longest string that
has target as prefix, follow up, stream of target string, 用trie，每个节点保
留最长string信息。
3. integer array add one
    rotation abc->bcd->cde, give a list of strings, group them if them are
rotations.
居然给我laptop，然后直接上面写，然后debug通过，给test case通过

4. given grid of colors, coordinate of a point and its color, find the
perimeter of the region that has the same color of that point.
    print all morse code given the length constraints, short “*” takes one
, long “——“takes two. (find a bug in the code) 就是排列组合的典型题
5. design: chromecast, how to know which app can be supported? There is a
cloud that can give the information to the chrome cast, appID, deviceID,
cache design. 

No offer。发面经供大家参考，5轮
1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
      （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
(string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
,b,b,b,a,c,bb, bbb, bb, abbba.

2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长[连续]
路径。
例如（括号对应上面node）  [修改：还有条件是 连续]
   树：                     2
                 |            |            |                |
                5            7          3                 6
         （|       | ）（   | ）   （|）         （|       |）
            6       3         2          4             5       8
                                 |
                                  3

返回3因为 （2-3-4） 这条线。优化要求时间O(n)


3.时间区间合并问题，leetcode上有相似题，关键词interval

4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
(3)完全平方解集，做一个：int minsol（int i）。
比如1=1^2 所以minsol(1)返回1,
2=1^2+1^2 返回2,
4=2^2或者4个1^2,1比4小， 返回1，
12=2^2+2^2+2^2或者3^2+3个1^2返回3.

5.有一个游戏，他说是fishing game，给一个数组vector Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector& Basket）；

 一个BST, 给你一个区间, 返回结点值全部在区间内的子树的结点个数.
比如:
2
1 3
区间 [1,2], 只有子树1,
返回结点个数1 .

系统设计面试题目总结