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

[9hills]

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

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

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


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

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

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

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

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

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

[dingyaguang117]

楼主公司做啥的

[wy315700]

走得好，，

[XianZaiZhuCe]

这哥们有点刚

[9hills]

@dingyaguang117 就普通的互联网公司啊。。。面试出个算法题不是正常的么，还是一面

总不能直接就来个 BOSS 面吧

[yellowV2ex]

估计对方心里暗骂了十遍“ sb 公司”

[XianZaiZhuCe]

@9hills 普通的互联网公司，啥职位？

[aheadlead]

面啥？
感觉还是蛮容易的啊 就遍历一遍 记录下每个节点的深度就好了

[batman2010]

这不是很基础的题吗?学过数据结构就能答上啊。

[9hills]

@XianZaiZhuCe 运维开发岗

[LaughingMeMe]

题目比较基础

[wbingeek]

挺好的,直接这样就筛了个人.不浪费双方时间...

[maemual]

也许人家刚失恋。。。。

[BillyRen]

坐等《我就是那个除了算法题扭头就走的人》

[Keita1314]

话说我之前面网易游戏的运维开发，都要求在纸上写代码的，面试还是要准备一下的吧，最起码说说思路

[lean]

印象的中，运维是脚本大牛（ 233.。。。

[ophunter]

这个得看应聘职位的高低

[yuezhimsolo]

我不会扭头走，我很诚实地说：能 google 一下么？
什么！不能！
那我不会耶，我忘了……求给机会

[defage]

有一次碰到一个问 langford 数列的。
一时没想出来，面试官还一起讲解，然后让代码实现一下，可惜那天太晚了，自己又无心这个公司， 距离太远了。

[iambic]

- -，大多数人是不会写 bfs 的

[fxxkgw]

我是搞运维的 基本天天跟脚本打交道 我觉得考些比较实际的东西可能更有效
当然如果你需要用算法去排除一部分人那也没办法
现在很多面试的同学都不是裸辞 可能只是在碰个运气，所以没什么准备 估计很多也没心情去跟你手写算法了。。
个人观点

[xp178171640]

使用层序遍历的思路应该可以吧。
之前看过一个题目是分层打印二叉树。
思路基本一样！保存当前层和下一层节点的总节点数。
这样就可以计算出哪一层的节点数最多，
也即是二叉树的宽度。
当然复杂度度为 n ，知不道还有没有其他更好的思路。

[xp178171640]

哦，忘了重点了，那兄弟真是直接就走了？

[meunicorn]

实习生去面试算法表示压力山大。。。

[tabris17]

不考二叉树反转已经是天大的恩典了

[grasses]

有个性

[blacktulip]

不错不错，佩服佩服

[grasses]

这么有个性的，收了吧，还能派他去跟产品经理喷。

[YouXia]

BFS

[vietor]

你让人家工作 N 年的主去和毕业生一样，写笔试题，这不是侮辱？只有毕业生才能记住算法细节，工作中早 hash map 之类的算法库了

[sun2920989]

这个真不过分，可能是面试者对于算法类的面试题没有心理准备吧。

[sun2920989]

不过一般这样的问题就直接写写最重要的代码段或者口述思路也可以，不要过于强求手写的代码一定没有小毛病一定可以直接运行。

[rannnn]

@vietor 你投下 FLAG 看别人问不问你数据结构

[xjbeta]

吾王美如画_(:3 」∠❀)_

[zjbztianya]

做了给过么。。。

[aheadlead]

@vietor 所以说要看是什么岗位啊

[ltype]

devops ，你不让他 5 分钟手写稿红黑树是看不起人家啊

[jason52]

额，楼主是不是那个 fabric 管理过 4000 台的那位运维大叔。。。

[Comdex]

说说思路就好了吧，一些实现细节当场还是有点难为的

[jason52]

我就想问问实现幂等性的思路。

[crowds]

..LZ 这坑定是看了简历感觉没啥好问的就出点算法题把人家打发走了。。
顺带说一句，普通的互联网公司 2333

[jimrok]

人家是觉得招来也不是搞算法的，纯粹刁难人的公司。

[crabRunning]

如果是开发岗，是我也得走装逼不成反被人家装去了，不能忍

