Facebook Intern phone interview

十二月临近final的时候意外收到facebook的电话面试，忙着考试也没好好准备。觉得浪费了很好的机会，还要好好刷题，facebook的题目还是很基础的
我面试题目如下，希望大家好好准备
1. stair climbing， print out all of pos

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

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

）;

题目都是不难的，可以有头绪，也能写出来完整的code，但是第二题想了一会儿，写完有一些bug，所以最后应该是挂在这个原因了。有些遗憾。

MCwong 发表于 2015-1-19 03:59
同问: 第一题follow up 如何用stack省空间的?

第二题应该省空间的话感觉可以直接枚举所有方案吧？一个循环决定走几个2步走几个1步，然后再generate combination……

补充内容 (2015-1-19 04:36):
generate n-choose-k combination的时候直接枚举所有的n-bit binary number然后把有k个1的挑出来，这样的话space是O(1)的。当然这样做time complexity会很大，但是他第二问只要求你降低space complexity。

补充内容 (2015-1-19 04:37):
你把recursion用stack给explicitly写出来，空间复杂度是不变的。

rhett.lhy 发表于 2015-1-19 04:25
第一题要求打印所有方案，应该不是constant space的，应该是O(2^n)吧；第三题是constant space

补充内容 ...

请问为什么是O(2^n)的space呢，谢谢！

husscc 发表于 2015-1-17 12:06
第一题constant space

第一题要求打印所有方案，应该不是constant space的，应该是O(2^n)吧；第三题是constant space

补充内容 (2015-1-19 04:27):
貌似我说错了，O(2^n)是用DP做第一题的space complexity; 用recursion的话应该就是O(n)的space吧

第二问，save space， 为啥用stack，这个跟recursion 不是一样吗

第一题constant space

如何constant？

houqingniao 发表于 2015-1-18 23:23
如何constant？

可以用DP，只记录最近2次的solution，要需要n^2的space

同问: 第一题follow up 如何用stack省空间的?

DP 打印所以solutions？应该用DFS吧。

用循环写这个make sense