Facebook第一轮电面面经

发信人: smilenceyu (smilence), 信区: JobHunting
标  题: Facebook第一轮电面面经
发信站: BBS 未名空间站 (Fri Nov 15 19:24:54 2013, 美东)

是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。

题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。

分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit

这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。

中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只有两端的时候，会比较有用，而
且我这个办法维护min和max每次都要做一次，应该有更好的。对average case是没有用
的。

最后问了下time cost，就是O(lgn)和o(n)，分别对应average和worst，他说怎么保证
balanced，就说就可以了，我说可以用红黑树或者AVL，或者先找中位数插入（后来一
想应该是先排序）

用sorted array行不行，与BST比较优缺点（前者没overhead，但是无法动态插入和删
除）。似乎他还挺满意。

让我问问题之后就欢快的结束了。




--

※ 修改:·smilenceyu 於 Nov 15 19:35:41 2013 修改本文·[FROM: 71.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 71.]

http://www.mitbbs.com/article_t/JobHunting/32578309.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东家电价格服务大升级，30天包退 ， 更多京东优惠券