Facebook最近面经整理

ML intern
第一轮:
求两个array的dot product,follow up:如果是sparse array怎么办。用hashmap 存(idx,value),他说可以。再follow up,hashmap结构有点复杂,能不能用简单点的结构。我说用tuple。他说可以。结果有点紧张没写出来。。。小哥说时间差不多了,做第二题吧,给定一个string,里面是字母,打印出所有的permutation。这题很快写出来了。
第二轮
第一题validate palindrome。很快写完了。第二题应该是lru的变种.

Onsite:
第一轮 天竺人 讨论BQ + 一小题 网站原题, 记不清题号了 两个sorted array, 放到一个里
array a : “ 11, 14, 39, *, *, *”
array b :” 15, 26, 28”, output 到 array a “11, 14, 15,16, 18, 39 ”
第二轮 coding
LeetCode659的变种
午饭
第三轮 系统设计
web crawler + API limiter
第四轮 coding
LeetCode 124, 347变种

店面:
第一题就是设计个class, 用于检测有无cycle。

第二题给定一个文档,找到一组 word, 这两个word要求char一样,顺序不同。

店面:
给你一堆字符串,希望找到作为前缀的字符串,题目不是很难, 我给出的是 Tier数据结构,一个buildTier函数,一个Search函数, 时间太短,Tier写了改,改了写,最后search应该是有点小bug

onsite:
Prob 1: Powerset. Recursive + iterative / for loop
Prob 2: Binary search in a sorted array that has been rotated. Ext: what if there are duplicates
Prob 3: Find the perimeter of each island in a given 0/1 matrix. Ext: how to dedup islands with the same shape
Prob 4: ML design. Some NLP prediction task. Basic questions about data collection, loss function design, and so on. Don’t remember the details.
Prob 5: ML design. FB newsfeed ranking design. Basic questions about data collection, loss function design, and so on.

店面:
leetcode 238
leetcode 953

店面:
给一个字符串,要求出每个字符的频率
SQL题,给了两个表格,要求合并表格并求出某一要求列的所有结果
男女身高题,用hypothesis test方法,中间有提到p-value

onsite:
楼主只刷了100多题就去了,碰到的题其实都不难。碰了3轮TOP K, 一轮是behavior,简单讲了下想法,当时就发现quick select 算法没想清楚,结果下一轮倒霉催的又被让写quick select。一直以为quick select跟quick sort 不同,不用recursion,结果被中国小哥一脸鄙视的guide完全程。最后跟我说是amortized O(N), worst case O(n^2).
其实注意到quick select 这个算法也是地里几次有人在狗家说碰过,还被面试官提示。有一个帖子说提了一下有这个算法,但是没写,因为当场写容易写错,楼主也以为当场要写的机会不多,结果妥妥的跪。而且容易思维定势,一碰到top k的题目,上来先问面试官那K个要不要sort,面试官如果说不用,自己跳到自己挖的坑里去了。

最后一轮跟面试官说碰过Top K了,换了3次题,最后换了立扣124。大概有思路,没亲手写过。写倒是写的顺利,第二天回想有一个bug。但是面试官中国小妹很生涩,可能是在practice 面试,旁边有一个南美大哥,估计是reverse shadow吧。现场拍照了,我猜事后review bug被看出来了。后来又出了个Binary search。Binary search的边界处理一直是楼主的痛点,练过一个case,但很久以前了,模板也没想好,而且体力有限,就随便说edge case需要另外处理,时间也到了就草草过了。
design倒是feedback 不错。Design onlingJudge system. Behavior的话楼主觉得往FB core value上靠就行。

另一个感慨是,FB的国人实在太多,还都很年轻,优势且不论,入职后拼体力倒有点吓人。

店面:
刷了大概150題還是沒刷到的題…
跟wildcard matching 差不多
檢查P 在不在L 裡
其中 * 在p代表任何字符

