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

 找回密码
 立即注册
  • 李英爱新剧《师任堂》接档《蓝海传说》 26日首播
  • 48岁许晴与友人庆生 素颜出镜似18岁少女
  • 林允牙齿大变样 网友惊呼认不出
  • 姚晨三亚度假摘芒果 偶遇儿时同学趣事多
  • 赵丽颖有新恋情?邓超一不小心提到了她男朋友
  • 林心如谈“幸福”的定义:每天都在笑
  • 外媒称中国正在研发百亿亿次超级计算机
  • 邓超狂晒打篮球帅照 孙俪冷回10字笑翻众人
  • 48亿:北京打造全球最亮“慧眼”
  • 中国基建狂魔:11072米世界第一航道桥合龙
  • 中国建立了146亿美元的互联网投资基金
  • 历届美国总统经历的市场
  • 市场:特朗普就任的第一周
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3012|回复: 9

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

[复制链接]

14

主题

375

帖子

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弄的这么复杂,面试的人真是
有点变态。不过话说回来也怪我一开始没跟他问清楚!最后面试完了想骂人

--


微信公众号】funinusa : 每日微信滚动更新美国市场打折团购折扣Coupon讯息。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

19

主题

84

帖子

108

积分

注册会员

Rank: 2

积分
108
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

主题

245

帖子

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




--

22

主题

84

帖子

136

积分

注册会员

Rank: 2

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


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

19

主题

88

帖子

126

积分

注册会员

Rank: 2

积分
126
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弄的这么复杂,面试的人真是
有点变态。不过话说回来也怪我一开始没跟他问清楚!最后面试完了想骂人

--

28

主题

101

帖子

150

积分

注册会员

Rank: 2

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


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

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



--

25

主题

94

帖子

139

积分

注册会员

Rank: 2

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


有cycle 不是叫图吗?



--

26

主题

97

帖子

159

积分

注册会员

Rank: 2

积分
159
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

主题

96

帖子

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?

14

主题

1124

帖子

2216

积分

金牌会员

Rank: 6Rank: 6

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

本版积分规则

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

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

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

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

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