找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3909|回复: 11
收起左侧

[Facebook] Facebook Intern面经

[复制链接]

5

主题

4

精华

118

积分

资深会员

Rank: 2

积分
118
发表于 11-9-2016 09:41 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 11-13-2016 03:31 PM 编辑
$ a- A1 F: l* [6 J9 d& Q" M/ v' {' B- I
一开始是基本的behavior question, why facebook. 问下项目。& g2 k" r. ]+ h
然后做了一道题,是对比两棵树的叶子节点,按照从左往右的顺序,逐个对比。输出第一对不同的node.. M. a# ~2 N5 g2 S( p
比如,下面两棵就该输出(C, D)0 o0 Y4 i/ W$ R) c. ?
    A
) U' r$ P- x9 u& C5 b$ Z7 N6 M    /\
) J# g+ q" X2 M$ q1 I( s" e  B   C
2 M. m0 S' K8 V% f  o
, v/ E$ J$ ~  k) _    A4 y" j9 k  A5 i7 z
    /\$ x) O% s1 R( C; p
  B   D
! W/ Q$ B) y" ^3 |/ S& D) A& u- j. w: L, o2 }6 l% Y* Q
我是用DFS把两个树的leaf node按照要求放进list里。然后对比。
) S+ J- {: ?# T, I6 ~. y7 m! v( o# [" k. Y3 W
Follow up 是优化空间复杂度。我用了Iterator。 他告诉我的方法是可以用parent pointer,这个我没明白,求指点。
9 x- ?- L% i; S5 V' r5 z9 e- o6 b8 I& ]( O/ k. [" }% n

9 ^# c) B; I* i# a/ c0 S补充内容 (12-17-2016 12:32 PM):
1 S: O0 v2 W  w! @5 |( iParent pointer的方法想到了。找到一个关键的parent, 只要找出从当前leaf往上的parent中,第一个走向左孩子的那个node,就是关键node.
1 w2 c% j% f2 G) C% D+ `. s关键node的右子树的最小孩子就是下一个。

评分

参与人数 1金钱 +2 收起 理由
Sophia + 2 感谢您的面经分享!大米送上!

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 11-9-2016 09:41 PM 来自美国米群网手机版 | 显示全部楼层
给您点个赞~~~

0

主题

0

精华

3

积分

新米人

Rank: 1

积分
3
发表于 11-12-2016 08:55 AM | 显示全部楼层
感谢pls331分享~~~好人一生平安~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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