Facebook Intern 面经

刚面完FB一面，非常新鲜的面经！加州的黑人老大叔面的我， 求米！！！！！！！！！

您好！
本帖隐藏的内容需要积分高于 88 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 88 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

面试太紧张了，小哥人很好最后结尾给我feedback是不要太紧张， 感觉要没戏了！权限设低点，集点人品吧！

不如说是高中数学题，就是求+1，-1，0填在n和坑里和为0的情况
当n是偶数，n=2k, 有C(2k, k)种
当n是奇数，n=2k+1，有(2k+1)*C(2k, k)种

dgnb88 发表于 2019-10-30 08:22
 请问一下DP怎么做的呀，以及在index=0的时候可以往左走吗？

index = 0 不可以往左走
我是DP[n][currentIdx] = k 这么存的
n是还剩下多少步, currentIdx是现在在这个array的什么位置, k是当所有可能性的个数
DP[n][currentIdx] = DP[n-1][currentIdx]+DP[n-1][currentIdx+1]+DP[n-1][currentIdx-1]

ye8610116 发表于 2019-10-30 16:23
不如说是高中数学题，就是求+1，-1，0填在n和坑里和为0的情况
当n是偶数，n=2k, 有C(2k, k)种
当n是奇数，n ...

这样想问题不大，但是题目有一个corner case需要考虑：最左的元素不能是 left， 因此需要减去: c(2k,k) - c(2k-1, k-1) + 1. 用dfs表示的话就是 dfs(curIdx, steps, curValue): dfs(1, n/2-1, 1) + dfs(1, n/2-1, 0)

Update 一下面完了30分钟收到邮件 过了！！！啊啊啊啊啊！ 谢谢黑人大哥高抬贵手！

 请问一下DP怎么做的呀，以及在index=0的时候可以往左走吗？

我突然觉得这道题可能不需要编程？可能可以直接算出来，如果n是偶数，m=n/2,  ( \sum_{i=0}^{m-1}  (n-2i choose (n-2i)/2 ) ) + 1
如果n是奇数，m=(n-1)/2,   (\sum_{i=0}^{m-1}  (n-1-2i choose (n-1-2i)/2 ) ) + 1
求指教

dgnb88 发表于 2019-10-30 08:33
我突然觉得这道题可能不需要编程？可能可以直接算出来，如果n是偶数，m=n/2,  ( \sum_{i=0}^{m-1}  (n-2i c ...

我觉得应该可以，我当时也有往这个方向想，只要确保number of left steps = number of right steps就行，结果面试官把我打住了，把我往backtrack那里引

YuhengChang 发表于 2019-10-30 09:01
index = 0 不可以往左走
我是DP[n][currentIdx] = k 这么存的
n是还剩下多少步, currentIdx是现在在 ...

n是已经走了多少步吧 DP会减少时间？这个题指数级是跑不了的

YuhengChang 发表于 2019/10/30 09:01:57
index = 0 不可以往左走
我是DP[n][currentIdx] = k 这么存的
n是还剩下多少步, currentIdx是现在在这个array的什么位置, k是当所有可能性的个...

话说，这个应该不能叫DP吧。严格来说应该是叫记忆化搜索？