找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Facebook] Facebook Intern面经

[复制链接]

5

主题

4

精华

118

积分

资深会员

Rank: 2

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

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

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

x
本帖最后由 Sophia 于 11-13-2016 03:31 PM 编辑
) o4 f! [( r( R
0 N# i4 J! i$ \! W: l/ C2 ]) v一开始是基本的behavior question, why facebook. 问下项目。$ l# t' U, _/ E0 ~+ o# J" F
然后做了一道题,是对比两棵树的叶子节点,按照从左往右的顺序,逐个对比。输出第一对不同的node.5 Z- p# J; u) `6 V$ P2 X* S
比如,下面两棵就该输出(C, D)
, l: H6 n6 r* w" h    A
. b8 b) C8 E" d9 k    /\
5 Y3 ?$ k) w# C4 P  B   C
' `. t! I  ~8 f& g" E& t+ E( V4 X8 a+ u2 d# o) l
    A
7 J  a5 C: H! V1 @& Z3 c8 B- b    /\; ]( p" ?3 G7 L9 Z  M7 l' @
  B   D
- ^/ f  o! Y5 H. J- n9 T: W# k8 R( R% z" F# g+ Y
我是用DFS把两个树的leaf node按照要求放进list里。然后对比。
& T0 c+ c/ v3 n9 `4 j: y1 t5 _# ~" N
Follow up 是优化空间复杂度。我用了Iterator。 他告诉我的方法是可以用parent pointer,这个我没明白,求指点。
0 q! T" }, s( C
5 F- S3 ~: B7 \: [* \6 O: b+ I: m
/ Y7 W1 n  s% ~6 z% H7 p! z补充内容 (12-17-2016 12:32 PM):
- o7 C" t' s+ t1 [8 G  u- O  YParent pointer的方法想到了。找到一个关键的parent, 只要找出从当前leaf往上的parent中,第一个走向左孩子的那个node,就是关键node.- ]( f  @0 {6 v. ~* |& R9 f; B
关键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分享~~~好人一生平安~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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