一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3980|回复: 20
收起左侧

Facebook 电面面经 full-time job

[复制链接] |试试Instant~ |关注本帖
CauchyNash 发表于 2016-4-24 23:22:25 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Facebook - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
曾经的一个师兄内推的职位,想做scientist但是FB家一开始木有职位选择全是SE,过了后才能通过bootcamp选组,被逼无奈面了SE,只刷了10天题所以跪的很正常。

东部时间晚上6点电话准时响起。是2-1面试,主面的小哥很年轻能听出是个刚入职左右的fresh Indian小哥,旁边的一个不怎么说话的是image processing组的senior engineer (虽然我的简历和Image processing没有很大关联)。
小哥先寒暄了几句,让我介绍下自己的背景以及为什么选择了FB家,然后进入技术面试环节。

第一题:给定一个数列,比如1234,将它match到字母上,1是A,2是B等等,那么1234可以是.鐣欏璁哄潧-涓浜-涓夊垎鍦
ABCD
但是还可以是12是L,所以1234也可以写作
LCD 或者
AWD. 鍥磋鎴戜滑@1point 3 acres
-google 1point3acres
给定一个定长的序列(可以非常长),请给出solution输出所有可能的字母组合(consecutive的,只要连续的组合)。

.鏈枃鍘熷垱鑷1point3acres璁哄潧我的思路:大概的思路就是递归,一个类似斐波那契数列的公式,省内存就用动态规划来做。. visit 1point3acres.com for more.

第二题:给出N个序列,比如2个序列A,B,没个序列包含若干的区间,比如
A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]

没个序列内的区间没有overlap但是序列之间的区间没有这个限制。请给出solution合并N个序列到一个序列 Final,Final内依然没有overlap的区间。
比如上例 Final就是 [1,6], [8, 20].

我的思路:粗暴循环 + interval红黑树


然最后还是挂了,个人觉得原因是不够熟练(觉得面我的题目还是有点偏难。。。),所有题目只给出了伪代码思路,而且均没有完成简单case的validation(时间不够),第二题伪代码刚写完就被叫停了。

还是自己准备不足,同时也坚定了我不做码农做scentist的决心(实在不擅长coding啊啊啊啊啊啊啊)。

评分

4

查看全部评分

mdyuki1016 发表于 2016-6-9 09:16:16 | 显示全部楼层
第一题, decoding way的变体, 也是使用dp, 但是 时间复杂度 O(n * m). 稍微改了下code 在leetcode跑了一遍.

public class Solution {
    public int numDecodings(String s) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if (s == null || s.length() == 0) return 0;
        if (s.charAt(0) == '0') return 0;
        List<List<String>> dp = new ArrayList<List<String>>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for (int i = 0; i < s.length()+1; i++) dp.add(new ArrayList<String>());
        dp.get(0).add("");-google 1point3acres
        dp.get(1).add(""+(char)('A'+(s.charAt(0)-'0')));
        for (int i = 2; i < dp.size(); i++) {
            int a = s.charAt(i-1) - '0';
            int b = (s.charAt(i-2)-'0') * 10 + a;
            if (a != 0) {
                char c = (char)('A' + a);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                for (String ss : dp.get(i-1)) {
                    dp.get(i).add(ss+c);
                }
            }
            if (b >= 10 && b <=26) {
                char c = (char)('A' + b);
                for (String ss : dp.get(i-2)) {
                    dp.get(i).add(ss+c);. visit 1point3acres.com for more.
                }
            }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
        return dp.get(s.length()).size();
    }
}
回复 支持 4 反对 0

使用道具 举报

997562971@qq.co 发表于 2016-8-1 04:04:12 | 显示全部楼层
第一题要输出所有结果,妥妥的DFS啊。。。DP是用来解决“一共多少种情况”的。
第二题。我感觉应该用个min heap。comparator 里比较每个interval的start。开始先把所有序列第一个interval放进heap里。然后取出一个,放入一个。外面要记录两个pointer: head,tail。如果取出的start比tail小,head不变,tail取tail和end里大的;如果start比tail大,head等于start,tail等于end。
回复 支持 1 反对 0

使用道具 举报

sclookout 发表于 2016-4-25 00:50:33 | 显示全部楼层
感觉上第二题,应该是类似于multi-merge吧。因为他强调了每一个序列都没有重合的,这样的话直接暴力循环就没有利用这个条件了。不知道楼主怎么觉得?或者谁有个靠谱的解?求大神们指导
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-25 02:19:10 | 显示全部楼层
sclookout 发表于 2016-4-25 00:50
感觉上第二题,应该是类似于multi-merge吧。因为他强调了每一个序列都没有重合的,这样的话直接暴力循环就 ...

这个题如果List是arryalist的话, merge之后, 如果要删除掉一些Interval, 复杂度为哦o(n)。
如果用linkedlist的话, 虽然删除是o(1),不过traverese要o(n)啊

有最优解么?
回复 支持 反对

使用道具 举报