[vietor]

@rannnn 嘴遁之术 就行

[huson]

我是觉得除非工作中需要接触算法相关，没必要出算法题，运维是考验解决问题的能力，怎样解决问题才是重点吧

[cgcs]

写代码的，熟悉点基础的数据结构和算法，难道不是应该的么？这跟工作多久，做运维还是开发还是测试，有啥关系么~~~

[mengzhuo]

这树是满的么？
满的就是 N*2 吧，直接 DFS 就好了么

不满的话，条件不够吧

[HerrDu]

逼格高，考考算法也没有关系

[bcys]

好像是基础点吧！！也需要问点逻辑思维，不然真是搬运工了

[kongkongyzt]

原来是百度......怪不得......

[gelupk]

刚在 qq 群里看到邮件截图说百度停止招人了，是真的么？

[newtonisaac]

你自己上次用这个算法是什么时候？

[ming2281]

```
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
}
```
贵司是否要应届生?

[hhacker]

ls 戳得好

[ming2281]

@hhacker 唉,主要是现在校招,郁闷得很

[29488503878]

这哥们挺有性格的啊，不错

[ffffwh]

似乎末端还可以搞搞分支定界优化

[ototsuyume]

这么基础的题目都有这么多人说考来没意义工作以后就忘记了可以看出现在的程序员多么浮躁反智主义多么严重

[yh7gdiaYW]

运维开发需要考算法 /数据结构么...@宇宙中心

[stage37]

@rannnn 出算法题就是为了考智商的， FLAG 考算法不代表考算法就科学啊。

[IwfWcf]

连这种题都写不出的话还叫学过数据结构吗？又不是要求手写红黑树……

[zonghua]

@meunicorn 刚好相反吧，大多数应届就应该会这个。

之前看到一个 ACM （敏感词）的吐槽同面试者把项目经验吹上天，自己没项目表达。

[stage37]

@zonghua 现在国内面应届也不怎么考算法了，因为很多面试官也不熟。对算法很熟手上没什么项目经验的应届面美帝那边 Google 之类的公司比较合适。

[rannnn]

@stage37 一般公司大多有 4 ～ 5 轮面试，考一两轮算法怎么不科学了？

[rannnn]

@stage37 况且这考的是数据结构并不是算法，并不需要智商，需要的是基本功

[ming2281]

@rannnn 有时候面试官靠算法也并不是一定要面试者做出来, 双方的沟通交流才是比较重要的.

[stage37]

@rannnn 刚毕业那会能随手写的叫基本功好，但毕业三五年了不能随手写不能叫基本功差。即便毕业三五年了不能随手写算法题，聪明人和笨人的区别在于聪明人想一想能写，笨人（哪怕他工作中的代码写得很好）不行。考算法科不科学取决于面试官和公司对代码写得好的笨人的态度。

[Andiry]

简单的题目，就算不能秒答，花一分钟正常人应该至少有思路。扭头就走的就让他走吧，不值得可惜。

[ototsuyume]

我想起了之前 V2EX 有个帖那个楼主说面试的时候被问到了像 virtual memory 这种 os 相关的知识,下面也是一堆人说问这种问题没有意义.我觉得大概只要是问到他们不会的问题他们就觉得这种问题没有意义,或者说不面试直接把 offer 送给他们才会满意.

[Lettersong]

自然语言描述：
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;

[ltype]

讲道理，一道 leetcode easy ， acc 前十的题，为什么楼上能扯那么长

[hanliumaozhi]

话说 这不是算法题啊。。。。。。

[zszone]

百度 HR 真会玩啊。

[bbx]

说明并不想去其实。曾经面一家公司，面的太晚，饿了，面试官让优化 code ，我说算了，就这样吧。

[bk201]

你说一个运维的你考人家数据结构怎么觉得都有点为难人家。

[florije]

听说百度也已经开始拥抱变化了呢~~

[shakoon]

很正常的面试，楼上冷嘲热讽说不该对运维出这种题的，感觉不是学渣就是半路出家来这个行业的吧。我毕业若干年了，不做码农也若干年，这种题目也还能轻车熟路。
如果是真的有心这个职位的应聘者，哪怕自己真的写不出代码，把算法思路描述一下也没有问题吧，扭头就走的人，感觉也挺好，真是为双方节约时间和资源。

