<
查看: 10410|回复: 24
收起左侧

Facebook 电面面经 full-time job

|只看干货
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   91% (22)
 
 
8% (2)    👎

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

给定一个定长的序列(可以非常长),请给出solution输出所有可能的字母组合(consecutive的,只要连续的组合)。

我的思路:大概的思路就是递归,一个类似斐波那契数列的公式,省内存就用动态规划来做。
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
目还是有点偏难。。。),所有题目只给出了伪代码思路,而且均没有完成简单case的validation(时间不够),第二题伪代码刚写完就被叫停了。

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

评分

参与人数 4大米 +108 收起 理由
lefthook + 3 感谢分享!
pengzewen37 + 5 感谢分享!
whdawn + 50
candy_shmily + 50

查看全部评分


上一篇:Salesforce电面
下一篇:Two Sigma Onsite 差评
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
第一题要输出所有结果,妥妥的DFS啊。。。DP是用来解决“一共多少种情况”的。
第二题。我感觉应该用个min heap。comparator 里比较每个interval的start。开始先把所有序列第一个interval放进heap里。然后取出一个,放入一个。外面要记录两个pointer: head,tail。如果取出的start比tail小,head不变,tail取tail和end里大的;如果start比tail大,head等于start,tail等于end。
回复

使用道具 举报

本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   97% (71)
 
 
2% (2)    👎
第一题, 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("");
        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);
                }
            }
        }
        return dp.get(s.length()).size();
    }
}
回复

使用道具 举报

本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
感谢楼主的分享,自己练习下保持手感。第一题类似于LC 320 GEneralized Abbreviation这种结构,好像fb和谷歌很爱考。见了好多题了。代码如下:
public class Solution {
    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",
                        "I", "J", "K", "L",
                        "M", "N", "O", "P",
                        "Q", "R", "S", "T",
                        "U", "V", "W", "X",
                        "Y", "Z"};
        dfs(s, ret, 0, "", map);
        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);
        
        //如果可以有两位数,比如"24"就可以对应"X",就要继续递归。而"27"就没有的对应。
        if (index < s.length() - 1) {
            int j = Integer.parseInt(s.charAt(index + 1));
            if (i * 10 + j <= 26) {
               dfs(s, ret, index + 2, item + map[i * 10 + j], map);
            }
        }
    }
}

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

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
感觉上第二题,应该是类似于multi-merge吧。因为他强调了每一个序列都没有重合的,这样的话直接暴力循环就没有利用这个条件了。不知道楼主怎么觉得?或者谁有个靠谱的解?求大神们指导
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
sclookout 发表于 2016-4-25 00:50
感觉上第二题,应该是类似于multi-merge吧。因为他强调了每一个序列都没有重合的,这样的话直接暴力循环就 ...

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

有最优解么?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
没有面试题是需要用红黑树解决的= =肯定是两个指针扫一遍就好啦,第二题。用最简单的算法就行
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (16)
 
 
11% (2)    👎
sclookout 发表于 2016-4-25 00:50
感觉上第二题,应该是类似于multi-merge吧。因为他强调了每一个序列都没有重合的,这样的话直接暴力循环就 ...

同意。累似merge k sorted array
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
第一题backtracking,第二题merge multilist
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
multi sorted list
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
哦,看错第一题,应该用dp即可
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
确实有感觉,PhD的时候其实并不注重coding。Scientist的职位现在很少啊,我也想找,未遂……
回复

使用道具 举报

 楼主| AK67 2016-4-25 23:22:23 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (22)
 
 
8% (2)    👎
shepherd001 发表于 2016-4-25 15:38
确实有感觉,PhD的时候其实并不注重coding。Scientist的职位现在很少啊,我也想找,未遂……

先从industry的postdoc做起吧以后慢慢爬,现在phd严重通胀做了industry的postdoc拿着业界工资还可以做些学界的事情,以后也可以往academia发展
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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