额，出了个算法题结果人家直接扭头就走了

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3360 天前的主题，其中的信息可能已经有所发展或是发生改变。

刚聊两句，出了个算法题：

定义二叉树的宽度为二叉树中包含节点最多的层中的节点数。现有一颗二叉树，其深度不大于 N
基本结构为
typedef struct tree
{
struct tree * left;
struct tree * right;
} * Btree

求二叉树宽度， ROOT 为此二叉树根节点指针

面试者：二叉树改成用数组存储可以么
我：随意
面试者：思索中
......

我：这道题没思路我们换其他方向的问题
面试者：我以前这种题也做过，但现在没心情做题，能走么
我：那你走吧

第 1 条附言 · 2015-10-20 16:20:26 +08:00

这道题考察三个点：
1. 思路。这个思路包含了递归思想，二叉树遍历等，这个我认为是编程基本功，连递归都不能理解，做什么程序员。一般来说只要思路正确，这个题就算过了。

2. 纸上写代码的能力。这个见仁见智，也不会非要写出来的代码一定要能执行，只要伪代码意思到了就行。但是这里有很多细节，比如二叉树的起点，左右递归的终止条件等。考察的是细节。

3. 沟通能力。不管是会还是不会，有思路不会写还是怎么样。要有良好沟通。

最后一点，可以换题。不会可以换一个方向问，有大把的题可以问，不限于算法。比如来个系统设计题之类，面试考察的是整体能力，又不是一道题定胜负，几道题不会没关系的

二叉树

struct

tree

节点

165 条回复 • 2016-06-27 19:22:42 +08:00

1 2

❮

❯

101

zongwan

2015-10-20 12:33:05 +08:00

建议楼主要求人事在招聘条件中加入对二叉树算法题的精通
这样可以节约双方的时间

面试者告别扭头走了是很有礼貌的节约双方时间的做法

写了那么久的代码依然对算法,不能自信到一遍就可以无 bug 运行
更别谈手写这种平时不常使用的

最近最多写的开发算法是 for 循环从微信取数据...
运维相关的工作也只是 dnsmasq iptables 等一些工具的命令.云同步运维配置等无算法关联
学习新技术也只是跑个 docker hadoop 之类的然后埋头看文档...

102

daniellu

2015-10-20 12:38:54 +08:00

换我也走，呵呵，感觉明显就是面试者为了显摆自己或者抓不住职位的面试重点，面试者无能而已。实际的工作，真正需要写复杂算法的职位，有多少呢？更加别说普通互联网公司了。招人，找到合适职位的人最重要，不是找到能写一个算法的人，写的出来，不出活，也是无用。

103

oska874

2015-10-20 12:44:33 +08:00

不会做，还不让人走了。

104

ooh

2015-10-20 12:55:32 +08:00

面试是双方的吧，为什么公司 hr 总把自己放在空中楼阁里面。

105

Andrewliu

2015-10-20 13:00:34 +08:00

搞运维也问算法?
这题也挺简单的吧, BFS 遍历一遍不行找到 max 了嘛....

106

nekoyaki

2015-10-20 13:06:28 +08:00

@KotiyaSanae
不在工作中用就找借口不去掌握，这是什么逻辑？
=======
我不是反对你的观点，单说这句话：这逻辑其实没啥问题呀。我工作中用不到的东西多了，不掌握有什么问题吗？
比如，我喷你“为什么不会西班牙语葡萄牙语、为什么不会月经护理，为什么不学 XXX ，你用不到就找借口不去学，你对自己负责吗？”那我是不是太不讲道理了。
每个人的工作确实不太一样。不去掌握用不到的东西，并不是什么问题。

107

alth0ugh

2015-10-20 13:13:05 +08:00

虽然我也并不会这道题，但是并没觉得 lz 有什么错啊

108

loryyang

2015-10-20 13:25:38 +08:00

这题真不难，没有任何复杂的东西，就简单遍历一遍就好了
而且解法可以变化的地方挺多的，可以看出不少东西：
1. 递归遍历树，参数是树和深度，然后开个数组记录下每个深度的 node 数量
2. 用队列把递归改成迭代，不过队列需要同时保存下节点的深度
3. 用两个数组，每一层是一个数组，每次循环同一深度的节点（一个数组），数组的长度就是这个深度的宽度
<script src="https://gist.github.com/anonymous/53ca446e6dea2552fc9b.js"></script>

109

KotiyaSanae

2015-10-20 13:27:17 +08:00

