周末了,八卦下什么是好的manager

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4389|回复: 36
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
xuepanchen 发表于 2017-8-4 09:08:16 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩

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

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

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

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

1. 介绍现在职位做的事,还有Why Facebook。
1. Flatten Binary Tree To Linked List变形。和LC原题不同的是,返回的是Doubled Linked List,并且顺序是树的Inordered Traversal。
2. 给一个质数数组,没有重复元素,比如[2, 3, 5],要求返回所有元素之间可能的乘积,比如结果是[2, 3, 5, 6, 10, 15, 30],每个数最多用一次,结果不一定需要是有序的。
. 围观我们@1point 3 acres
每道题写完后都会让你手动过一遍test case,说一说每一步的结果,还问一下时间复杂度。第一题的复杂度是O(N),N是树上的元素数目。第二题的复杂度我认为是O(2^N),N是所给数组的长度。因为每个元素都有两种选择,包括或者不包括。

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

. 1point 3acres 论坛
祝各位找工工作,或是学习顺利。

评分

参与人数 1大米 +40 收起 理由
candy_shmily + 40

查看全部评分


上一篇:口袋宝石店面壹
下一篇:Offerup onsite

本帖被以下淘专辑推荐:

我的人缘0
littlegrass 发表于 2017-8-4 14:36:02 | 显示全部楼层
本楼: 【顶】   100% (4)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
第二题我是这样子做的,有没有更好的答案?. 1point3acres

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

  6. public void helper(int[] nums, int start, int curr, Set<Integer> result) {
  7.         for (int i = start; i < nums.length; i++) {. 1point3acres
  8.                 result.add(curr * nums[i]);
  9.                 helper(nums, i+1, 1, result);
  10.                 helper(nums, i+1, curr * nums[i], result);
  11.         }.留学论坛-一亩-三分地
  12. }
复制代码


评分

参与人数 1大米 +5 收起 理由
DavidLi210 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
lixiaonin 发表于 2017-8-9 01:10:33 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
看我这样做那个质数乘积可不可以:. 1point3acres
用1做辅助,最后再除掉

def products_of_primes(arry):
        res = [1]
        for num in arry:
                ans = []
                for p in res:
                        ans.append(p)
                        ans.append(p*num)
                res = ans
        res.pop(0)
        return res. from: 1point3acres

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]

补充内容 (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
        res.pop(0)
        return res
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 03:53:28 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
shurui91 发表于 2017-8-4 10:05
同问 第二题如何DP

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

vector<int> product(vector<int> input) {
    vector<int> result;
    for(int element : input) {
        int curr_size = result.size();
        for(int pos = 0; pos < curr_size; pos++) { result.push(element * result[pos]); }
        result.push_back(element);
    }
    return result;
}
回复

使用道具 举报

我的人缘0
mimighost007 发表于 2017-8-4 09:50:19 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  94% (86)
 
 
5% (5)  踩
第二题不是质数么,那就是2^n-1个不同的乘积么
回复

使用道具 举报

头像被屏蔽
我的人缘0
brn 发表于 2017-8-4 09:57:34 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

我的人缘0
shurui91 发表于 2017-8-4 10:05:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (61)
 
 
6% (4)  踩
同问 第二题如何DP
回复

使用道具 举报

我的人缘0
chris612ku 发表于 2017-8-4 10:21:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (15)
 
 
0% (0)  踩
楼主. 围观我们@1point 3 acres
想请问一下第一题也要自己build一个tree跑test case吗?
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 03:25:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
mimighost007 发表于 2017-8-4 09:50
第二题不是质数么,那就是2^n-1个不同的乘积么

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

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 03:27:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
littlegrass 发表于 2017-8-4 14:36-google 1point3acres
第二题我是这样子做的,有没有更好的答案?
. 留学申请论坛-一亩三分地
这个解法就是我一开始写的,会有重复的答案。
回复

使用道具 举报

我的人缘0
yikehongxin 发表于 2017-8-5 03:42:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (231)
 
 
8% (22)  踩
没有重复的prime,直接再怎么互相组合乘机,也不会有完全相同的因子吧,且又是最小的因子,所以不可再分解,因此,谨慎的质疑有重复的可能。
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 03:44:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
littlegrass 发表于 2017-8-4 14:36. 1point 3acres 论坛
第二题我是这样子做的,有没有更好的答案?

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

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 03:46:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
brn 发表于 2017-8-4 09:57
第二题怎么dp 不就是个裸dfs吗
.本文原创自1point3acres论坛
DFS当然是可以的,你用一个SET去过滤重复的值。但是因为你在计算过程中会产生重复,所以时间上并不是最佳的。
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 03:46:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
chris612ku 发表于 2017-8-4 10:21
楼主
想请问一下第一题也要自己build一个tree跑test case吗?

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

使用道具 举报

我的人缘0
edyyy 发表于 2017-8-5 03:48:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (80)
 
 
15% (15)  踩
这个质数组题,结果的个数是 (2^n)  - 1吧,就是所有集合数去掉空集,因为是质数 a*b != c*d, 所以子集元素乘积各不相同。
回复

使用道具 举报

我的人缘0
edyyy 发表于 2017-8-5 03:50:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (80)
 
 
15% (15)  踩
Flatten Binary Tree To Linked List变形。LC原题是前序遍历,返回的是原来的数据结构,现在返回的是中序遍历,用Doubled Linked List有什么特殊意义吗?
回复

使用道具 举报

我的人缘0
littlegrass 发表于 2017-8-5 04:07:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
xuepanchen 发表于 2017-8-5 03:53
这个是我的做法,对于每一个新的数,我们将它和每一个之前所产生的结果相乘,然后也放到结果数组里,再是 ...
. Waral 博客有更多文章,
谢谢!祝楼主拿到onsite
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 04:22:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
daguanyuan 发表于 2017-8-5 03:42
没有重复的prime,直接再怎么互相组合乘机,也不会有完全相同的因子吧,且又是最小的因子,所以不可再分解 ...

我所谓的重复是指在DFS的计算过程中会产生重复的结果,需要用一个SET去过滤掉重复的中间结果。可以参考下水道那层的做法。
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 04:23:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
edyyy 发表于 2017-8-5 03:48
这个质数组题,结果的个数是 (2^n)  - 1吧,就是所有集合数去掉空集,因为是质数 a*b != c*d, 所以子集元素 ...
. 1point 3acres 论坛
对的,一共是(2^N) - 1个答案,所以我说复杂度是O(2^N)。
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-5 04:24:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
edyyy 发表于 2017-8-5 03:50
Flatten Binary Tree To Linked List变形。LC原题是前序遍历,返回的是原来的数据结构,现在返回的是中序 ...

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

使用道具 举报

我的人缘0
mellon 发表于 2017-8-5 08:01:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
找到一個視頻 可是是circular double linkedlist
https://www.youtube.com/watch?v=Dte6EF1nHNo
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-22 07:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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