Facebook面经汇总(上篇)



  • 面经1:
    楼主周一去的Facebook Menlo Park Office Onsite,因为是实习所以只面一轮。
    面试官是一个中国大哥,人挺nice,一上来就问要不要中文面~问了一下背景和两个project,都答得还不错。看看表已经过去15分钟了,开始做题。题目其实也挺常规的,Binary Tree Serialization & Deserialization,要求将一个任意的二叉树转换成一个链表(对应Java里面的List数据结构)。
    原题:
    https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)
    楼主之前准备过不少二叉树的题目,唯独没准备到这一道,只好硬着头皮现想。想到之前做过一个将Binary Search Tree转换成链表的题目,楼主本能觉得用Pre-Order Traversal可以解决问题。面试官问如果保障还原的二叉树和原来的一致,楼主给的解法是记录每个节点左右子树的节点个数,存成一个三元组,这样就能很容易断出链表内根节点、左子树、右子树的范围,然后递归还原。面试官感觉一开始是没有想到这个解法的(后来我看了一下网上的主流解法,也确实都是存null或者各种marker,没有看到存子树个数的解法)。不过楼主解释之后面试官表示logically sound,可以写代码了。看看表,已经又过去了10分钟,面试只有20分钟的时间了。因为每个function都需要一个driver和一个helper rfunction,基本上把一面墙给写满了。楼主一开始没有想到计算子树内节点个数的有效解法,直接写了一个function递归统计,被面试官指出时间复杂度太高。另外在deserialize部分边界判定没有做好。面完已经超时15分钟,面试官很遗憾地告诉我我的implementation不行,就差直接说你挂了,当时心里非常难过……只能怪自己刷题不够,基础不够扎实了。

    其实后来仔细想了一下,我给的解法是可以更好的。首先只需要存左子树的节点个数就可以了,因为这样就可以确定出左右子树在链表中的边界,从而将链表分为三部分来递归处理。这样空间需求量刚好两倍于原节点个数,也是比较优秀的解法。统计左子树节点个数可以这样做:在处理每一个节点的时候,先将节点值和随便一个整数(比如0)放入链表中,然后记录下链表的当前大小。之后递归调用处理左子树。处理完左子树后,再获取一次链表的当前大小,和之前记录的大小求差再除以2,就能知道左子树的元素个数了。这样就只需要O(1)的时间完成每个节点的处理,总体时间复杂度也就是O(n)。

    补充一下timeline:
    内推:9月底
    HR约电面:10月初
    电面:11.7(中途因为接不到电话延期过一次)
    HR约Onsite:11.11
    Onsite:12.4
    HR约电话:12.9
    Offer:12.12
    祝大家好运!

    面经2:
    就一道题 : regular expression 前面聊了十分钟项目,
    这个面试官着重强调想看我的thingking process,第一次遇到这种类型的。。于是我把我的dp方程全部写到注释中讲解清楚了才开始写code
    最后面试官指了个地方,有bug,我改了,然后问了下我的时间复杂度和空间复杂度。

    面经3:
    大概九月中下旬请我的同学内推的FB,之后大概十月初收到的消息。但是期间HR又失踪的大概两三周,陆陆续续的拖到了今天才完成的第一轮电面。特别感谢内退的同学和今天面试官国人大哥。LZ在西雅图一家公司工作了半年多点,最近也是陆陆续续刷题准备跳槽。在职刷题感觉有些力不从心啊。

    今天中午十二点,面试官是一位国人大哥,准时打来电话。一上来介绍了一下自己的情况,然后让LZ说了一下在组里大概做的东西。LZ有点渣口语,说了半天不知道面试官听懂了几句。

    之后先面了一道post-order traversal iterative,LC原题,但是LZ之前一直不会,昨天晚上和同学聊天,同学帮我压的题。当时拿到题LZ还是有点激动的。之后面试官让LZ解释,LZ渣口语又来了,说了半天不知道面试官大哥听懂了多少,有点对不起.后来又面了一道非常 LC77, 也是一道非常常规的题。只是求的是 一共有多少种组合,当时LZ脑子抽了。。没想出来,直接返回的List<List<>>,然后算的大小。估计国人大哥看到这里也觉得LZ是扶不起来的阿斗,也没再追究。现在想想这解法这真挺无语的。希望以后的面试时候别再犯了。

    还是挺感谢国人大哥的,面的都是最最常规的题,很多地方没有死扣,要不可能就跪的很惨。

    面经4:
    三题:
    1.山羊拉丁
    2.统计词频
    3.恐龙题
    全部面经题no surprise

    面经5:
    从内推到收到一面通知,等了三周多快四周的样子。一面后刚好是感恩假期,等了一周没有反应,手上又有一offer要due,发邮件催来了二面。面完后三天收到正式的offer。

    Round 1:
    lc 297. output 是一个list。 写完后面试官给了一个follow up,貌似是c++的问题,但楼主没有怎么用过c++,具体什么忘了。
    Round2:
    lc 29 和 二叉树转化成循环双链表
    题目不难,到现在也觉得有点虚。希望继续努力争取好的表现。

    推荐给大家一个CS群,都是找工作的大家聚在一起,定时会在群里分享IT咨询、工作机会,交流大牛的工作心得。
    0_1482529249602_782300758280234399.jpg


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待