V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
This topic created in 3843 days ago, the information mentioned may be changed or developed.
刚聊两句，出了个算法题：
定义二叉树的宽度为二叉树中包含节点最多的层中的节点数。现有一颗二叉树，其深度不大于 N
基本结构为
typedef struct tree
{
struct tree * left;
struct tree * right;
} * Btree
求二叉树宽度， ROOT 为此二叉树根节点指针
面试者：二叉树改成用数组存储可以么
我：随意
面试者：思索中
......
我：这道题没思路我们换其他方向的问题
面试者：我以前这种题也做过，但现在没心情做题，能走么
我：那你走吧
定义二叉树的宽度为二叉树中包含节点最多的层中的节点数。现有一颗二叉树，其深度不大于 N
基本结构为
typedef struct tree
{
struct tree * left;
struct tree * right;
} * Btree
求二叉树宽度， ROOT 为此二叉树根节点指针
面试者：二叉树改成用数组存储可以么
我：随意
面试者：思索中
......
我：这道题没思路我们换其他方向的问题
面试者：我以前这种题也做过，但现在没心情做题，能走么
我：那你走吧
Supplement 1 · Oct 20, 2015
这道题考察三个点：
1. 思路。这个思路包含了递归思想，二叉树遍历等，这个我认为是编程基本功，连递归都不能理解，做什么程序员。一般来说只要思路正确，这个题就算过了。
2. 纸上写代码的能力。这个见仁见智，也不会非要写出来的代码一定要能执行，只要伪代码意思到了就行。但是这里有很多细节，比如二叉树的起点，左右递归的终止条件等。考察的是细节。
3. 沟通能力。不管是会还是不会，有思路不会写还是怎么样。要有良好沟通。
最后一点，可以换题。不会可以换一个方向问，有大把的题可以问，不限于算法。比如来个系统设计题之类，面试考察的是整体能力，又不是一道题定胜负，几道题不会没关系的
1. 思路。这个思路包含了递归思想，二叉树遍历等，这个我认为是编程基本功，连递归都不能理解，做什么程序员。一般来说只要思路正确，这个题就算过了。
2. 纸上写代码的能力。这个见仁见智，也不会非要写出来的代码一定要能执行，只要伪代码意思到了就行。但是这里有很多细节，比如二叉树的起点，左右递归的终止条件等。考察的是细节。
3. 沟通能力。不管是会还是不会，有思路不会写还是怎么样。要有良好沟通。
最后一点，可以换题。不会可以换一个方向问，有大把的题可以问，不限于算法。比如来个系统设计题之类，面试考察的是整体能力，又不是一道题定胜负，几道题不会没关系的
 |
1
dingyaguang117 Oct 19, 2015 via iPhone  1
楼主公司做啥的
|
 |
2
wy315700 Oct 19, 2015
走得好，，
|
 |
3
XianZaiZhuCe Oct 19, 2015 via Android
这哥们有点刚
|
 |
4
9hills OP |
 |
5
yellowV2ex Oct 19, 2015
估计对方心里暗骂了十遍“ sb 公司”
|
|
6
XianZaiZhuCe Oct 19, 2015 via Android
@9hills 普通的互联网公司，啥职位？
|
 |
7
aheadlead Oct 19, 2015
面啥？
感觉还是蛮容易的啊 就遍历一遍 记录下每个节点的深度就好了 |
 |
8
batman2010 Oct 19, 2015
这不是很基础的题吗?学过数据结构就能答上啊。
|
|
9
9hills OP @XianZaiZhuCe 运维开发岗
|
 |
10
LaughingMeMe Oct 19, 2015
题目比较基础
|
 |
11
wbingeek Oct 19, 2015
挺好的,直接这样就筛了个人.不浪费双方时间...
|
 |
12
maemual Oct 19, 2015
也许人家刚失恋。。。。
|
 |
13
BillyRen Oct 19, 2015
坐等《我就是那个除了算法题扭头就走的人》
|
 |
14
Keita1314 Oct 19, 2015
话说我之前面网易游戏的运维开发，都要求在纸上写代码的，面试还是要准备一下的吧，最起码说说思路
|
 |
