一亩三分地论坛

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

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

FB 电面 很简单但是做的有bug。

[复制链接] |试试Instant~ |关注本帖
ZhiDong 发表于 2015-5-25 11:12:50 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Facebook - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
4月底面试的。 很简单 寒暄过后就来了一道 LC 的 subset, follow up subset II, 不用存结果,只要print out 即可. code 很简单,但是出了一点小错。 问了复杂度。复杂度这个比较蛋疼, subset 空间复杂度,如果用递归做 我回答的是O(n*n) 因为call stack 的深度为 n 然后我中间存了一个中间结果String 所以是n *n。 然后时间复杂度回答的是 (2^n * n) ,2^n 是结果数量 乘以n是因为 输出的时候每个字符遍历,所以乘以n。 然后又问subset II 复杂度多少? 我回答 O(pow(2,n)* n ).  FB面试官不满意,让更准确一点, 然后还给出每个字符出现的频率, 比如 aaaa bbb 那么 a出现 4次 b出现3次, 复杂度是多少? 脑子反抽,回答了一个 a的频率 乘以 b 的频率, 面试官举个例子说不对, 然后我就在推导,快到时间的时候面试官说 其实是 (ck + 1) *(ck-1 +1)*...(c0+1) ck 为每个字符的频率, 我一想对啊,组成的subset不就是从 每个字符里面抽取 0 - ck 个字符出来么。。 然后时间没到40分钟 面试官就让结束了。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

因为复杂度回答的很糟糕, 肯定跪了。不过还是让onsite了,求bless。


  

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
yuxrose 发表于 2015-5-25 13:17:23 | 显示全部楼层
这个复杂度好tricky, bless!
回复 支持 反对

使用道具 举报

达达主义 发表于 2015-5-26 07:05:07 | 显示全部楼层
请问是new grad吗
回复 支持 反对

使用道具 举报

 楼主| ZhiDong 发表于 2015-5-26 07:46:04 | 显示全部楼层
达达主义 发表于 2015-5-26 07:05-google 1point3acres
请问是new grad吗
. 1point3acres.com/bbs
不是 有些工作经验了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-5-27 22:56:46 | 显示全部楼层
subset的输入不是int[] num吗,怎么会有字符
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-8-21 21:31:54 | 显示全部楼层
楼主请问下 为什么是2^n? 不是分支数为n 深度为n 应该是n^n 么 subset 谢谢
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2015-8-21 21:49):
明白了。。。请忽略我
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-9-23 14:34:26 | 显示全部楼层
复杂度考的这么仔细,得好好看看了...
回复 支持 反对

使用道具 举报

allen6432 发表于 2015-9-25 01:54:17 | 显示全部楼层
我感觉反向字符出现次数分析不太对,如果是subset1, 那么每个字符出现次数应该是2^(n-1).如果是subset2,假设这个string有k1个a,k2个b,k3个c.a的出现次数是:(k1+1)*(k2+1)*(k3+1)/2
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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