V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nowcoder
V2EX  ›  程序员

Homebrew 的作者被 Google 拒啦,因为他不会翻转二叉树

  nowcoder · 2015-06-11 12:01:06 +08:00 · 23402 次点击
这是一个创建于 3213 天前的主题,其中的信息可能已经有所发展或是发生改变。

Homebrew 的作者被 Google 拒啦,因为他不会翻转二叉树,然后作者在twitter上开骂啦,然后很多公司开始抢人了。

你来挑战一下翻转二叉树吧
http://www.nowcoder.com/books/coding-interviews/564f4c26aa584921bc75623e48ca3011

非递归版本的答案如下:
http://www.nowcoder.com/questionTerminal/bcffd7e8a0d4402c99773bed98690bb7

89 条回复    2021-12-09 19:54:22 +08:00
huanghuaxin
    1
huanghuaxin  
   2015-06-11 12:07:24 +08:00
我也做不出来…
yasonyyx
    2
yasonyyx  
   2015-06-11 12:07:54 +08:00
不要忘了抄送给 Max Howell
phoenixlzx
    3
phoenixlzx  
   2015-06-11 12:10:50 +08:00   ❤️ 6
Google 的算法很牛的,例如你在 Google+ 上发 po 文,带有一个 tag 叫做 #Google你个SB

它会自动帮你打上一个 tag 叫做 #Google你个大SB
nowcoder
    4
nowcoder  
OP
   2015-06-11 12:11:27 +08:00
@phoenixlzx ......
magicdawn
    5
magicdawn  
   2015-06-11 12:17:05 +08:00
原来翻转就是左右换一下~
gooffer
    6
gooffer  
   2015-06-11 12:18:37 +08:00
递归很容易实现啊
leopku
    7
leopku  
   2015-06-11 12:26:19 +08:00
`on a whiteboard` 这是要手写的节奏啊,不刷题库我也写不粗来
gengrui
    8
gengrui  
   2015-06-11 12:27:12 +08:00
我当初面Facebook的Android position的时候,code test 是做一个二进制加法器。果然挂了...
wavingclear
    9
wavingclear  
   2015-06-11 12:31:24 +08:00
@magicdawn 刚看到这个新闻就想上下翻么这怎么翻……
MrGba2z
    10
MrGba2z  
   2015-06-11 12:37:48 +08:00
为啥又开了一帖子, 而且还置顶了.
chenshaoju
    11
chenshaoju  
   2015-06-11 12:39:12 +08:00
@MrGba2z 这是商业推广……
MrGba2z
    12
MrGba2z  
   2015-06-11 12:41:29 +08:00
@chenshaoju
噢, 学渣自动忽略了最后两段 现在才看到
Xingbao
    13
Xingbao  
   2015-06-11 12:49:25 +08:00
就一悲剧,话说谷歌的面试官不认识他么
laotaitai
    14
laotaitai  
   2015-06-11 13:00:49 +08:00 via Android
brew作者只写了这个有名的工具么?若是,不会翻转二叉树悲剧,也是正常的,面试Google,你所有的成就自动忽略掉,只考你真实技能。
xuyl
    15
xuyl  
   2015-06-11 13:01:38 +08:00
二叉树也算是基本的数据结构了,但我们做web开发的根本就用不到了。
patrickwtl
    16
patrickwtl  
   2015-06-11 13:08:49 +08:00
这个题不难吧
hooluupog
    17
hooluupog  
   2015-06-11 13:11:38 +08:00   ❤️ 1
显然Homebrew 的作者是去裸面了,事先也没准备。当初python之父不是都面了10轮么。。
ChiangDi
    18
ChiangDi  
   2015-06-11 13:12:38 +08:00
为何被置顶了?
ChiangDi
    19
ChiangDi  
   2015-06-11 13:13:11 +08:00
懂了原来是牛课网的广告
KingHL
    20
KingHL  
   2015-06-11 13:14:03 +08:00
搞定
nbndco
    21
nbndco  
   2015-06-11 13:15:18 +08:00   ❤️ 1
@laotaitai 反转二叉树是真实技能也是醉了,仿佛有人真正在实际工作中用过一样。mxcl水平如何看看github就知道了,反正我觉得比只会反转二叉树的显然厉害太多。虽然反转二叉树不难,但这门奇怪的“真实技能”基本也就是应届生最精通了。
shiny
    22
shiny  
   2015-06-11 13:17:48 +08:00   ❤️ 1
这个广告打得好。大音希声,大象无形,真正的好广告看不出来是一个广告。
anoymoux
    23
