传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2384|回复: 6
收起左侧

Facebook On Campus面经一枚

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

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

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

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

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

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

打印ABD, ACE, ACF就OK了,仔细点写没问题。
然后分析下空间复杂度时间复杂度,开始follow up。

现在不仅要打印路径,还要把树的形状打印出来,例如
ABD要打印成
(空格)(空格)A
(空格)B
D
ACE要打印成
A
(空格)C
E. From 1point 3acres bbs

如此类推。稍微想了想我说在DFS的时候多加一个vector,记录当前缩进深度,以根节点A为0作参考,左节点减1右结点加1,于是
ABD 有深度vector [0, -1, -2]
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,然后就有顺序了。
他表示这个方法work,但是其实更简单的方法是利用之前得到的深度vector,里面的最小值就是顺序,例如ABD vector最小值是-2,肯定就是最左边的路径了。

最后问5分钟问题就走了,好嗨森愉悦!虽然不是说好的leetcode原题。。继续求各种onsite人品!!

评分

3

查看全部评分

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

使用道具 举报

22691482 发表于 2014-11-7 14:17:28 | 显示全部楼层
最后那个follow up,面试官的方法有点问题。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

比如:
           A
       B      C-google 1point3acres
    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,面试官的方法有点问题。。. Waral 鍗氬鏈夋洿澶氭枃绔,

比如:

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

使用道具 举报

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

使用道具 举报

kongweihan 发表于 2014-11-24 08:06:52 | 显示全部楼层
herz 发表于 2014-11-7 16:16. from: 1point3acres.com/bbs
那可以根据vector的和来做

如果是这种情况呢?
  1.                   A
  2.                  /  \
  3.                 B   C
  4.                     / .鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.                   D
  6.                  /. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.                 E. From 1point 3acres bbs
  8.                /
  9.               F
复制代码
可能楼主的意思是根据深度vector的字典顺序吧 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感谢楼主分享面经!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 17:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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