@nekoyaki 我承认您的指摘很有道理，我也觉得，如果我是个程序员（虽然我的确是），当然我不会也不用去掌握西班牙语，葡萄牙语。如果因为不懂西班牙语或者葡萄牙语就被喷，的确也太不公平。
但是，算法不是西班牙语，不是葡萄牙语。因为，算法在我看来，是基础或者说必不可少的一部分。
譬如，您说您精通德文，然后我问你：请问您知道三四格变形么，您回答不知道。那么这个时候，我必然会对您的水平提出质疑，因为这的确是基础。
请问您，如果您的同事，连二叉树是什么都不知道，您会认为，他是一个合格的程序员么？
请问您，如果您给您同事说了，解释了二叉树，并且强调了其很重要，之后您同事还是不知道二叉树为何，您会认为他是一个合格的程序员么？
每个人的工作确实不太一样，但是在这个行业，基础是相通的，因为抱着不去掌握用不到的东西的念头，于是不去好好巩固和掌握基础，我认为是大问题。
至少，我觉得，人应该对自己和工作更负责。

110

nekoyaki

2015-10-20 13:35:17 +08:00

@KotiyaSanae
所以我说，我不是反对你的观点，而只是说，我引出的那句话的逻辑并没有什么问题。
你的观点我大体是赞同的。但是我的另一个态度是——如果真的理智地确定自己用不到，那不去学也不是大问题。

111

KotiyaSanae

2015-10-20 13:42:44 +08:00

@nekoyaki 恩，您说的是，看个人吧

112

breakind

2015-10-20 13:48:49 +08:00

这种题都没思路的，招来有什么用？
可以写不出代码，但是至少得知道怎么解吧。
很反感现在很多从业者一看到算法就开喷，作为写代码的，每天不都是跟这些东西打交道么。

113

konakona

2015-10-20 14:06:11 +08:00

其实二叉树的应用是很普遍的……为什么那么多人说“工作中用不到算法的时候很多”而由？
WEB 方面：
你写一个 RBAC 的后台，你在根据角色组的权限（ Role ）和菜单（ Node ）的时候就会用到二叉树，这是最常见的例子了。
IOS 方面就更多了。

114

stackpop

2015-10-20 14:12:56 +08:00

呵呵, 现在面算法题在 V2EX 是政治不正确的, 只有退学的和非 CS 科班出身写了很多烂 app 的人在 V2EX 才是很酷的.

115

bobbychen

2015-10-20 14:13:51 +08:00

问题确实很简单~~~可能现在的面试者都比较反感算法方面的东西吧

116

typcn

2015-10-20 14:17:02 +08:00

运维也问算法？

117

jasonding

2015-10-20 14:22:38 +08:00

表示二叉树已经忘光了，排序也忘光了。都是基础算法，但是实际工作中真心完全用不到。实际开发用的最多的还是 HashMap 和 ArrayList,偶尔用用 HashSet 。

118

raincious

2015-10-20 15:09:33 +08:00

是不是题目传导的时候出现问题了？

不知道面试的时候，楼主是不是也像帖子一样把数据结构和问题都写清楚交给被面试者的。毕竟一次性给出太多的东西，缓冲区比较小的人可能根本记不住。况且还包含了“{二叉树中 [包含 (节点) 最多的层] 中的节点数}”这样复杂的描述。

不过光看主帖的话，应该可以推断出楼主已经推测出“*被*面试者是不想做题，只想闪人”的结论了。这倒是符合我的观察，一般不太愿意写程序的人，很大程度上都是怕遇到算法题的。所以考考算法观察下也不错。

119

donglingyongadls

2015-10-20 15:12:15 +08:00

之前阿里缩招，今天百度缩招；挺想奉劝那些说没用的人，潮水退了，才知道谁在裸泳。风口过了，才知道谁是装飞的猪。

120

raingolee

2015-10-20 15:13:24 +08:00

其实最重要还是看什么岗位吧

开发考算法和数据结构无可厚非，

但是运维岗位也考这个怪不了面试者提前离开把

121

feuvan

2015-10-20 15:14:39 +08:00

还是招能白板手写代码的比较可靠啊
哪怕人肉编译不过也行

122

Jimrussell

2015-10-20 15:37:27 +08:00

也许是这个面试者知道自己太水从面子上挂不住呢？又没让白板手写平衡二叉，这题说个大概思路对科班生来说太基础了啊。

123

moro

2015-10-20 15:59:42 +08:00

会不会这个，和运维关系不大吧。
题目不难，可是有用吗。
招人是来解决问题的，不是按这个目的出题的，都是耍流氓。

124

wikinee

2015-10-20 16:11:13 +08:00

感觉好难。
我的思路，看看是不是满二叉树，是的话最后一层，不是倒数第二层

125

9hills

2015-10-20 16:12:57 +08:00

@wikinee 这个思路是错的哈。 77 楼的思路是对的，代码没细看

