一亩三分地论坛

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

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

Facebook Intern phone interview

[复制链接] |试试Instant~ |关注本帖
dabao 发表于 2015-1-17 09:18:56 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 实习@Facebook - 网上海投 - 技术电面 |Fail

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

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

x
十二月临近final的时候意外收到facebook的电话面试,忙着考试也没好好准备。觉得浪费了很好的机会,还要好好刷题,facebook的题目还是很基础的
我面试题目如下,希望大家好好准备. From 1point 3acres bbs
1. stair climbing, print out all of possible solutions of the methods to climb a stars, you are allowed climb one or two steps for each time; what is time/space complexity? (use recursion)
2. follow up: could you change the algorithm to save space?  -> I use stack
3. the total number of different ways to climb stairs; (这个事leetcode原题,fib数列);

题目都是不难的,可以有头绪,也能写出来完整的code,但是第二题想了一会儿,写完有一些bug,所以最后应该是挂在这个原因了。有些遗憾。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

3

查看全部评分

houqingniao 发表于 2015-1-17 11:53:34 | 显示全部楼层
第二问,save space, 为啥用stack,这个跟recursion 不是一样吗
回复 支持 反对

使用道具 举报

husscc 发表于 2015-1-17 12:06:39 | 显示全部楼层
第一题constant space
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-1-18 23:23:52 来自手机 | 显示全部楼层
如何constant?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-1-18 23:34:43 | 显示全部楼层

可以用DP,只记录最近2次的solution,要需要n^2的space
回复 支持 反对

使用道具 举报

MCwong 发表于 2015-1-19 03:59:30 | 显示全部楼层
同问: 第一题follow up 如何用stack省空间的?
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-1-19 04:25:23 | 显示全部楼层
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吧
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-1-19 04:31:51 | 显示全部楼层
MCwong 发表于 2015-1-19 03:59
同问: 第一题follow up 如何用stack省空间的?
. From 1point 3acres bbs
第二题应该省空间的话感觉可以直接枚举所有方案吧?一个循环决定走几个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写出来,空间复杂度是不变的。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-1-19 10:50:25 | 显示全部楼层
DP 打印所以solutions?应该用DFS吧。

用循环写这个make sense
回复 支持 反对

使用道具 举报

yolkfive 发表于 2015-1-22 04:08:57 | 显示全部楼层
rhett.lhy 发表于 2015-1-19 04:25
第一题要求打印所有方案,应该不是constant space的,应该是O(2^n)吧;第三题是constant space
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问为什么是O(2^n)的space呢,谢谢!
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-1-22 05:13:06 | 显示全部楼层
第一题应该是O(n)吧?
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-1-22 05:44:25 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 08:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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