谷歌电面，什么是 Merge Sort ?

V2EX = way to explore

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

现在注册

已注册用户请登录

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

刚刚谷歌电面，问到："average case time complexity of merge sort"，然后我说："Haha, what is merge sort?"，然后电话里互相 haha 了一会儿，然后就没有然后了。

第 1 条附言 · 2016-11-19 07:36:41 +08:00

没去刷题的原因是觉得自己本来不懂得算法这些东西，去刷了也不知道有多大效果，也想着无所谓了反正算法不行，不如就当闲聊吧，这样也更真实～

已决定要补补算法相关知识，用了 Merge Sort 却不知道那是 Merge Sort 也显得很不专业，根本属于民科么，想入行还是要学习领域内的概念。

共勉～

sort

merge

电面

haha

75 条回复 • 2016-11-21 23:43:43 +08:00

defclass

2016-11-18 10:53:16 +08:00

merge sort 常见排序吧...

shyling

2016-11-18 10:54:55 +08:00

haha

muziki

2016-11-18 10:55:32 +08:00

这个不是算法书里面常见的算法嘛

anianj

2016-11-18 10:55:49 +08:00

归并排序？

aias

2016-11-18 10:57:06 +08:00

厉害

pandachow

2016-11-18 10:58:30 +08:00

haha

t123yh

2016-11-18 10:59:08 +08:00 via Android

归并排序，时间复杂度 n log n

xmoiduts

2016-11-18 10:59:55 +08:00

[转发] https://visualgo.net/sorting 选择下面的 MERGE 选项卡。

starvedcat

2016-11-18 10:59:56 +08:00

楼主怎么拿到面试的

hpeng

2016-11-18 11:02:19 +08:00 via iPhone

讲道理，这个比翻转二叉树简单多了

shakespaces

2016-11-18 11:03:33 +08:00 via Android

hahaha

BingoXuan

2016-11-18 11:04:17 +08:00 via iPhone

我记得 merge sort 最常见名字就是快速排序，利用递归算法来分解数组再递归排序合并。现在还能手敲代码

shsf4

2016-11-18 11:09:08 +08:00

楼主怎么得到面试机会？

zhy0216

2016-11-18 11:09:27 +08:00 via iPhone

@BingoXuan 快排是 quicksort

incompatible

2016-11-18 11:21:07 +08:00

@BingoXuan 记错了。 Merge sort 在中文里叫“归并排序”，你说的是快速排序是 quick sort 。

BingoXuan

2016-11-18 11:22:12 +08:00 via iPhone

@zhy0216 多谢指点，太久没碰算法了！(◎_◎;)

Dwayne

2016-11-18 11:36:10 +08:00 via iPhone

归并排序.. 可以拿来求逆序数对

bazingaterry

2016-11-18 11:38:16 +08:00

归并排序用来找逆序对数，刚学算法的时候愣是一天没写出来。

dtfm

2016-11-18 11:39:49 +08:00

我仿佛已经听到面试官爽朗的笑声

fyooo

2016-11-18 11:42:27 +08:00

Orz

Google 是我辈想都不敢想的牛公司，我连面试机会都没有呢。

楼主很厉害了

zonyitoo

2016-11-18 11:46:49 +08:00

楼主这也敢面 Google

ishamo

2016-11-18 12:09:39 +08:00 via Android

原址归并还是有点麻烦的吧

vitovan

2016-11-18 12:12:47 +08:00

r#13 @starvedcat
@shsf4

google foobar

vitovan

2016-11-18 12:13:05 +08:00

r#19 @dtfm 哈哈~

Sasasu

2016-11-18 12:16:33 +08:00 via Android

你刷过了 foobar 但不知道归并排序？

vitovan

2016-11-18 12:34:38 +08:00

r#25 @Sasasu 野路子出身的弊端呀~回头补补算法概念去~

beimenjun

2016-11-18 12:37:48 +08:00

不过换个角度，虽然是阴沟翻船了，但是能拿到电面，楼主必有过人之处吧。

（不过这个 Google 一下很多结果啊）

tairan2006

2016-11-18 12:39:45 +08:00 via Android

哈哈哈

Cbdy

2016-11-18 13:01:43 +08:00

很常用的稳定排序算法
t.cn/RfIplc0

327beckham

2016-11-18 13:16:02 +08:00

面 google 的话，好歹刷一刷基本算法

humor66

2016-11-18 13:34:11 +08:00

不要浪费机会，好歹算法导论看几遍， leetcode 刷几遍，祝楼主好运

v9ox

2016-11-18 13:36:48 +08:00

运气爆表, 为毛我面试股沟题那么难.

ljcarsenal

2016-11-18 13:37:07 +08:00 via Android

@vitovan foobar 啥东西

easing

2016-11-18 13:42:03 +08:00

楼主是不想去 google 觉得太 low 了吧？不然都有面试机会为毛假装说不知道 merge sort

mortonnex

2016-11-18 13:44:21 +08:00 via iPhone

归并排序

想了想思路，第一时间进入脑海的是当时刷算法时画的图

有个图，就很简单了~

不过楼主不是来活跃气氛的？面 G 还不得翻来覆去刷算法？

ynyounuo

2016-11-18 13:46:43 +08:00

@ljcarsenal
之前为了推广图灵传电影搞得一个隐形招聘
可以通过一个 IP 触发，也可以通过搜索随机的字串来自动触发