126

smartdie

2015-10-20 16:28:22 +08:00

觉得不合适，就不浪费双方的时间了。之前有个公司面试我三个多小时，三个技术面试官分别出题，最后 hr 面试。要是 bat 也就算了，还是个做 app 的初创公司……

127

smartdie

2015-10-20 16:30:27 +08:00

其实算法可以考，但是看什么职位多少钱的人，面试者自己心里算计一下觉得没必要就省了大家时间了。

128

Mysdes

2015-10-20 16:30:29 +08:00

老实说，这题让我现做，我也做不出来，因为，我不是程序猿啊，哈哈哈。

129

Kathymomo

2015-10-20 16:34:15 +08:00

老实说，这题让我现做，我也做不出来，因为，我不是程序猿啊，哈哈哈。

130

alexzhang

2015-10-20 16:37:20 +08:00

市场没到如此紧缺的地步吧，怎么这么拽

131

chengh06

2015-10-20 16:40:37 +08:00

看了大家的回复，也是醉了。

132

tempuseraccount

2015-10-20 16:45:03 +08:00

这个都不会的人，招来的确没有什么意义……
这完全不需要任何算法啊，会写搜索就行了

133

tempuseraccount

2015-10-20 16:52:03 +08:00

看了回复，发现有人说运维岗位怎么怎么着，但是 lz 说的是运维开发……
如果 lz 没有乱用词，的确要招 DevOps 的话，这个岗位对计算机科学的基础知识要求还是挺高的，出这么一个考察 CS 基本理解的面试题不算过分

134

suckli

2015-10-20 16:56:18 +08:00

反正我工作了这么多年，从来没自己写过二叉树
掩面 =。=

135

DrowYue

2015-10-20 17:13:01 +08:00

一道 2 、 30 行的基础数据结构题目都搞不定，难道还是面试官的错了？

136

moxhuis

2015-10-20 17:33:16 +08:00

天天扯算法，人家不鸟你并不一定是不会做啊。。
有些情况是，你公司本身就处于备选状态。别人一想还不如去别的。。
面完试，还得被面试官在论坛上秀优越感，也是醉了。
还说了一堆马后炮的事情－－。。

137

z7039585

2015-10-20 17:33:43 +08:00

同意楼上某位的回复。现在 V2EX 上培训班或者半路出身的码农越来越多了，在他们中的一部分人眼里看来算法、数据结构、计算机组成原理这些东西在实际工作上用不到，屁用没有。面试问这个的不是装 b 就是煞笔 :)

138

zongwan

2015-10-20 17:34:35 +08:00

@KotiyaSanae
请默写小学背诵过的<诗经>
如果连小学的都默写不出来的话好意思说自己是毕业的大学生吗?

139

iuxlabs

2015-10-20 18:00:43 +08:00

@breakind 说得好

140

iuxlabs

2015-10-20 18:01:14 +08:00

@stackpop 现在这个风气，实在是不好

141

iuxlabs

2015-10-20 18:02:36 +08:00

@z7039585 是这个问题

142

situs

2015-10-20 18:06:29 +08:00

这个 leetcode 里有，就是 bfs ，声明一个 max ，然后遍历比较 count 与 max 的值。

143

iuxlabs

2015-10-20 18:06:35 +08:00

@cgcs 同意，基本功哦

144

iuxlabs

2015-10-20 18:08:04 +08:00

@ototsuyume 这么浮躁的状况，到底是怎么造成的？

145

expkzb

2015-10-20 18:10:21 +08:00

@iuxlabs 因为 google 很方便，随便查查就能对付了

146

iuxlabs

2015-10-20 18:12:59 +08:00

@KotiyaSanae 完全同意！

147

2015-10-20 18:25:34 +08:00 via Android

难道等你喊下一位？面试本来就是双方互面。比如说，我讨厌面试官的面相。

148

jo32

2015-10-20 18:35:49 +08:00 via iPhone

https://www.google.com/about/careers/students/guide-to-technical-development.html

149

Betsy

2015-10-20 18:36:40 +08:00 via Android

感觉学过数据结构与算法的应该是可以写出个大概的，估计那个人没看过这门课吧...

150

situs

2015-10-20 18:56:10 +08:00

class Node:
def __init__(self,value,left=None,right=None):
self.value=value
self.left=left
self.right=right

def getMaxCount(node):
if node.left is None and node.right.right is None:return 1
else:
import collections
q=collections.deque()
q.appendleft(node)
count=len(q)
m=count
while q :
while count!=0:
root=q.pop()
count=count-1
if root.left:
q.appendleft(root.left)
if root.right:
q.appendleft(root.right)
count=len(q)
m=count if count>m else m
return m