anoymoux  
   2015-06-11 13:21:02 +08:00
baidu亮了。。刚打fanzhuan就反转了-_-
limuxy
    24
limuxy  
   2015-06-11 13:21:55 +08:00   ❤️ 2
众☜看!这是一个二叉树!
yxaaa123
    25
yxaaa123  
   2015-06-11 13:44:36 +08:00
@limuxy 森 <- 这是啥?
x4
    26
x4  
   2015-06-11 13:52:20 +08:00 via Android
@yxaaa123 晶←_←
x4
    27
x4  
   2015-06-11 13:53:32 +08:00 via Android
@anoymoux 试着打布谷鸟
benjiam
    28
benjiam  
   2015-06-11 13:55:23 +08:00   ❤️ 1
说明 也许牛人会因此进不了google, 但是绝对不会有水货进去。
cszjutstar
    29
cszjutstar  
   2015-06-11 14:01:10 +08:00
我也不会二叉树
cancan
    30
cancan  
   2015-06-11 14:03:20 +08:00
好广告。
rainday
    31
rainday  
   2015-06-11 14:04:50 +08:00
这题不难啊
nowcoder
    32
nowcoder  
OP
   2015-06-11 14:21:11 +08:00
@Xingbao 故意为难的吧
AntiGameZ
    33
AntiGameZ  
   2015-06-11 14:24:47 +08:00
真心好广告
lilydjwg
    34
lilydjwg  
   2015-06-11 14:34:14 +08:00
链接在哪里?我要去围观。
lilydjwg
    35
lilydjwg  
   2015-06-11 14:35:30 +08:00
另外吐槽一下这个 nowcoder.com 的代码编辑器里代码的字体竟然不等宽!
nowcoder
    36
nowcoder  
OP
   2015-06-11 14:37:08 +08:00
@lilydjwg 多谢反馈。马上找工程师大哥改改改
sumuye
    37
sumuye  
   2015-06-11 14:38:40 +08:00
哈哈也是倒霉
20150517
    38
20150517  
   2015-06-11 14:48:18 +08:00 via Android
这题不难的,其实进fb,google谁不背些题?我去年电面fb,还有题准备过的
cyshi
    39
cyshi  
   2015-06-11 14:52:24 +08:00
答案正确:恭喜!您提交的程序通过了所有的测试用例

=====

不过个人考察算法题的时候 一般都会让应聘者随意google
Qiangyuan
    40
Qiangyuan  
   2015-06-11 14:54:05 +08:00
图片里这是什么软件?Twitter?没见过,求解
ostholz
    41
ostholz  
   2015-06-11 15:04:37 +08:00   ❤️ 1
有一个回: brew install btree-invert
哈哈
yiplee
    42
yiplee  
   2015-06-11 15:08:50 +08:00
@hooluupog 其实他去面试前有准备,他自己在 Twitter 上面说的。
yiplee
    43
yiplee  
   2015-06-11 15:09:55 +08:00
@Qiangyuan 是 Twitter
bin456789
    44
bin456789  
   2015-06-11 15:21:04 +08:00
1417收藏,真励志
jhdxr
    45
jhdxr  
   2015-06-11 15:27:11 +08:00
@nowcoder 排行居然混着c/c++和java。。。
eriale
    46
eriale  
   2015-06-11 15:29:46 +08:00
fszaer
    47
fszaer  
   2015-06-11 15:34:40 +08:00
@phoenixlzx 呵呵呵呵
nbndco
    48
nbndco  
   2015-06-11 15:40:49 +08:00   ❤️ 11
顺带贴个解答吧,我觉得只有这个答案是理解了什么是数据结构的,问出这个问题的人感觉没有理解什么是数据结构。

https://news.ycombinator.com/item?id=9697008

It can't be just mirroring, because there's the obvious zero-op solution because "left" and "right" don't actually mean anything except when you're visualizing it for humans:
struct NormalNode {
int value;
struct NormalNode *left;
struct NormalNode *right;
};

struct ReversedNode {
int value;
struct ReversedNode *right;
struct ReversedNode *left;
};

struct ReversedNode *reverseTree(struct NormalNode *root) {
return (struct ReversedNode *)root;
}
There. Now left is right and right is left.
21grams
    49
21grams  
   2015-06-11 16:46:28 +08:00
哈哈,楼上的这个太牛了。
heqichang
    50
heqichang  
   2015-06-11 16:50:22 +08:00
@nbndco 我x, 这是个好想法
xhjsxw
    51