jiang42

2016-11-18 14:33:13 +08:00 via iPhone

其实吧，就算知道归并排序也是会被刷的 233333

我还知道桶排序， Tim Sort ，照样电面被刷😂😂

aussieweever

2016-11-18 14:45:20 +08:00 via Android

当年 google 还在国内的时候也拿到过电面，可惜技能值太低

macemers

2016-11-18 15:39:21 +08:00 via Android

hahahaha

firehot

2016-11-18 15:40:42 +08:00

面 Google 不刷算法也是心大

dunn

2016-11-18 16:02:34 +08:00

haha 最后居然录取了

Powered

2016-11-18 16:24:01 +08:00 via iPhone

@vitovan
@dunn

结果拿到 offer 了吗？

timestamp

2016-11-18 16:28:54 +08:00

归并排序，我这个学化学出生的都知道， hahaha

iFlicker

2016-11-18 16:52:39 +08:00

😂😂😂 希望下边能看到楼主说:"我被录用了！"的消息~

KaoN

2016-11-18 17:07:45 +08:00 via iPhone

lz 一定是被录取了才发帖的！

limitsy

2016-11-18 17:36:09 +08:00

只有我觉得楼主不是不知道归并而是不知道 Merge Sort 是归并么。。

vitovan

2016-11-18 18:41:23 +08:00

r#46 @limitsy 我也不知道归并，数据结构课一节只上过一节，其他全窝在宿舍抠 VB 了，我真是......

arnofeng

2016-11-18 19:41:29 +08:00

haha 最后居然录取了

wintercoder

2016-11-18 21:58:50 +08:00

。。。你居然能到面试，我都挂笔试了

suliuyes

2016-11-18 22:33:05 +08:00

我这种糙汉一看都知道是归并排序（平常常说 merge 分支什么的）……讲道理，楼主到底怎么拿到面试机会的……：）

n6DD1A640

2016-11-18 23:39:11 +08:00

一会楼主附言说已入职，打脸啪啪啪

snnn

2016-11-18 23:42:14 +08:00

他是开玩笑的。 google foobar 的题挺难的，最简单的也是类似于最大流最小割这种难度的。我刷完了所有题。

20015jjw

2016-11-19 06:35:41 +08:00 via Android

至少数据结构 /基本算法 /lc 刷一边吧... 基本的尊重呢...
google 的题是真的好玩不过

Ahri

2016-11-19 08:18:18 +08:00

You signed an NDA with Google in which you agreed you would not disclose your interview questions.

vitovan

2016-11-19 08:22:48 +08:00

r#54 @Ahri I haven't signed anything.

vitovan

2016-11-19 08:24:35 +08:00

r#53 @20015jjw 只是想拯救一下小兔子~没想到...

Ahri

2016-11-19 08:38:23 +08:00

@vitovan I know the process. Either you signed (with ink or electronically) without reading it or you are lying.

wwhc

2016-11-19 08:48:07 +08:00

@Ahri 电话面试有签有不签的

vitovan

2016-11-19 08:49:21 +08:00

r#57 @Ahri
What do you feel when you are typing your comments?
What's the feeling of point out my ignorance or lie?
😎

aprikyblue

2016-11-19 09:09:24 +08:00 via Android

ha ha ha

lts9165

2016-11-19 09:20:05 +08:00

根本不敢说话，怕被 lz 转身入职打脸

cxshun

2016-11-19 09:26:03 +08:00

merge sort 就是归并排序哦，话说楼主是怎么拿到面试机会的啊？

谷歌的面试基本就要靠算法啦，算法牛怎么都行，算法烂怎么都不行。

mauve

2016-11-19 11:08:20 +08:00

type it in your website google.com and you 'll get it

Tangdixi

2016-11-19 12:33:50 +08:00 via iPhone

这个真的要好好反省下了楼主题都不刷 …

huntzhan

2016-11-19 12:36:06 +08:00

根本不敢说话，怕被 lz 转身入职打脸

haihan

2016-11-19 13:09:30 +08:00

个人感觉这就是文化问题。既然想进去，就得从面试开始适应对面的文化。

cppgohan

2016-11-19 15:37:24 +08:00

楼主在国内, 还是在国外?

面试官是歪果仁? 也会说 HaHa 蛤蛤

cppgohan

2016-11-19 15:41:53 +08:00

可以参考 homebrew 作者, 白板编程反转二叉树, 然后就没有然后. :|

hantsy

2016-11-19 16:16:19 +08:00

刚毕业的时候面这些应该都没问题，这些排序以前用 C 语言都写过。。。现在嘛，我也只能 Haha 了。

vitovan

2016-11-19 18:59:52 +08:00 via Android

@cppgohan 「哈哈」应该是全球通用的吧，哈哈大笑不分种族性别及国籍的，私以为。

snoopygao

2016-11-19 20:07:50 +08:00

@aias 又见魔性狗头，混 v2 的就这么几个人么

aias

2016-11-19 22:40:21 +08:00

@snoopygao 233

Yc1992

2016-11-20 12:55:06 +08:00 via Android

一场和老外的尬聊

wyx

2016-11-20 21:11:47 +08:00

在线等，很急！

leeyiw

2016-11-21 23:43:43 +08:00

haha