《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2781|回复: 36
收起左侧

[2017/08/03] Facebook电面面经

[复制链接] |试试Instant~ |关注本帖
xuepanchen 发表于 2017-8-4 09:08:16 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
朋友的内推,约得今天的电面。面试官是个国人小哥,人挺好的。

1. 介绍现在职位做的事,还有Why Facebook。. Waral 鍗氬鏈夋洿澶氭枃绔,
1. Flatten Binary Tree To Linked List变形。和LC原题不同的是,返回的是Doubled Linked List,并且顺序是树的Inordered Traversal。. from: 1point3acres.com/bbs
2. 给一个质数数组,没有重复元素,比如[2, 3, 5],要求返回所有元素之间可能的乘积,比如结果是[2, 3, 5, 6, 10, 15, 30],每个数最多用一次,结果不一定需要是有序的。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

每道题写完后都会让你手动过一遍test case,说一说每一步的结果,还问一下时间复杂度。第一题的复杂度是O(N),N是树上的元素数目。第二题的复杂度我认为是O(2^N),N是所给数组的长度。因为每个元素都有两种选择,包括或者不包括。

第二题做得一般,一开始写了个DFS算法,在手动跑test case的时候发现会产生重复,立马重写了一个DP的,写的时候还有个小bug也是在跑test case的时候改正了。希望小哥高抬贵手别太计较哈哈。


祝各位找工工作,或是学习顺利。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

lixiaonin 发表于 2017-8-9 01:10:33 | 显示全部楼层
看我这样做那个质数乘积可不可以:. From 1point 3acres bbs
用1做辅助,最后再除掉

def products_of_primes(arry):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        res = [1]
        for num in arry: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                ans = []
                for p in res:
                        ans.append(p)
                        ans.append(p*num).鏈枃鍘熷垱鑷1point3acres璁哄潧
                res = ans
        res.pop(0). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return res

print products_of_primes([2,3,5])
# [5, 3, 15, 2, 10, 6, 30]

print products_of_primes([2,3,5,7])
# [7, 5, 35, 3, 21, 15, 105, 2, 14, 10, 70, 6, 42, 30, 210]. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2017-8-9 01:22):
搞复杂了。。。应该这样就好:
def products_of_primes(arry):
        res = [1]
        for num in arry:
                ans = []
                for p in res:
                        ans.append(p * num)
                res += ans. from: 1point3acres.com/bbs
        res.pop(0)
        return res
回复 支持 3 反对 0

使用道具 举报

littlegrass 发表于 2017-8-4 14:36:02 | 显示全部楼层
第二题我是这样子做的,有没有更好的答案?

  1. public List<Integer> products(int[] nums) {
  2.         Set<Integer> result = new HashSet<>();
  3.         helper(nums, 0, 1, result);
  4.         return new ArrayList<>(result);. 1point 3acres 璁哄潧
  5. }

  6. public void helper(int[] nums, int start, int curr, Set<Integer> result) {
  7.         for (int i = start; i < nums.length; i++) {. 鍥磋鎴戜滑@1point 3 acres
  8.                 result.add(curr * nums[i]);.1point3acres缃
  9.                 helper(nums, i+1, 1, result);
  10.                 helper(nums, i+1, curr * nums[i], result);
  11.         }
  12. }
复制代码


回复 支持 3 反对 0

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 03:53:28 | 显示全部楼层
shurui91 发表于 2017-8-4 10:05
同问 第二题如何DP

这个是我的做法,对于每一个新的数,我们将它和每一个之前所产生的结果相乘,然后也放到结果数组里,再是把这个数本身也放到数组里,为了之后的计算。

vector<int> product(vector<int> input) {
    vector<int> result;. From 1point 3acres bbs
    for(int element : input) {
        int curr_size = result.size();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for(int pos = 0; pos < curr_size; pos++) { result.push(element * result[pos]); }. 鍥磋鎴戜滑@1point 3 acres
        result.push_back(element);
    }
    return result;
}
回复 支持 1 反对 0

使用道具 举报

mimighost007 发表于 2017-8-4 09:50:19 | 显示全部楼层
第二题不是质数么,那就是2^n-1个不同的乘积么
回复 支持 1 反对 0

使用道具 举报