xhjsxw  
   2015-06-11 16:50:23 +08:00
刷一遍newcoder就会了
201314
    52
201314  
   2015-06-11 16:53:46 +08:00 via Android
要想会这个题,去牛客刷题哦!!
raincious
    53
raincious  
   2015-06-11 17:01:04 +08:00
@nbndco

最牛的答案出现了,直接改名……
cdwind
    54
cdwind  
   2015-06-11 17:11:55 +08:00   ❤️ 1
这写不出来太不应该了吧,写个递归半分钟的事情。。。

class Solution {
public:
void Mirror(TreeNode *pRoot) {
if (!pRoot)
return;
TreeNode *tmp = pRoot->right;
pRoot->right = pRoot->left;
pRoot->left = tmp;
Mirror(pRoot->right);
Mirror(pRoot->left);
}
};

答案正确:恭喜!您提交的程序通过了所有的测试用例
cdwind
    55
cdwind  
   2015-06-11 17:14:12 +08:00
@cdwind 要求非递归啊。。。
cdwind
    56
cdwind  
   2015-06-11 17:29:57 +08:00
@cdwind
用堆栈模拟下递归..

class Solution {
private:
stack<TreeNode*> mStack;
public:
void Mirror(TreeNode *pRoot) {
mStack.push(pRoot);
while (!mStack.empty()){
TreeNode *rpRoot = mStack.top();
mStack.pop();
if (!rpRoot)
continue;
TreeNode *tmp = rpRoot->right;
rpRoot->right = rpRoot->left;
rpRoot->left = tmp;
mStack.push(rpRoot->right);
mStack.push(rpRoot->left);
}
}
};
initialdp
    57
initialdp  
   2015-06-11 17:45:51 +08:00
把Homebrew卖给google,然后雇佣那个家伙让他天天在白板上反转。
ehs2013
    58
ehs2013  
   2015-06-11 17:50:04 +08:00
@initialdp 那我还是去用 MacPorts 吧……
lsgbhp
    59
lsgbhp  
   2015-06-11 17:58:11 +08:00   ❤️ 1
没人说Max Howell面的是iOS的职位么
fulvaz
    60
fulvaz  
   2015-06-11 18:48:08 +08:00   ❤️ 1
会不会根本不是关键问题

只是因为筛选简单

比如说,好多企业要求985毕业学生,然而他的岗位其实普通大专生就可以了,那为什么还要设置985要求?
设门槛嘛,985有垃圾,大专也有大师,但是很明显985里面更找到靠谱的人几率更大,节约筛选时间.

同理,现在很多公司都有一个恶习就是考算法,都是在设置门槛,很明显,会算法的人里面找到靠谱的几率也很大,看清楚,--> 是几率大 <-----,还是有坑
nowcoder
    61
nowcoder  
OP
   2015-06-11 19:00:02 +08:00
@fulvaz 几率大就够了。企业也要节省时间成本 的
ryd994
    62
ryd994  
   2015-06-11 19:19:11 +08:00
@nbndco 我差点想到………
然而学渣只是想到了用子类,没想到可以直接cast……
jadetang
    63
jadetang  
   2015-06-11 19:57:27 +08:00
@20150517 你怎么过简历筛选的
20150517
    64
20150517  
   2015-06-11 20:01:53 +08:00 via Android
@jadetang 他们linkedin上找到我的,说第一轮电面,就是他们美国电话过来,你通着电话 ,然后在一个网站上让你写程序,他们同时能看到
refresh
    65
refresh  
   2015-06-11 20:02:57 +08:00   ❤️ 1
一姑娘想找一个有钱人做来老公(企业找优秀的程序员),设置了很多科学的筛选方法(某些算法或学历等)来筛选出有钱人。有一天,来了一个亿万富翁,虽然他拿出来了存款(已有成就,而且很优秀),但他很遗憾没通过姑娘的测试。
姑娘说,通过我这套测试的,是百万富翁的机率肯定要大一些,没通过的,肯定是穷屌丝。

结论:思维定势和官僚主义是要命的。
ant_sz
    66
ant_sz  
   2015-06-11 20:16:44 +08:00
感觉只有像这种牛人面到的算法题才会这么简单。。。。即使没专门训练过应该也可以做的出来吧。。。

普通没有其他资历的人遇到的题比这难多了。。。。
spencerqiu
    67
spencerqiu  
   2015-06-11 20:36:46 +08:00
@Livid

这两位。感受到了楼主的恶意啊~

@xhjsxw @201314
ceclinux
    68
