一亩三分地论坛

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

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

Facebook 新鲜面经

[复制链接] |试试Instant~ |关注本帖
youling_tong 发表于 2015-1-21 04:24:53 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 猎头 - 技术电面 |Other

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

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

x
面试官是个美国人,和我介绍了一下他自己,然后问了我现在的情况。和我说面coding大概35分钟,然后最后再留一点时间给我问问题。. From 1point 3acres bbs
囧的是只面了一道题。
Leetcode 原题: Letter Combinations of a Phone number,有修改的是,只需要Print out,不需要返回List<String>

写完之后,我很主动的拿了一个例子验算,证明我的正确性。接着面试官问我时间复杂度。
我说if a = digits.length(), b = MAX(number of characters mapping to a digit), 我说错了,第一次说的是a*b, 过了一会儿在hint之下纠正回来是pow(b,a)

面试官还不罢休,然后问我System.out.println()的时间复杂度... 我就被问蒙圈了... 不是还是pow(b,a)么... 他就写了个
  1. <div>System.out.print(String s){</div><div>     for(char c in s){</div><div>         printChar(c);</div><div>     }</div><div>}</div>
复制代码
可能是为了说明我不要用List... 直接print?

最后问了下问题,我问了Facebook bootcamp, 和Android team的情况,他还挺健谈 说了很多..
感觉只面了一题,实在是很虚。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

ysong1pt3ac 发表于 2015-1-21 04:44:40 | 显示全部楼层
不明白什么叫system.out.println()的时间复杂度.. visit 1point3acres.com for more.
一般来高按他给的那个循环,如果 n 是字符串的长度. 那就是O(n)
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴可是在这道题目里,每个号码是定长的,时间是O(1)不是吗.
回复 支持 反对

使用道具 举报

 楼主| youling_tong 发表于 2015-1-21 04:50:33 | 显示全部楼层
ysong1pt3ac 发表于 2015-1-21 04:44
不明白什么叫system.out.println()的时间复杂度.
一般来高按他给的那个循环,如果 n 是字符串的长度. 那就 ...

反正最后我说的是pow(b,a)*b..

就是printChar()最后会被调用这么多次..

特别纠结
回复 支持 反对

使用道具 举报

ysong1pt3ac 发表于 2015-1-21 05:52:24 | 显示全部楼层
youling_tong 发表于 2015-1-21 04:50
反正最后我说的是pow(b,a)*b..

就是printChar()最后会被调用这么多次..

应该是对的
这里b是常数,a是变量.鐣欏璁哄潧-涓浜-涓夊垎鍦
整个复杂度也就是 指数级的O(b^a)
回复 支持 反对

使用道具 举报

dtcxzch 发表于 2015-1-23 08:59:09 | 显示全部楼层
youling_tong 发表于 2015-1-20 15:50
反正最后我说的是pow(b,a)*b..

就是printChar()最后会被调用这么多次..

为什么不是pow(b,a) * a. 最后要print的时候List或者stringbuilder或char[]里是只有a个字符啊
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-1-24 10:46:20 | 显示全部楼层
我也感觉是pow(b,a) * a也?
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-2 07:24:01 | 显示全部楼层
感觉面试官并不是真的想考输出函数的时间复杂度,而是想提醒一下在递归函数中进行 I/O 操作是个非常不好的。

在时间复杂度较高或者会被反复调用的函数中进行 I/O 操作会降低函数的性能,因为输出函数本身就是性能较低的。
回复 支持 反对

使用道具 举报

 楼主| youling_tong 发表于 2015-4-21 13:02:09 | 显示全部楼层
干.什么 发表于 2015-4-2 07:24
感觉面试官并不是真的想考输出函数的时间复杂度,而是想提醒一下在递归函数中进行 I/O 操作是个非常不好的 ...

有道理 受教了
回复 支持 反对

使用道具 举报

yanguango 发表于 2015-4-30 08:07:57 | 显示全部楼层
那这个问题是不是把所有组合放在数组中,最后再一起打印出来比较妥呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 04:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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