一亩三分地论坛

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

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

Facebook 第一轮电面,三道题。

[复制链接] |试试Instant~ |关注本帖
CeciliaM 发表于 2016-9-2 06:13:00 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
早听说Facebook面试水原来是真的。大叔超nice,上来先介绍了自己的组,然后问了为啥想在FB工作,我一通捧他,然后三道leetcode原题……

1. Copy a string and remove duplicates-google 1point3acres
Input: "kkbkbw"
Output: "kbw"

被问到 string+=操作复杂度的时候,口胡amortized O(1) 并成功忽悠住了对方。
面试完了去翻文档被打脸……是O(n),希望大叔不要去查证(哭泣)
. visit 1point3acres.com for more.
2. Group anagram. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
原题,输入一个string里表,按照anagram分组
Input: ["arts", "star", "cat"]
Output: [ ["arts", "star"], ["cat"] ].鏈枃鍘熷垱鑷1point3acres璁哄潧

3. Valid BST
也是原题,判断一个二叉树是不是BST。写的bottom-up O(n). From 1point 3acres bbs

大叔是写IOS的,似乎C++不熟,问的极其细致,要求解释每一个API,说明每一行代码每一个操作的复杂度_(・ω・」 ∠)_


顺便求明天狗家onsite人品_(・ω・」 ∠)_
.1point3acres缃

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| CeciliaM 发表于 2016-9-2 07:51:24 | 显示全部楼层
iPhD 发表于 2016-9-2 07:40
3. Valid BST
"写的bottom-up O(n)". more info on 1point3acres.com
这是什么解法?

……我忽然想起来只要inorder遍历一遍就行了啊!我在干什么啊!!!
_(・ω・」 ∠)_

感觉人生远去了……
回复 支持 1 反对 0

使用道具 举报

gaocan1992 发表于 2016-9-2 06:31:21 | 显示全部楼层
好奇楼主是怎么拿到面试的,能私聊吗
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 06:56:52 | 显示全部楼层
gaocan1992 发表于 2016-9-2 06:31
好奇楼主是怎么拿到面试的,能私聊吗

网投直接就电面了-google 1point3acres
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-9-2 07:31:18 | 显示全部楼层
第一题需要remove以后的string最小吗?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 07:40:17 | 显示全部楼层
3. Valid BST
"写的bottom-up O(n)"
这是什么解法?
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 07:40:36 | 显示全部楼层
sniffsky 发表于 2016-9-2 07:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题需要remove以后的string最小吗?

是把所有duplicate的都去掉,比如如果有很多个k的话,只留下第一个。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
维持其它字母的顺序不变。
所以remove之后的结果是唯一的啊……
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-2 07:41:31 | 显示全部楼层
CeciliaM 发表于 2016-9-1 14:56
网投直接就电面了
. from: 1point3acres.com/bbs
楼主你网投的什么职位啊,可以透露下么。plus楼主简历应该很牛
回复 支持 反对

使用道具 举报

keepworkinghard 发表于 2016-9-2 07:48:25 | 显示全部楼层
您是什么时候毕业啊?年底么?
祝onsite offer
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 07:52:28 | 显示全部楼层
gaocan1992 发表于 2016-9-2 07:41
楼主你网投的什么职位啊,可以透露下么。plus楼主简历应该很牛

new grad 不要求phd的唯一的那个……
看着海量的new grad phd的岗,MS哭晕在厕所
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 07:58:20 | 显示全部楼层
keepworkinghard 发表于 2016-9-2 07:48
您是什么时候毕业啊?年底么?. more info on 1point3acres.com
祝onsite offer

. visit 1point3acres.com for more.感谢!.鐣欏璁哄潧-涓浜-涓夊垎鍦
是明年五月

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 08:02:37 | 显示全部楼层
CeciliaM 发表于 2016-9-2 07:51
……我忽然想起来只要inorder遍历一遍就行了啊!我在干什么啊!!!
_(・ω・」 ∠)_ ...

对,应该2种方法,一个左右最大最小值递归,另一种inorder递归。。。都是时间O(n), in-place....
回复 支持 反对

使用道具 举报

keepworkinghard 发表于 2016-9-2 08:06:44 | 显示全部楼层
CeciliaM 发表于 2016-9-2 07:58
感谢!
是明年五月

现在google全职,要先做oa么?
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 08:10:05 | 显示全部楼层
iPhD 发表于 2016-9-2 08:02
对,应该2种方法,一个左右最大最小值递归,另一种inorder递归。。。都是时间O(n), in-place....

递归的话有函数栈,感觉应该都算 Space O(h) ?
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 08:10:26 | 显示全部楼层
keepworkinghard 发表于 2016-9-2 08:06
现在google全职,要先做oa么?

我做了OA,内推是直接MTV onsite
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 08:13:03 | 显示全部楼层
CeciliaM 发表于 2016-9-2 08:10
递归的话有函数栈,感觉应该都算 Space O(h) ?

对,递归都是O(h), h是树的高度,如果平衡的话就是logn..鏈枃鍘熷垱鑷1point3acres璁哄潧
in-place的数学定义是复杂度小于等于logn,不是非要常数才叫in-place.
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-2 08:16:43 | 显示全部楼层
iPhD 发表于 2016-9-2 08:13
对,递归都是O(h), h是树的高度,如果平衡的话就是logn.
in-place的数学定义是复杂度小于等于logn,不是 ...
. from: 1point3acres.com/bbs
受教!大感谢!
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-5 04:09:05 | 显示全部楼层
CeciliaM 发表于 2016-9-2 07:40
是把所有duplicate的都去掉,比如如果有很多个k的话,只留下第一个。
维持其它字母的顺序不变。-google 1point3acres
所以re ...

完全不像原题啊。原题316 不是个Hard space O(1) 还得按字母顺序么。. 鍥磋鎴戜滑@1point 3 acres
Remove all duplicates from a given string. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感觉是这个
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-5 04:47:43 | 显示全部楼层
c++里string后面append东西的复杂度挺复杂的,跟具体怎么用有关。
http://stackoverflow.com/questio ... append-vs-push-back. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
觉得你答O(1)也许不能算错...
回复 支持 反对

使用道具 举报

smellycat 发表于 2016-9-5 06:55:28 | 显示全部楼层
cicean 发表于 2016-9-5 04:09
完全不像原题啊。原题316 不是个Hard space O(1) 还得按字母顺序么。
Remove all duplicates from a g ...

完全没读懂316是个什么意思……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 07:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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