ceclinux  
   2015-06-11 21:16:53 +08:00
这个是故意的把……
jadetang
    69
jadetang  
   2015-06-11 21:44:27 +08:00
@20150517 这么说来linkedin还是挺重要的。看来你是牛人啊。能被主动找到
lilydjwg
    70
lilydjwg  
   2015-06-11 21:51:29 +08:00   ❤️ 1
@20150517 我讨厌背题,浪费时间浪费生命。CloudFlare 也讨厌背题的: https://blog.cloudflare.com/cloudflare-interview-questions/
paulagent
    71
paulagent  
   2015-06-11 22:19:31 +08:00
@refresh 举的例子不恰当。公司招聘n人,n可以是几十上百上千上万,一个女人要找这些老公吗? 要是找这些老公还是要根据条件来判断。
sdysj
    72
sdysj  
   2015-06-11 23:26:52 +08:00
homebrew 这种项目都是社区支持上来的,技术含量也不高,居然还能说是他自己写的,人品问题。
zonghua
    73
zonghua  
   2015-06-11 23:45:33 +08:00
@fulvaz 感觉像我这样的只能去要饭了,根本跨不了没有这道坎。
robot9
    74
robot9  
   2015-06-12 03:11:54 +08:00
@gengrui 我最喜欢的问题 = = 加法完了之后做乘法 再有空做除法
gengrui
    75
gengrui  
   2015-06-12 07:30:46 +08:00
@robot9 唉,当时是做phone screen interview, 只给15分钟,确实比较紧张
liuzuo
    76
liuzuo  
   2015-06-12 08:02:12 +08:00 via Android
@gengrui 二进制全加器?
breeswish
    77
breeswish  
   2015-06-12 08:11:22 +08:00   ❤️ 1
谷歌偏爱算法方面厉害的,对于工程方面科技树茂盛的不是很感冒
breeswish
    78
breeswish  
   2015-06-12 08:19:00 +08:00
话说原作者 twitter 上说 “to min-max the tree, ascending to descending.”,说的是颠倒一个堆而不是交换左右 ?
TimLang
    79
TimLang  
   2015-06-12 09:33:34 +08:00
递归很容易解,迭代的话要用栈,递归解法参考: http://yuntui.org/2015/06/Invert_binary-tree/
txl263
    80
txl263  
   2015-06-12 09:52:05 +08:00
原来是牛课网的广告
pinxue
    81
pinxue  
   2015-06-12 12:44:24 +08:00   ❤️ 1
这哥们诚心的吧,没道理写不出来的。我自己以前进上海贝尔时纸上用 C 写过对分查找,进思科时白板上用 Java 写过大数加法,其实心态放平也没啥的。

另外,Google 的招聘流程就是这样子,先要过算法和 HR,然后才会到用人部门。这个对于公司还是有好处的,网红程序员就不容易混进去,国内不少公司扩张期招聘都会引进一堆眼高手低的,就是面试流程太宽松了。
windyboy
    82
windyboy  
   2015-06-12 13:37:12 +08:00
如果怀疑homebrew的作者算法不合格,我想意义就不大的
面试我想只是一个基本的功夫
对于有能力的程序员,算法可以在实际工作中再去搞
当然感觉这哥们也是自视比较高
进不去双方都是损失
lilydjwg
    83
lilydjwg  
   2015-06-12 18:24:55 +08:00
@pinxue 我当年就没有算法耶。
pinxue
    84
pinxue  
   2015-06-12 21:48:19 +08:00
@lilydjwg 这是显摆顔值来了?
konakona
    85
konakona  
   2015-06-12 22:09:44 +08:00
然后作者狠心将Google IP群组Ban了...永生不得brew..
lilydjwg
    86
lilydjwg  
   2015-06-13 08:02:29 +08:00
@konakona 并且所有使用 homebrew 的用户会被询问要不要将默认搜索引擎换成 DuckDuckGo :-D
nikoukou
    87
nikoukou  
   2015-06-13 09:42:41 +08:00
Just turn the whiteboard upside-down.23333333
SmiteChow
    88
SmiteChow  
   2015-06-16 13:01:19 +08:00
囧,生产和科研的差别
LINAICAI
    89
LINAICAI  
   2021-12-09 19:54:22 +08:00
可能他不是科班出身?哈哈哈
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5853 人在线   最高记录 6543   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 33ms · UTC 01:56 · PVG 09:56 · LAX 18:56 · JFK 21:56
Developed with CodeLauncher
♥ Do have faith in what you're doing.