15
lean Oct 19, 2015
印象的中，运维是脚本大牛（ 233.。。。
|
 |
16
ophunter Oct 19, 2015
这个得看应聘职位的高低
|
 |
17
yuezhimsolo Oct 19, 2015
我不会扭头走，我很诚实地说：能 google 一下么？
什么！不能！ 那我不会耶，我忘了……求给机会 |
 |
18
defage Oct 19, 2015 1
有一次碰到一个问 langford 数列的。
一时没想出来，面试官还一起讲解，然后让代码实现一下，可惜那天太晚了，自己又无心这个公司， 距离太远了。 |
 |
19
iambic Oct 19, 2015
- -，大多数人是不会写 bfs 的
|
 |
20
fxxkgw Oct 19, 2015
我是搞运维的 基本天天跟脚本打交道 我觉得考些比较实际的东西可能更有效
当然如果你需要用算法去排除一部分人那也没办法 现在很多面试的同学都不是裸辞 可能只是在碰个运气，所以没什么准备 估计很多也没心情去跟你手写算法了。。 个人观点 |
 |
21
xp178171640 Oct 19, 2015 1
使用层序遍历的思路应该可以吧。
之前看过一个题目是分层打印二叉树。 思路基本一样！保存当前层和下一层节点的总节点数。 这样就可以计算出哪一层的节点数最多， 也即是二叉树的宽度。 当然复杂度度为 n ，知不道还有没有其他更好的思路。 |
|
22
xp178171640 Oct 19, 2015
哦，忘了重点了，那兄弟真是直接就走了？
|
 |
23
meunicorn Oct 19, 2015
实习生去面试算法表示压力山大。。。
|
 |
24
tabris17 Oct 19, 2015
不考二叉树反转已经是天大的恩典了
|
 |
25
grasses Oct 19, 2015
有个性
|
 |
26
blacktulip Oct 19, 2015 via iPhone
不错不错，佩服佩服
|
|
27
grasses Oct 19, 2015
这么有个性的，收了吧，还能派他去跟产品经理喷。
|
 |
28
YouXia Oct 19, 2015
BFS
|
 |
29
vietor Oct 19, 2015 via Android
你让人家工作 N 年的主去和毕业生一样，写笔试题，这不是侮辱？只有毕业生才能记住算法细节，工作中早 hash map 之类的算法库了
|
 |
30
sun2920989 Oct 19, 2015
这个真不过分，可能是面试者对于算法类的面试题没有心理准备吧。
|
|
31
sun2920989 Oct 19, 2015
不过一般这样的问题就直接写写最重要的代码段或者口述思路也可以，不要过于强求手写的代码一定没有小毛病一定可以直接运行。
|
 |
33
xjbeta Oct 19, 2015
吾王美如画_(:3 」∠❀)_
|
 |
34
zjbztianya Oct 19, 2015
做了给过么。。。
|
 |
36
ltype Oct 19, 2015
devops ，你不让他 5 分钟手写稿红黑树是看不起人家啊
|
 |
37
jason52 Oct 19, 2015 via Android
额，楼主是不是那个 fabric 管理过 4000 台的那位运维大叔。。。
|
 |
38
Comdex Oct 19, 2015
说说思路就好了吧，一些实现细节当场还是有点难为的
|
|
39
jason52 Oct 19, 2015 via Android
我就想问问实现幂等性的思路。
|
 |
40
crowds Oct 19, 2015
..LZ 这坑定是看了简历感觉没啥好问的就出点算法题把人家打发走了。。
顺带说一句，普通的互联网公司 2333 |
 |
41
jimrok Oct 19, 2015
人家是觉得招来也不是搞算法的，纯粹刁难人的公司。
|
 |
42
crabRunning Oct 19, 2015 via Android
如果是开发岗，是我也得走装逼不成反被人家装去了，不能忍
|
 |
44
huson Oct 19, 2015
我是觉得除非工作中需要接触算法相关，没必要出算法题，运维是考验解决问题的能力，怎样解决问题才是重点吧
|
 |
