一亩三分地论坛

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

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

Facebook On Campus面经一枚

[复制链接] |试试Instant~ |关注本帖
herz 发表于 2014-11-7 13:32:50 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Facebook - 内推 - 校园招聘会 |Pass

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

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

x
本来昨天该面的谁知道被告知安排错了,可能攒了不少人品,下午面完,小哥高兴地跟我说我已经直接推荐你去On site了,HR跟你说的时候记住装得很惊喜喔!开心!

题目只有一道,但是一直在follow up,一开始让我写出打印一棵树的根节点到叶节点的所有路径,为方便后面follow up的叙述,我举个例子:
    A
  B   C
D    E  F

打印ABD, ACE, ACF就OK了,仔细点写没问题。
然后分析下空间复杂度时间复杂度,开始follow up。.鐣欏璁哄潧-涓浜-涓夊垎鍦

现在不仅要打印路径,还要把树的形状打印出来,例如
ABD要打印成
(空格)(空格)A
(空格)B
D
ACE要打印成. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
A
(空格)C
E
.鐣欏璁哄潧-涓浜-涓夊垎鍦
如此类推。稍微想了想我说在DFS的时候多加一个vector,记录当前缩进深度,以根节点A为0作参考,左节点减1右结点加1,于是
. Waral 鍗氬鏈夋洿澶氭枃绔,ABD 有深度vector [0, -1, -2]. 鍥磋鎴戜滑@1point 3 acres
ACE 有深度vector [0, 1, 0]
然后打印的时候找出当前vector最小值,如果小于0,所有值都加上这个偏移量来打印就可以了。
当然还有继续分析时间空间复杂度= =.1point3acres缃

接下来是parallel follow up,问我现在有很多部机器可以帮我同时处理,这么把这个task分给这么多机器。
我说如果碰到一个节点,如果有两个子节点,当前机器就继续处理左节点,多分配一个新的到右节点。

然后是parallel完,这么collect每个机器的数据回来,并且保持顺序(例如ABD在ACE前面,ACE在ACF前面),
我就说可以用bitmap来存,当前层数就是第几个0或1,左节点就是0右节点就是1,例如例子里的ABD就是000,ACE就是010,然后就有顺序了。. from: 1point3acres.com/bbs
他表示这个方法work,但是其实更简单的方法是利用之前得到的深度vector,里面的最小值就是顺序,例如ABD vector最小值是-2,肯定就是最左边的路径了。.1point3acres缃
. from: 1point3acres.com/bbs
最后问5分钟问题就走了,好嗨森愉悦!虽然不是说好的leetcode原题。。继续求各种onsite人品!!

评分

3

查看全部评分

22691482 发表于 2014-11-7 13:51:30 | 显示全部楼层
明天电面F,,最后几个面试了
回复 支持 反对

使用道具 举报

22691482 发表于 2014-11-7 14:17:28 | 显示全部楼层
最后那个follow up,面试官的方法有点问题。。

比如:
           A
       B      C
    D       E   F

ACE, ACF 最小深度都是0,根据最小深度没法区分啊。。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-11-7 15:41:02 | 显示全部楼层
原来是UCLA的学长!!~~学长是哪位?
回复 支持 反对

使用道具 举报

 楼主| herz 发表于 2014-11-7 16:16:02 | 显示全部楼层
22691482 发表于 2014-11-7 14:17
最后那个follow up,面试官的方法有点问题。。

比如:

那可以根据vector的和来做
回复 支持 反对

使用道具 举报

danchou 发表于 2014-11-9 03:39:17 | 显示全部楼层
很好!很具体很详细
回复 支持 反对

使用道具 举报

kongweihan 发表于 2014-11-24 08:06:52 | 显示全部楼层
herz 发表于 2014-11-7 16:16.鐣欏璁哄潧-涓浜-涓夊垎鍦
那可以根据vector的和来做

如果是这种情况呢?
  1.                   A
  2.                  /  \. From 1point 3acres bbs
  3.                 B   C
  4.                     /
  5.                   D
  6.                  /
  7.                 E
  8.                /. 鍥磋鎴戜滑@1point 3 acres
  9.               F
复制代码
可能楼主的意思是根据深度vector的字典顺序吧
感谢楼主分享面经!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 18:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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