推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3967|回复: 14
收起左侧

facebook电面+onsite

[复制链接] |试试Instant~ |关注本帖
kennethinsnow 发表于 2015-10-19 01:25:57 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Facebook - 内推 - Onsite |Fail在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
phone:
3sum  上去就用sort + two pointer被烙印怀疑见过原题,要求不sort解决,用hashset解决。要求在线编译通过
. 1point3acres.com/bbs

onsite:
第一轮: 小白,上来瞎聊,问我当manager会怎么样,不明白他想问什么,估计他也不太满意。最后5分钟出了一道算法,find the shallow depth of a binary tree. the shortest distance between root and a leaf node,level traverse解决。
2.1 remove minimum number of left and right brackets and return the string with valid bracket pairs. given (a))()), should return ()(), given )()()), should return either ()() or (()). 解法很多,stack, two pointer等等都很好解,当时进了死胡同,一定要用dp解min结果没做出来,烙印也一直盘问不给任何提示。
3.1 Design tinyurl,胡扯一大通,小白估计也明白我就是纸上谈兵,没干过这类活。
4.1 design scheduler. given string “AABC” representing different task, and int k is the minimum interval for the same task, calculate the minimum steps to execute the sequence.
[size=14.6667px]AABC 2 should take A[][]ABC total of 6 steps; ABAB 2 should take AB[]AB total of 5 steps, AAAA should take 10 steps.
[size=14.6667px]很简单,不过当时已晕,被很nice的小白指出错误无数。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

fromemories1 发表于 2015-10-19 02:21:47 | 显示全部楼层
订~~~~~~~~~~~
回复 支持 反对

使用道具 举报

千骨娜娜 发表于 2015-10-19 03:38:44 | 显示全部楼层
楼主电面只有一道题嚒?
回复 支持 反对

使用道具 举报

chemsslu 发表于 2015-10-19 09:23:33 | 显示全部楼层
小白问一下不sort该怎么解决
回复 支持 反对

使用道具 举报

cu0817 发表于 2015-10-19 10:44:36 | 显示全部楼层
LZ可解释下 为啥“ABAB” k=2  需要5 step 么?
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-19 10:46:54 | 显示全部楼层
千骨娜娜 发表于 2015-10-19 03:38
楼主电面只有一道题嚒?

一道题,当时被烙印弄得有点晕,吭哧半天才写出来
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-19 10:47:34 | 显示全部楼层
chemsslu 发表于 2015-10-19 09:23
小白问一下不sort该怎么解决

hashset存前面的数,参见2sum
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-19 10:49:12 | 显示全部楼层
cu0817 发表于 2015-10-19 10:44
LZ可解释下 为啥“ABAB” k=2  需要5 step 么?

AB AB才行,中间要等一个单位的时间
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-19 11:22:12 | 显示全部楼层
bless楼长拿到offer!!第二题可以用longest valid parentheses的方法做吗?maintain 一个 stack, 最后算stack里所有indices的间隔?
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-19 12:00:44 | 显示全部楼层
nuanuan1208 发表于 2015-10-19 11:22
bless楼长拿到offer!!第二题可以用longest valid parentheses的方法做吗?maintain 一个 stack, 最后算s ...

9月面的,早就跪了. visit 1point3acres.com for more.
你那个思路是对的,不过也可以直接碰到不合法的就扔掉,比如没有左括号对应的右括号,和最后多出来的左括号,记住左右括号数就可以。
更直观的也可以是两头各扫一遍,左边扫去掉非法的右括号,右边扫去掉非法的左括号。
回复 支持 反对

使用道具 举报

cu0817 发表于 2015-10-19 21:03:37 | 显示全部楼层
kennethinsnow 发表于 2015-10-19 12:00
9月面的,早就跪了
你那个思路是对的,不过也可以直接碰到不合法的就扔掉,比如没有左括号对应 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
LZ 的想法是用一个变数A记住当前不合法的数量 (eg 不合法就是先遇到左括号) 另外用一个变数B记录右括号,遇到右括号B+1,如果B=0时,遇到左括号A+1?
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-20 04:29:06 | 显示全部楼层
第二题感觉类似CPU里的指令运行dependency问题。
用一个map来记录上次遇到每种指令是在哪个index。如果遇到一个指令,发现上次遇到相同指令是在距离K以内,那么就要等待够K那么久,再继续执行下面的指令。

补充内容 (2015-10-20 04:33):
应该是onsite第四题
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-20 04:32:40 | 显示全部楼层
第一题,如果是sort + 2pointer的话,复杂度应该是O(n^2)。如果是hashset的话(我不太懂Java,我是C++),就是先把每个元素都放set里,然后二重循环,每次取两个数a和b,看能使得三个数和为0的第三个数c是否在set里面 (a+b+c==0)。
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-20 12:33:52 | 显示全部楼层
cu0817 发表于 2015-10-19 21:03
LZ 的想法是用一个变数A记住当前不合法的数量 (eg 不合法就是先遇到左括号) 另外用一个变数B记录右括号, ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这题这里有详细讨论

http://www.mitbbs.com/article_t/JobHunting/33049009.html
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-20 12:36:35 | 显示全部楼层
gamespeed 发表于 2015-10-20 04:32
第一题,如果是sort + 2pointer的话,复杂度应该是O(n^2)。如果是hashset的话(我不太懂Java,我是C++), ...

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴hashset复杂度一样不过需要额外空间,其实不好
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-24 11:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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