brn 发表于 2017-8-4 09:57:34 | 显示全部楼层
第二题怎么dp 不就是个裸dfs吗
回复 支持 反对

使用道具 举报

shurui91 发表于 2017-8-4 10:05:38 | 显示全部楼层
同问 第二题如何DP
回复 支持 反对

使用道具 举报

chris612ku 发表于 2017-8-4 10:21:30 | 显示全部楼层
楼主
想请问一下第一题也要自己build一个tree跑test case吗?
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 03:25:31 | 显示全部楼层
mimighost007 发表于 2017-8-4 09:50
第二题不是质数么,那就是2^n-1个不同的乘积么

恩对的,一共有(2^N)- 1个答案
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 03:27:41 | 显示全部楼层
littlegrass 发表于 2017-8-4 14:36. 1point3acres.com/bbs
第二题我是这样子做的,有没有更好的答案?

这个解法就是我一开始写的,会有重复的答案。
回复 支持 反对

使用道具 举报

daguanyuan 发表于 2017-8-5 03:42:55 | 显示全部楼层
没有重复的prime,直接再怎么互相组合乘机,也不会有完全相同的因子吧,且又是最小的因子,所以不可再分解,因此,谨慎的质疑有重复的可能。
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 03:44:40 | 显示全部楼层
littlegrass 发表于 2017-8-4 14:36
第二题我是这样子做的,有没有更好的答案?

不好意思我没看仔细,没看到你用了SET。这个当然是对的,但是在计算过程中很多值被重复计算了,比较浪费时间。
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 03:46:05 | 显示全部楼层
brn 发表于 2017-8-4 09:57
第二题怎么dp 不就是个裸dfs吗

DFS当然是可以的,你用一个SET去过滤重复的值。但是因为你在计算过程中会产生重复,所以时间上并不是最佳的。
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 03:46:41 | 显示全部楼层
chris612ku 发表于 2017-8-4 10:21
楼主 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想请问一下第一题也要自己build一个tree跑test case吗?

面试官会给你一个例子,你就照着他给的例子手动跑一边你的程序。
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-8-5 03:48:26 | 显示全部楼层
这个质数组题,结果的个数是 (2^n)  - 1吧,就是所有集合数去掉空集,因为是质数 a*b != c*d, 所以子集元素乘积各不相同。
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-8-5 03:50:15 | 显示全部楼层
Flatten Binary Tree To Linked List变形。LC原题是前序遍历,返回的是原来的数据结构,现在返回的是中序遍历,用Doubled Linked List有什么特殊意义吗?
回复 支持 反对

使用道具 举报

littlegrass 发表于 2017-8-5 04:07:42 | 显示全部楼层
xuepanchen 发表于 2017-8-5 03:53
这个是我的做法,对于每一个新的数,我们将它和每一个之前所产生的结果相乘,然后也放到结果数组里,再是 ...

谢谢!祝楼主拿到onsite
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 04:22:27 | 显示全部楼层
daguanyuan 发表于 2017-8-5 03:42
没有重复的prime,直接再怎么互相组合乘机,也不会有完全相同的因子吧,且又是最小的因子,所以不可再分解 ...
.1point3acres缃
我所谓的重复是指在DFS的计算过程中会产生重复的结果,需要用一个SET去过滤掉重复的中间结果。可以参考下水道那层的做法。
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 04:23:18 | 显示全部楼层
edyyy 发表于 2017-8-5 03:48
这个质数组题,结果的个数是 (2^n)  - 1吧,就是所有集合数去掉空集,因为是质数 a*b != c*d, 所以子集元素 ...

对的,一共是(2^N) - 1个答案,所以我说复杂度是O(2^N)。
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-5 04:24:19 | 显示全部楼层
edyyy 发表于 2017-8-5 03:50
Flatten Binary Tree To Linked List变形。LC原题是前序遍历,返回的是原来的数据结构,现在返回的是中序 ...

我也不知道有什么特殊意思,估计就是为了不出原题吧,做法都是一样的。
回复 支持 反对

使用道具 举报

mellon 发表于 2017-8-5 08:01:39 | 显示全部楼层
找到一個視頻 可是是circular double linkedlist
https://www.youtube.com/watch?v=Dte6EF1nHNo
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-18 10:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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