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

 找回密码
 立即注册
  • NASA神秘发现:超越太阳系!
  • 欧洲惊现致命放射性粒子 科学家都蒙了
  • 澳洲一轻型飞机撞上商场坠毁 5人全部死亡
  • 科学家破译蝙蝠聊天内容:对飙垃圾话
  • 范冰冰穿花衣旧照曝光 网友调侃:还以为是谢大脚
  • 杨幂揪心想念女儿 硬起来保护家庭:别说我家人
  • 高晓松晒收藏的《金瓶梅》 书都被读烂了
  • 宇宙神秘难解之题:中国科学家搞定了
  • 历史首次!杨振宁弃美国国籍 转为中科院院士
  • 淘宝违反“广告法”?被起诉索赔20万
  • 星巴克:零售渠道发展
  • 大多退休职工仍在继续工作
  • AMD“Ryzen”:试图占据更多市场份额
  • 机器人会导致失业,我们需要提前做准备
  • Square股票超出预期,上涨44%
  • 美国各地雇员加入“无移民”抗议活动而被解雇
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3016|回复: 9

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

[复制链接]

14

主题

377

帖子

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 : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

22

主题

89

帖子

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

主题

246

帖子

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




--

23

主题

85

帖子

140

积分

注册会员

Rank: 2

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


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

20

主题

89

帖子

135

积分

注册会员

Rank: 2

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

主题

102

帖子

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

主题

96

帖子

151

积分

注册会员

Rank: 2

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


有cycle 不是叫图吗?



--

28

主题

99

帖子

166

积分

注册会员

Rank: 2

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

主题

97

帖子

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

主题

1149

帖子

2267

积分

金牌会员

Rank: 6Rank: 6

积分
2267
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|唐人社区

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

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