45
cgcs Oct 19, 2015
写代码的，熟悉点基础的数据结构和算法，难道不是应该的么？这跟工作多久，做运维还是开发还是测试，有啥关系么~~~
|
 |
46
mengzhuo Oct 19, 2015
这树是满的么？
满的就是 N*2 吧，直接 DFS 就好了么 不满的话，条件不够吧 |
 |
47
HerrDu Oct 19, 2015
逼格高，考考算法也没有关系
|
 |
48
bcys Oct 19, 2015
好像是基础点吧！！也需要问点逻辑思维，不然真是搬运工了
|
 |
49
kongkongyzt Oct 19, 2015
原来是百度......怪不得......
|
 |
50
gelupk Oct 19, 2015
刚在 qq 群里看到邮件截图说百度停止招人了，是真的么？
|
 |
51
newtonisaac Oct 19, 2015 3
你自己上次用这个算法是什么时候？
|
 |
52
ming2281 Oct 19, 2015
```
int widthOfBinTree(root) { /** * 原来的层次遍历转化一下 */ if (root == NULL) return 0 q //q is queue maxWidth = 1, curWidth = 1,nextWidth = 0 q.enqueue(root) while (!q.empty()) { while (curWidth != 0) { //当前层有多少层,就循环多少次-->主要是记录下一层节点数 curWidth-- TreeNode x = q.dequeue() if (x.l != NULL) { q.enqueue(x.l) nextWidth++ } if (x.r != NULL) { q.enqueue(x.r) nextWidth++ } } curWidth = nextWidth //当前层了 maxWidth = max(maxWidth, curWidth) //取大 nextWidth = 0 //转为记录下一层 } return maxWidth } ``` 贵司是否要应届生? |
 |
53
hhacker Oct 19, 2015
ls 戳得好
|
 |
55
29488503878 Oct 19, 2015
这哥们挺有性格的啊，不错
|
 |
56
ffffwh Oct 19, 2015 via Android
似乎末端还可以搞搞分支定界优化
|
 |
57
ototsuyume Oct 19, 2015 7
这么基础的题目都有这么多人说考来没意义工作以后就忘记了可以看出现在的程序员多么浮躁反智主义多么严重
|
 |
58
yh7gdiaYW Oct 19, 2015
运维开发需要考算法 /数据结构么...@宇宙中心
|
 |
60
IwfWcf Oct 19, 2015 2
连这种题都写不出的话还叫学过数据结构吗？又不是要求手写红黑树……
|
 |
62
stage37 Oct 19, 2015
@zonghua 现在国内面应届也不怎么考算法了，因为很多面试官也不熟。对算法很熟手上没什么项目经验的应届面美帝那边 Google 之类的公司比较合适。
|
|
66
stage37 Oct 19, 2015
@rannnn 刚毕业那会能随手写的叫基本功好，但毕业三五年了不能随手写不能叫基本功差。即便毕业三五年了不能随手写算法题，聪明人和笨人的区别在于聪明人想一想能写，笨人（哪怕他工作中的代码写得很好）不行。考算法科不科学取决于面试官和公司对代码写得好的笨人的态度。
|
 |
67
Andiry Oct 19, 2015 1
简单的题目，就算不能秒答，花一分钟正常人应该至少有思路。扭头就走的就让他走吧，不值得可惜。
|
|
68
ototsuyume Oct 19, 2015
我想起了之前 V2EX 有个帖那个楼主说面试的时候被问到了像 virtual memory 这种 os 相关的知识,下面也是一堆人说问这种问题没有意义.我觉得大概只要是问到他们不会的问题他们就觉得这种问题没有意义,或者说不面试直接把 offer 送给他们才会满意.
|
 |