L: [“foo”, “bad”, “boy”]
p: “f*o” -> true

p: fi* -> false

想了想說了trie的方法還是做不出來

90% 掛了…求安慰

店面:

  1. LC 252; Follow up 时间空间复杂度
  2. LC 253; Follow up 时间空间复杂度
  3. LC 257; Follow up 让我自己定义一个test case然后跑一遍

面经:
9.10 内推
9.26 hr打招呼
10.23 背靠背
10.30 通知加面
11.8 加面一轮
11.13 通知过coding填team match survey
11.28-29 四轮team match
12.4 电话加邮件给offer

三轮电面内容如下(顺序打乱了)

LC162 但是是找max,后续问怎么证明你这个bs的正确性,再问了如果是strict max呢(必须比左右两边都大,等于不行)

LC63 不是这一题,但是是一个极端变种,我感觉我看过有人做过但是找不到了,大概就是长方形格子,里面有各种block,能上下左右移动,找(从任意位置开始能达到的最远距离)里面的最小的

LC252 但是先问的是给一串intervals和一个新的interval,怎么判断新的interval和前面的有没有交集,假设前面的都没有交集

LC133 原题

没遇到最难的那几道题,但是也没答好,说实话没想到过了。感觉一定要多说话,我就没停下说话,写代码之前先讲思路,面试官说可以写的时候再写,coding的话除了流散那题,我基本都保证了一遍bug free,确实题也不难。面经题刷了三遍吧,但是最后面试的时候完全记不住了,就是凭本能在写,可能没白费刷了一年题的功夫。

一流儿后面找strict max的时候想着找O(log n),面试官看我折腾了半天没出来,说只有O(n),必须全走一遍,谢谢放我过TT。

63完全没做出来,就搞了个最次的暴力流+dfs,但是没写完时间不够了,中间写错了几个地方,面完感觉已经move on了。ps谢谢面试官小姐姐努力帮我,我感觉小姐姐已经竭尽全力在提示我想让我pass,但是我水平太低了让小姐姐失望了。

Team match的总结如下:

有几篇水文章,只用过UCI的数据,从没自己搞过数据,我感觉我挂在这上面了

  1. 填survey的时候可以多选几个,这样后面让挑自己想去的组的时候选项会多好多,我试过,只选两个可能后面只有两三个组可选,我填的时候有六七个组可以选。

  2. team match四个组没有一个组问具体的ML的知识,但是有两个组问了很多处理数据的问题,比如怎么选feature,为什么这么选,除了这些feature你觉得还有什么能够帮助做decision的,我们好多数据都是没有label的该怎么办啊,能不能搞个feedback loop什么的。剩下两个组就是他们讲他们组的东西,我讲一下我的项目。

  3. 感觉team macth不好说结果。我感觉我聊的最好的一个组没要我,即使那个面试官说了你来我们这很适合啊。最后只有一个组给了我offer,但是面试的时候我觉得那一轮是我表现最差的。

fb这家公司作为北美的血汗工厂,对bugfree的要求当然是最高的。 但是有题库,并要求对题目理解的深,一道题会有多个follow up,比较考基本功。

2 Likes

这题其实就是intersection of two arrays,leetcode 原题

我就一直没看懂这个题是啥意思

就是两个array同一个index的地方,必须都不是0,有一个是0就忽略。相当于非零的 intersection

Tuple 在Java的实现就是:AbstractMap.SimpleEntry

public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable

AbstractMap.SimpleEntry.hashcode()为什么用key.hashCode() ^ value.hashCode() ?

引用

        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
                   (value == null ? 0 : value.hashCode());
        }

就是说 key 和 value 都一样,就算是一样(同一个 object)

1 Like

他实际上说:AbstractMap.SimpleEntry 可以

FB intern 还考系统设计?

为什么sparse array, sparse matrix类的问题这么高频?

FB有behavior question吗?

有 project deep dive,有点bq成分