ben_child 发表于 2016-4-25 05:56:39 | 显示全部楼层
没有面试题是需要用红黑树解决的= =肯定是两个指针扫一遍就好啦,第二题。用最简单的算法就行
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-4-25 06:08:04 | 显示全部楼层
sclookout 发表于 2016-4-25 00:50
感觉上第二题,应该是类似于multi-merge吧。因为他强调了每一个序列都没有重合的,这样的话直接暴力循环就 ...

同意。累似merge k sorted array
回复 支持 反对

使用道具 举报

jose1901 发表于 2016-4-25 06:30:43 | 显示全部楼层
第一题backtracking,第二题merge multilist
回复 支持 反对

使用道具 举报

jose1901 发表于 2016-4-25 06:32:12 | 显示全部楼层
multi sorted list
回复 支持 反对

使用道具 举报

jose1901 发表于 2016-4-25 07:37:28 | 显示全部楼层
哦,看错第一题,应该用dp即可
回复 支持 反对

使用道具 举报

shepherd001 发表于 2016-4-25 15:38:45 | 显示全部楼层
确实有感觉,PhD的时候其实并不注重coding。Scientist的职位现在很少啊,我也想找,未遂……
回复 支持 反对

使用道具 举报

 楼主| CauchyNash 发表于 2016-4-25 23:22:23 | 显示全部楼层
shepherd001 发表于 2016-4-25 15:38
确实有感觉,PhD的时候其实并不注重coding。Scientist的职位现在很少啊,我也想找,未遂……
. visit 1point3acres.com for more.
先从industry的postdoc做起吧以后慢慢爬,现在phd严重通胀做了industry的postdoc拿着业界工资还可以做些学界的事情,以后也可以往academia发展
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-26 01:34:05 | 显示全部楼层
感谢楼主的分享,自己练习下保持手感。第一题类似于LC 320 GEneralized Abbreviation这种结构,好像fb和谷歌很爱考。见了好多题了。代码如下:
public class Solution {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    public List<String> generateCombination(String s) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        List<String> ret = new LinkedList<String>();
        if (s == null || s.length() == null) {
            return ret;
        }
        String[] map = {"",
                        "A", "B", "C", "D",
                        "E", "F", "G", "H",. visit 1point3acres.com for more.
                        "I", "J", "K", "L",
                        "M", "N", "O", "P",
                        "Q", "R", "S", "T", 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        "U", "V", "W", "X",
                        "Y", "Z"};
        dfs(s, ret, 0, "", map);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        return ret;
    }
   
    void dfs(String s, List<String> ret, int index, String item, String[] map) {
        if (index >= s.length()) {
            ret.add(item);
            return;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
        
        int i = Integer.parseInt(s.charAt(index));
        dfs(s, ret, index + 1, item + map[i], map);
        . 1point3acres.com/bbs
        //如果可以有两位数,比如"24"就可以对应"X",就要继续递归。而"27"就没有的对应。
        if (index < s.length() - 1) {
            int j = Integer.parseInt(s.charAt(index + 1));
. 鍥磋鎴戜滑@1point 3 acres            if (i * 10 + j <= 26) {
               dfs(s, ret, index + 2, item + map[i * 10 + j], map);
            }
        }
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}

时间上,个人觉得要求所有可能性,而且不是那种是否的题目,应该没办法用dp提速了,也没办法用带记忆的dfs搜索提速了。
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-4-26 02:17:46 | 显示全部楼层
不就是decode way和merge interval的变形么?
回复 支持 反对

使用道具 举报

shepherd001 发表于 2016-4-26 05:16:02 | 显示全部楼层
CauchyNash 发表于 2016-4-25 23:22
先从industry的postdoc做起吧以后慢慢爬,现在phd严重通胀做了industry的postdoc拿着业界工资还可以做些 ...

我想做research,但是不想在academic圈子里混,很纠结啊
回复 支持 反对

使用道具 举报

 楼主| CauchyNash 发表于 2016-4-26 06:36:07 | 显示全部楼层
shepherd001 发表于 2016-4-26 05:16
我想做research,但是不想在academic圈子里混,很纠结啊

去industry做scientitist吧虽然位置少的可怜。。。
回复 支持 反对

使用道具 举报

poormm 发表于 2016-6-2 03:28:29 | 显示全部楼层
facebook的scientist也是按码农的流程面试吧?
回复 支持 反对

使用道具 举报

 楼主| CauchyNash 发表于 2016-6-3 14:22:31 | 显示全部楼层
poormm 发表于 2016-6-2 03:28
facebook的scientist也是按码农的流程面试吧?

是的字数补丁
回复 支持 反对

使用道具 举报

chen6145 发表于 2016-6-29 12:26:50 | 显示全部楼层
lz求解为啥dp可以省内存?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-6 14:14:00 | 显示全部楼层
mdyuki1016 发表于 2016-6-9 09:16
第一题, decoding way的变体, 也是使用dp, 但是 时间复杂度 O(n * m). 稍微改了下code 在leetcode跑了一遍. ...

可以backtracking, 这样dp的时候不用每个idx都存下完整的list of string,只需要存下当前这步可能的选择, 然后最后backtracking出所有答案
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 08:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表