69
Lettersong Oct 20, 2015
自然语言描述：
struct node { Elementtype data; node *LChild; node *RChild; int level; } 节点结构如上， level 用来标识节点所处的层数， 算法核心：层序遍历，需要用到队列 过程： 节点初始 level 都为 0 根节点入队 int maxLevel = 0; while (队列不为空) { node *tmp = 队列出队; if (tmp->LChild) { tmp->LChild 入队 tmp->LChild->level = tmp->level + 1; } if (tmp->RChild) { tmp->RChild 入队 tmp->RChild->level = tmp->level + 1; } // 这一句保证最后 maxLevel 为最底层节点的层数 if (tmp->level > maxLevel) maxLevel = tmp->level; } 上面的层序遍历时间复杂度为 O(n)，做完之后每个节点都有自己所属的层数 vector<int> flag(maxLevel, 0); 再遍历一遍整棵树，每访问一个节点， flag.at(node->level) += 1; 时间复杂度仍然是 O(n) 最后扫一遍 flag 数组，找出最大的值就是宽度。 return 0; |
|
70
ltype Oct 20, 2015 1
讲道理，一道 leetcode easy ， acc 前十的题，为什么楼上能扯那么长
|
 |
71
hanliumaozhi Oct 20, 2015
话说 这不是算法题啊。。。。。。
|
 |
72
zszone Oct 20, 2015
百度 HR 真会玩啊。
|
 |
73
bbx Oct 20, 2015
说明并不想去其实。曾经面一家公司，面的太晚，饿了，面试官让优化 code ，我说算了，就这样吧。
|
 |
74
bk201 Oct 20, 2015
你说一个运维的你考人家数据结构怎么觉得都有点为难人家。
|
 |
75
florije Oct 20, 2015
听说百度也已经开始拥抱变化了呢~~
|
 |
76
shakoon Oct 20, 2015
很正常的面试，楼上冷嘲热讽说不该对运维出这种题的，感觉不是学渣就是半路出家来这个行业的吧。我毕业若干年了，不做码农也若干年，这种题目也还能轻车熟路。
如果是真的有心这个职位的应聘者，哪怕自己真的写不出代码，把算法思路描述一下也没有问题吧，扭头就走的人，感觉也挺好，真是为双方节约时间和资源。 |
 |
77
play78 Oct 20, 2015 1
//如果不考虑其他情况，单纯实现，代码不用那么复杂吧。
void cnt[MAX] = {0}; void dfs(tree * n, int deep){ if(n == NULL) return ; if(n->left != NULL){ cnt[deep]++; dfs(n->left, deep+1); } if(n->right != NULL){ cnt[deep]++; dfs(n->right, deep+1); } return ; } main(){ cnt[0]=1; dfs(Btree, 1); int m = max(cnt); } |
 |
78
neutrino Oct 20, 2015
没有思路，想了一晚上。上面的答案没看懂，有人讲解一下吗。。
|
 |
79
syyy Oct 20, 2015
楼主刚聊两句就出算法题，真的合适吗？
可能面试的被人坑过。 其实楼主意愿也不是太强烈，否则可以先谈谈别的再看看。 综合而言，就是两方意愿都一般，一个不愁招不到人，一个不愁找不到工作。 |
 |
80
neo2015 Oct 20, 2015
越是刚毕业越写的出来，工作一段时间后彻底写不出来了
我一做 Android 的，貌似想不起平时会遇到这样的问题，不行就谷歌呗。 反正每次项目都可以高效的做出来，优化好 我是很少向底层进发，更多的时候在研究用户，用户想要什么，这个地方的设计合理不合理，交互对不对。然后自己开发的 APP ，用户群里用户咨询问题，他们喜欢什么功能 |
 |
81
hackerwgf PRO 要是我真的想去这个公司的话，我会厚着脸皮问一下二叉树和宽度是什么意思…或者给我个机会我 google 一下了解概念后给个思路什么的
|
 |
83
66beta Oct 20, 2015
哎，想起我去漕河泾某外企面试前端
叫我写 ruby ，不会。。。 叫我写 C 语言遍历二叉树， C 语言早还给老师了，用伪码写了。。。 然后就失去了联系，哈哈哈 |
 |
84
c0878 Oct 20, 2015
估计是个会点 shell 和 python 的运维来投运维开发 结果发现要考算法 直接超出能力范围了
|
 |
85
xxm459259 Oct 20, 2015 1
这离「算法题」还差得远好不好，就是很基本的数据结构操作。
|
 |
86
Qlccks2 Oct 20, 2015
工作时间越长我忘得越多，只是解决问题的能力提高了。
|
 |
87
chrishine Oct 20, 2015
曾经面试一个人，额，七八年还是十年的 C++ 开发经验。
我让讲一下 RAII ，我担心自己发音不准，特地写出来这个单词。 然后。。这是啥？ |
 |
88
PublicID Oct 20, 2015
我们中出了叛徒。
|
 |
89
wshcdr Oct 20, 2015
恩，按层遍历二叉树的一个变形
///////////////// #include <iostream> #include <queue> using namespace std; struct Node { Node* left; Node* right; int value; Node(int v) { left = right = NULL; value = v; } ~Node() { if (left) { delete left; left = NULL; } if (right) { delete right; right = NULL; } } }; void PrintLevel(Node* root) { int max_width = 0; queue<Node*> q; if (root) { q.push(root); int cur_level = 1; int cur_level_num = 1; int next_level_num = 0; while(!q.empty()) { Node* cur_node = q.front(); q.pop(); cout << cur_node->value << ", "; cur_level_num--; if (cur_node->left) { q.push(cur_node->left); next_level_num++; } if (cur_node->right) { q.push(cur_node->right); next_level_num++; } if (cur_level_num == 0) { if (q.size() > max_width) { max_width = q.size(); } cout << endl; cur_level++; cur_level_num = next_level_num; next_level_num = 0; } } } cout << "max_width = " << max_width << endl; } int _tmain(int argc, _TCHAR* argv[]) { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); PrintLevel(root); delete root; return 0; } |
 |
90
railgun Oct 20, 2015
运维也要考算法吗……
还是我们公司的运维太低级了？ |
 |
91
blacklee Oct 20, 2015
只要是开发，任何方向的开发，考算法题就都不过分。
就我自己而言，毕业 10 年，一直在写代码，业余时间甚至写代码分析千万级数据。但是，这种题目，我不会。 我想表达的观点是，这种题目不过分，但是并没有非常深刻的实际意义。 |
 |
92
lijingyu68 Oct 20, 2015
二叉树的深度：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
二叉树的宽度：二叉树的每一层中都有一定数量的节点，节点数最多的那一层的节点数叫做二叉树的宽度。 看到这种题，没准备的话我连什么叫宽度都忘了。。 |
 |
93
WaylanPunch Oct 20, 2015
这位同学怎么能这样呢？要是我就直接跪下：“我不会！”
|
 |
94
GordianZ Oct 20, 2015 1
这种题也就高中 NOIP 入门难度啊，不会的还好意思说自己是修电脑的？
|
 |
95
yoa1q7y Oct 20, 2015
这哥们的脾性我挺喜欢的
|
|
96
yoa1q7y Oct 20, 2015
应该是一个有意思的人
|
 |
97
mahone3297 Oct 20, 2015
我，好像会唉。。。。开心～
|
 |
98
Hongmin Oct 20, 2015
@lijingyu68 搞了这么多年数据结构，头一次听说宽度。。。。
|
 |
99
tiancaiamao Oct 20, 2015
这哥们走得太直接了。换成我被面到不会做的算法题，并且觉得面试官有意有算法刁难的。
我就会说：“这道题没思路。要不我出道题你做做吧”。 然后用一道特别难的算法题暴掉面试官。如果没暴掉...挂了也服气的。 PS.这道题倒没什么难度嘛，不就一个层次遍历么。 |
 |
100
KotiyaSanae Oct 20, 2015 3
一个简单的层序遍历+排序， O(n)的题，很难？
说考考应届生可以，考工作几年后的人是耻辱？ 为什么？ 您承认自己连应届生都不如了么？ 不去思考然后就说我不会的人，我觉得，至少某些方面，你们已经失去了思考的信心和能力。 扭头就走这不叫性格，这叫无能。 不在工作中用就找借口不去掌握，这是什么逻辑？您真的对您自己负责么？ |
Select Language