W***o
发帖数: 6519 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: Wardo (餐厅忙的时候客户端，否则服务端), 信区: Programming
标 题: 说一道关于unbalanced树的面试题
发信站: BBS 未名空间站 (Fri Oct 28 16:39:00 2016, 美东)
前两天面试一个公司，题目是用bfs在tree上找string，但是unbalanced tree.
可能有点先入为主的概念，我开始“默认”这是一个unbalanced binary search tree
，写代码到一半的时候，面试的人一再强调unbalanced tree，我当时也被他弄懵了。
写到最后，他说这是一个unsorted tree，我恍然大悟，原来开始他说的unbalanced
tree就是unsorted 的意思，我k，这能是同一个概念吗
我改代码完了之后，他又继续说：这tree里可能有cycle，也就是两个parent nodes可
能会共享一个儿子或孙子node，我k，真是烦。一个tree弄的这么复杂，面试的人真是
有点变态。不过话说回来也怪我一开始没跟他问清楚！最后面试完了想骂人 |
s**********g
发帖数: 14942 | 2 unbalanced tree也没有默认sorted啊..
这个他本来可能想考你communication吧,因为面试一上来不应该先把各种犄角旮旯的
trick问清楚吗..sort与否是最基本的之一了吧 |
c********t
发帖数: 5706 | 3 有cycle还能叫tree吗? 应该骂他。求问一下, bfs或dfs对于unbalanced tree 与
balanced tree有什么不一样吗？
tree
【在 W***o 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: Wardo (餐厅忙的时候客户端，否则服务端), 信区: Programming
: 标 题: 说一道关于unbalanced树的面试题
: 发信站: BBS 未名空间站 (Fri Oct 28 16:39:00 2016, 美东)
: 前两天面试一个公司，题目是用bfs在tree上找string，但是unbalanced tree.
: 可能有点先入为主的概念，我开始“默认”这是一个unbalanced binary search tree
: ，写代码到一半的时候，面试的人一再强调unbalanced tree，我当时也被他弄懵了。
: 写到最后，他说这是一个unsorted tree，我恍然大悟，原来开始他说的unbalanced
: tree就是unsorted 的意思，我k，这能是同一个概念吗
: 我改代码完了之后，他又继续说：这tree里可能有cycle，也就是两个parent nodes可
|
a*******g
发帖数: 3500 | |
W***o
发帖数: 6519 | 5 根据我后来的感觉，面试我的这个人主要是想让我用一个额外的空间数组来track
visited
nodes，这样就会避免cycle的问题。可是，在树上用bfs的时候谁用的着额外的空间数
组来track visited node啊？因为tree根本就不应该有cycle的。
所以，那个面试从一开始他说unbalanced，我就开始犯晕。用bfs还管是否unbalanced？
面试最后他说这是一个unsorted tree，我不得不把判断left/right的那几行去掉，反
正就是统统遍历一次好了。
总之奇葩的面试: unsorted 说成unbalanced；tree里还有tmd cycle
【在 c********t 的大作中提到】
: 有cycle还能叫tree吗? 应该骂他。求问一下, bfs或dfs对于unbalanced tree 与
: balanced tree有什么不一样吗？
:
: tree
|
W***o
发帖数: 6519 | 6 bfs 和 dfs 输出的顺序不一样吧。 unbalanced tree 就是注意一下 缺一个或两个孩
子的情况吧
【在 c********t 的大作中提到】
: 有cycle还能叫tree吗? 应该骂他。求问一下, bfs或dfs对于unbalanced tree 与
: balanced tree有什么不一样吗？
:
: tree
|
c********t
发帖数: 5706 | 7 碰到这样的，真是倒霉。感觉面试70%靠运气，30%靠实力。不过以后先clarify所有问
题再开始解决会比较好。
我的意思是我做bfs 或dfs travel的时候, 从来没考虑tree是不是balanced呀，
unbalanced缺孩子，要做哪些判断？能给个三行codes讲一下吗？多谢！
【在 W***o 的大作中提到】
: bfs 和 dfs 输出的顺序不一样吧。 unbalanced tree 就是注意一下 缺一个或两个孩
: 子的情况吧
|
s**********g
发帖数: 14942 | 8 tree上用bfs不需要额外空间存visited
但是增加visited也就是一点点code的事儿吧？
unbalanced？
【在 W***o 的大作中提到】
: 根据我后来的感觉，面试我的这个人主要是想让我用一个额外的空间数组来track
: visited
: nodes，这样就会避免cycle的问题。可是，在树上用bfs的时候谁用的着额外的空间数
: 组来track visited node啊？因为tree根本就不应该有cycle的。
: 所以，那个面试从一开始他说unbalanced，我就开始犯晕。用bfs还管是否unbalanced？
: 面试最后他说这是一个unsorted tree，我不得不把判断left/right的那几行去掉，反
: 正就是统统遍历一次好了。
: 总之奇葩的面试: unsorted 说成unbalanced；tree里还有tmd cycle
|
