一亩三分地论坛

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

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

Facebook Phone Interview

[复制链接] |试试Instant~ |关注本帖
fireisborn 发表于 2015-11-26 09:44:22 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 校园招聘会 - 技术电面 |Passfresh grad应届毕业生

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

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

x
11.20 facebook 第一面,今天收到 onsite 通知,没有面到高频题,但题目还是蛮简单的,上面经
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一次遇到欧洲人面试我,是一个法国小哥,听声音以为很年轻,但发现居然是 Instagram 的 Tech Lead 我差点吓尿了,一开始简单自我介绍了一下,然后有问 Why Facebook ,我把我之前去听他们 tech talk 的一些感觉讲出来,感觉这部分都算答得不错

然后就是题目是 unique paths,最基本的 DP 问题,写完之后他会一直问你怎麽优化,我基本上是优化 space complexity O(m * n) -> O(m + n),结果意外的是他还问我能不能优化,我想说不知道可不可以用两个 variable 表达,结果就被阴了...因为答案其实是不能优化下去的,所以要知道怎样就是最优解也是很重要的~该停就要停,不然就中招,还好我后来有即时悬崖乐马跟他说我懂了,不能继续优化下去了,然后他又问说如果把  path 的过程用 d 表示 move down,r 表示 move right,可不可以从其中一个 path 的表示算出有几种 path ? ex. 3 * 2 matrix ,其中一个结果是 “rrd” 能不能从这一个结果推断有几个  unique paths? 这也很简单,就是排列组合而已,m * n 答案就是 (m + n - 2)! / ((n - 1)! * (m - 1)!) ,后来想一想这其实就是这题的最优解,法国小哥真是循循善诱啊,感恩感恩,不过这解法再扩展到如果中间有障碍的情况就完全不适用了,而且容易 overflow,没有很把这解法放心上就是了(汗
. from: 1point3acres.com/bbs
然后又聊一下他的 team 在干嘛还有跟他问一些建议,就结束了
这个面试官有跟我提到一个不错的建议是说以后可以先说说这个算法的 time complexity & space complexity 再跟面试官沟通要写哪一个,但我基本上都有先跟面试官确认要写了吗才开始写...或许他是期待我可以做更完整的分析吧,总之学习了
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
感觉整个面试还蛮顺的,即将 onsite,求点大米&RP~

评分

3

查看全部评分

窗外一棵树 发表于 2016-1-5 09:45:00 | 显示全部楼层
向楼主请教一下 这个题的time complexity 是 O(m + n) 吗  . Waral 鍗氬鏈夋洿澶氭枃绔,

根据这个 (m + n - 2)! / ((n - 1)! * (m - 1)!) 的解法 感觉 O(m+ n) 就能算出来-google 1point3acres

但就算是 优化过的 space complexity 为O(m+n) 的解法,至少要循环 m*n 次,不就是O(m*n)了吗


回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2016-1-5 19:06:51 | 显示全部楼层
窗外一棵树 发表于 2016-1-5 09:45
向楼主请教一下 这个题的time complexity 是 O(m + n) 吗  

根据这个 (m + n - 2)! / ((n - 1)! * (m -  ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. 對
2. 你是開固定的 list ,每次就是用那個空間而已,所以還是線性空間,並沒有因為你 iterate 就增加使用的空間
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2016-1-6 02:45:51 | 显示全部楼层
fireisborn 发表于 2016-1-5 19:06
1. 對
2. 你是開固定的 list ,每次就是用那個空間而已,所以還是線性空間,並沒有因為你 iterate 就增 ...

我可能没表达清楚。 我比较困惑的是time complexity 为什么是O(m + n ) 而不是O(m*n)呢. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

code大概是这样的吧:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for (int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[j] += dp[j-1];
            }. visit 1point3acres.com for more.
        }
这个感觉循环了m*n次,所以时间复杂度不是O(m*n)吗
回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2016-1-6 10:40:42 | 显示全部楼层
窗外一棵树 发表于 2016-1-6 02:45
我可能没表达清楚。 我比较困惑的是time complexity 为什么是O(m + n ) 而不是O(m*n)呢

code大概是这 ...
-google 1point3acres
我的文章寫的是優化 space complexity 啊 lol
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2016-1-6 11:19:05 | 显示全部楼层
fireisborn 发表于 2016-1-6 10:40
我的文章寫的是優化 space complexity 啊 lol

我有看懂关于space complexity的部分啦,但是对于time complexity 还是有点疑问。所以想请教一下。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

这题的time complexity应该是 O(m*n) 还是O(m+n)呢

因为那个二层嵌套循环感觉应该是O(m*n)
. 1point 3acres 璁哄潧
但是根据(m + n - 2)! / ((n - 1)! * (m - 1)!) 这个解法,感觉O(m+n) 就能解出来了啊
回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2016-1-10 14:18:57 | 显示全部楼层
窗外一棵树 发表于 2016-1-6 11:19
我有看懂关于space complexity的部分啦,但是对于time complexity 还是有点疑问。所以想请教一下。

这 ...

二層循環是 O(m * n),數學解法是 O(m + n)
回复 支持 反对

使用道具 举报

lyburke 发表于 2016-2-5 06:41:16 | 显示全部楼层
求问LZ为什么space complexity是O(m + n)啊。。。只用O(m)不可以吗
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-9 02:36:29 | 显示全部楼层
同好奇,应该time space O(m)就可以了吧?
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2016-2-10 13:11:21 | 显示全部楼层
a598165394 发表于 2016-2-9 02:36. from: 1point3acres.com/bbs
同好奇,应该time space O(m)就可以了吧?

我也觉得是O(m),不需要O(m+n)
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2016-2-10 13:12:31 | 显示全部楼层
  1. public class Solution {
  2.     public int uniquePaths(int m, int n) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.         
  4.         if(m==0 || n==0) return 0;
  5.         if(m==1 || n==1) return 1;
  6.         int[] path = new int[m-1];
  7.         path[0] = 2;
  8.         for(int i=1;i<path.length;i++){
  9.             path[i] = path[i-1] + 1;
  10.         }
  11.         for(int j=2;j<n;j++){. 1point3acres.com/bbs
  12.             path[0] = path[0] + 1;
  13.             for(int i=1;i<path.length;i++){
  14.                 path[i] = path[i] + path[i-1];
  15.             }-google 1point3acres
  16.         }
  17.         return path[m-2];
  18.     }
  19. }
复制代码

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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