[play78]

//如果不考虑其他情况，单纯实现，代码不用那么复杂吧。
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);
}

[neutrino]

没有思路，想了一晚上。上面的答案没看懂，有人讲解一下吗。。

[syyy]

楼主刚聊两句就出算法题，真的合适吗？
可能面试的被人坑过。
其实楼主意愿也不是太强烈，否则可以先谈谈别的再看看。
综合而言，就是两方意愿都一般，一个不愁招不到人，一个不愁找不到工作。

[neo2015]

越是刚毕业越写的出来，工作一段时间后彻底写不出来了

我一做 Android 的，貌似想不起平时会遇到这样的问题，不行就谷歌呗。
反正每次项目都可以高效的做出来，优化好

我是很少向底层进发，更多的时候在研究用户，用户想要什么，这个地方的设计合理不合理，交互对不对。然后自己开发的 APP ，用户群里用户咨询问题，他们喜欢什么功能

[hackerwgf]

要是我真的想去这个公司的话，我会厚着脸皮问一下二叉树和宽度是什么意思…或者给我个机会我 google 一下了解概念后给个思路什么的

[hienchu]

@9hills 运维就少问算法吧

[66beta]

哎，想起我去漕河泾某外企面试前端
叫我写 ruby ，不会。。。
叫我写 C 语言遍历二叉树， C 语言早还给老师了，用伪码写了。。。

然后就失去了联系，哈哈哈

[c0878]

估计是个会点 shell 和 python 的运维来投运维开发 结果发现要考算法 直接超出能力范围了

[xxm459259]

这离「算法题」还差得远好不好，就是很基本的数据结构操作。

[Qlccks2]

工作时间越长我忘得越多，只是解决问题的能力提高了。

[chrishine]

曾经面试一个人，额，七八年还是十年的 C++ 开发经验。
我让讲一下 RAII ，我担心自己发音不准，特地写出来这个单词。
然后。。这是啥？

[PublicID]

我们中出了叛徒。

[wshcdr]

恩，按层遍历二叉树的一个变形

/////////////////
#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;
}

[railgun]

运维也要考算法吗……
还是我们公司的运维太低级了？

[blacklee]

只要是开发，任何方向的开发，考算法题就都不过分。
就我自己而言，毕业 10 年，一直在写代码，业余时间甚至写代码分析千万级数据。但是，这种题目，我不会。
我想表达的观点是，这种题目不过分，但是并没有非常深刻的实际意义。

[lijingyu68]

二叉树的深度：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
二叉树的宽度：二叉树的每一层中都有一定数量的节点，节点数最多的那一层的节点数叫做二叉树的宽度。
看到这种题，没准备的话我连什么叫宽度都忘了。。

[WaylanPunch]

这位同学怎么能这样呢？要是我就直接跪下：“我不会！”

[GordianZ]

这种题也就高中 NOIP 入门难度啊，不会的还好意思说自己是修电脑的？

[yoa1q7y]

这哥们的脾性我挺喜欢的

[yoa1q7y]

应该是一个有意思的人

[mahone3297]

我，好像会唉。。。。开心～

[Hongmin]

@lijingyu68 搞了这么多年数据结构，头一次听说宽度。。。。

[tiancaiamao]

这哥们走得太直接了。换成我被面到不会做的算法题，并且觉得面试官有意有算法刁难的。
我就会说：“这道题没思路。要不我出道题你做做吧”。
然后用一道特别难的算法题暴掉面试官。如果没暴掉...挂了也服气的。
PS.这道题倒没什么难度嘛，不就一个层次遍历么。

[KotiyaSanae]

一个简单的层序遍历+排序， O(n)的题，很难？
说考考应届生可以，考工作几年后的人是耻辱？
为什么？
您承认自己连应届生都不如了么？
不去思考然后就说我不会的人，我觉得，至少某些方面，你们已经失去了思考的信心和能力。
扭头就走这不叫性格，这叫无能。
不在工作中用就找借口不去掌握，这是什么逻辑？您真的对您自己负责么？