美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 刘烨过39岁生日感慨:不敢再装三十几岁的男孩子
  • 操心太多?被传赴美陪产的陈冠希怎么这么显老
  • 徐静蕾公开与男友相处细节:他做事比我果断
  • 影版《奶酪陷阱》又有新人加入 朴山多拉演女主好友
  • 亮点太多!赵薇怀抱"小沈阳" 身后的苏有朋亮了
  • 杨坤恋情曝光!揭秘他至今不婚不育的隐情
  • 小沈阳搂张柏芝合唱 手放在这个部位有点尴尬
  • 余文乐自认说错话:不是被逼承认恋情 想保护对方
  • 罗晋绯闻女友苗圃复出 嫁大21岁富商变豪门阔太
  • 回归家庭做奶爸 陈思诚逛婴幼儿店认真挑玩具
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3019|回复: 9

    内推面经 -说一道关于unbalanced树的面试题 (转载)- 唐人社区|北美华人论坛

    [复制链接]

    14

    主题

    379

    帖子

    404

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    404
    QQ
    发表于 2016-11-4 21:14:01 | 显示全部楼层 |阅读模式
    分享到:
    {$content}

    唐人社区-北美华人论坛-内推面经版-说一道关于unbalanced树的面试题 (转载)


      JobHunting
    标 题: 说一道关于unbalanced树的面试题 (转载)



    Programming
    标 题: 说一道关于unbalanced树的面试题


    前两天面试一个公司,题目是用bfs在tree上找string,但是unbalanced tree.

    可能有点先入为主的概念,我开始“默认”这是一个unbalanced binary search tree
    ,写代码到一半的时候,面试的人一再强调unbalanced tree,我当时也被他弄懵了。
    写到最后,他说这是一个unsorted tree,我恍然大悟,原来开始他说的unbalanced
    tree就是unsorted 的意思,我k,这能是同一个概念吗

    我改代码完了之后,他又继续说:这tree里可能有cycle,也就是两个parent nodes可
    能会共享一个儿子或孙子node,我k,真是烦。一个tree弄的这么复杂,面试的人真是
    有点变态。不过话说回来也怪我一开始没跟他问清楚!最后面试完了想骂人

    --


    【返利网站】返利额度最高的海外购物返利网站Topcashback:平均返利7~10%,注册就送$10点我注册
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    22

    主题

    91

    帖子

    132

    积分

    注册会员

    Rank: 2

    积分
    132
    QQ
    发表于 2016-11-4 22:44:11 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    tree上用bfs不需要额外空间存visited
    但是增加visited也就是一点点code的事儿吧?

    【 在 Wardo (餐厅忙的时候客户端,否则服务端) 的大作中提到: 】
    : 根据我后来的感觉,面试我的这个人主要是想让我用一个额外的空间数组来track
    : visited
    : nodes,这样就会避免cycle的问题。可是,在树上用bfs的时候谁用的着额外的空间数
    : 组来track visited node啊?因为tree根本就不应该有cycle的。
    : 所以,那个面试从一开始他说unbalanced,我就开始犯晕。用bfs还管是否
    unbalanced?
    : 面试最后他说这是一个unsorted tree,我不得不把判断left/right的那几行去掉,反
    : 正就是统统遍历一次好了。
    : 总之奇葩的面试: unsorted 说成unbalanced;tree里还有tmd cycle



    --

    11

    主题

    247

    帖子

    272

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    272
    QQ
    发表于 2016-11-4 23:40:11 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    根据我后来的感觉,面试我的这个人主要是想让我用一个额外的空间数组来track
    visited
    nodes,这样就会避免cycle的问题。可是,在树上用bfs的时候谁用的着额外的空间数
    组来track visited node啊?因为tree根本就不应该有cycle的。

    所以,那个面试从一开始他说unbalanced,我就开始犯晕。用bfs还管是否unbalanced?

    面试最后他说这是一个unsorted tree,我不得不把判断left/right的那几行去掉,反
    正就是统统遍历一次好了。

    总之奇葩的面试: unsorted 说成unbalanced;tree里还有tmd cycle


    【 在 coldknight (冷骑士) 的大作中提到: 】
    : 有cycle还能叫tree吗? 应该骂他。求问一下, bfs或dfs对于unbalanced tree 与
    : balanced tree有什么不一样吗?
    : tree




    --

    24

    主题

    86

    帖子

    143

    积分

    注册会员

    Rank: 2

    积分
    143
    QQ
    发表于 2016-11-4 23:53:17 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    unbalanced tree也没有默认sorted啊..
    这个他本来可能想考你communication吧,因为面试一上来不应该先把各种犄角旮旯的
    trick问清楚吗..sort与否是最基本的之一了吧
    --

    21

    主题

    90

    帖子

    138

    积分

    注册会员

    Rank: 2

    积分
    138
    QQ
    发表于 2016-11-4 23:57:40 | 显示全部楼层
    JobHunting
    标  题: 说一道关于unbalanced树的面试题 (转载)



    Programming
    标  题: 说一道关于unbalanced树的面试题


    前两天面试一个公司,题目是用bfs在tree上找string,但是unbalanced tree.

    可能有点先入为主的概念,我开始“默认”这是一个unbalanced binary search tree
    ,写代码到一半的时候,面试的人一再强调unbalanced tree,我当时也被他弄懵了。
    写到最后,他说这是一个unsorted tree,我恍然大悟,原来开始他说的unbalanced
    tree就是unsorted 的意思,我k,这能是同一个概念吗

    我改代码完了之后,他又继续说:这tree里可能有cycle,也就是两个parent nodes可
    能会共享一个儿子或孙子node,我k,真是烦。一个tree弄的这么复杂,面试的人真是
    有点变态。不过话说回来也怪我一开始没跟他问清楚!最后面试完了想骂人

    --

    29

    主题

    103

    帖子

    164

    积分

    注册会员

    Rank: 2

    积分
    164
    QQ
    发表于 2016-11-5 00:18:17 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    bfs 和 dfs 输出的顺序不一样吧。 unbalanced tree 就是注意一下 缺一个或两个孩
    子的情况吧

    【 在 coldknight (冷骑士) 的大作中提到: 】
    : 有cycle还能叫tree吗? 应该骂他。求问一下, bfs或dfs对于unbalanced tree 与
    : balanced tree有什么不一样吗?
    : tree



    --

    27

    主题

    99

    帖子

    151

    积分

    注册会员

    Rank: 2

    积分
    151
    QQ
    发表于 2016-11-5 00:19:36 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    有cycle 不是叫图吗?



    --

    30

    主题

    102

    帖子

    173

    积分

    注册会员

    Rank: 2

    积分
    173
    QQ
    发表于 2016-11-5 00:31:34 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    有cycle还能叫tree吗? 应该骂他。求问一下, bfs或dfs对于unbalanced tree 与
    balanced tree有什么不一样吗?

    【 在 Wardo (餐厅忙的时候客户端,否则服务端) 的大作中提到: 】
    :  Programming
    : 标  题: 说一道关于unbalanced树的面试题
    :
    : 前两天面试一个公司,题目是用bfs在tree上找string,但是unbalanced tree.
    : 可能有点先入为主的概念,我开始“默认”这是一个unbalanced binary search
    tree
    : ,写代码到一半的时候,面试的人一再强调unbalanced tree,我当时也被他弄懵了。
    : 写到最后,他说这是一个unsorted tree,我恍然大悟,原来开始他说的unbalanced
    : tree就是unsorted 的意思,我k,这能是同一个概念吗
    : 我改代码完了之后,他又继续说:这tree里可能有cycle,也就是两个parent nodes可
    : 能会共享一个儿子或孙子node,我k,真是烦。一个tree弄的这么复杂,面试的人真是
    : ...................



    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    23

    主题

    98

    帖子

    136

    积分

    注册会员

    Rank: 2

    积分
    136
    QQ
    发表于 2016-11-5 00:44:54 | 显示全部楼层
    JobHunting
    标  题: Re: 说一道关于unbalanced树的面试题 (转载)


    碰到这样的,真是倒霉。感觉面试70%靠运气,30%靠实力。不过以后先clarify所有问
    题再开始解决会比较好。

    我的意思是我做bfs 或dfs travel的时候, 从来没考虑tree是不是balanced呀,
    unbalanced缺孩子,要做哪些判断?能给个三行codes讲一下吗?多谢!

    【 在 Wardo (餐厅忙的时候客户端,否则服务端) 的大作中提到: 】
    : bfs 和 dfs 输出的顺序不一样吧。 unbalanced tree 就是注意一下 缺一个或两个孩
    : 子的情况吧


    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    15

    主题

    1177

    帖子

    2323

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    2323
    QQ
    发表于 2016-11-28 17:06:23 | 显示全部楼层
    锄禾日当午,发帖真辛苦。谁知坛中餐,帖帖皆辛苦!
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -说一道关于unbalanced树的面试题 (转载)- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -说一道关于unbalanced树的面试题 (转载)- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

    Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

    本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

    安全联盟认证 安全联盟认证

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