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