首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  职场话题

谷歌电面,什么是 Merge Sort ?

  •  
  •   vitovan · 2016-11-18 10:50:16 +08:00 · 7408 次点击
    这是一个创建于 1060 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚刚谷歌电面,问到:"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 也显得很不专业,根本属于民科么,想入行还是要学习领域内的概念。

    共勉~
    75 回复  |  直到 2016-11-21 23:43:43 +08:00
        1
    defclass   2016-11-18 10:53:16 +08:00
    merge sort 常见排序吧...
        2
    shyling   2016-11-18 10:54:55 +08:00
    haha
        3
    muziki   2016-11-18 10:55:32 +08:00
    这个不是算法书里面常见的算法嘛
        4
    anianj   2016-11-18 10:55:49 +08:00
    归并排序?
        5
    aias   2016-11-18 10:57:06 +08:00
    厉害
        6
    pandachow   2016-11-18 10:58:30 +08:00
    haha
        7
    t123yh   2016-11-18 10:59:08 +08:00 via Android
    归并排序,时间复杂度 n log n
        8
    xmoiduts   2016-11-18 10:59:55 +08:00   ♥ 4
    [转发] https://visualgo.net/sorting 选择下面的 MERGE 选项卡。
        9
    starvedcat   2016-11-18 10:59:56 +08:00
    楼主怎么拿到面试的
        10
    hpeng   2016-11-18 11:02:19 +08:00 via iPhone   ♥ 3
    讲道理,这个比翻转二叉树简单多了
        11
    shakespaces   2016-11-18 11:03:33 +08:00 via Android
    hahaha
        12
    BingoXuan   2016-11-18 11:04:17 +08:00 via iPhone
    我记得 merge sort 最常见名字就是快速排序,利用递归算法来分解数组再递归排序合并。现在还能手敲代码
        13
    shsf4   2016-11-18 11:09:08 +08:00
    楼主怎么得到面试机会?
        14
    zhy0216   2016-11-18 11:09:27 +08:00 via iPhone   ♥ 1
    @BingoXuan 快排是 quicksort
        15
    incompatible   2016-11-18 11:21:07 +08:00   ♥ 1
    @BingoXuan 记错了。 Merge sort 在中文里叫“归并排序”,你说的是快速排序是 quick sort 。
        16
    BingoXuan   2016-11-18 11:22:12 +08:00 via iPhone
    @zhy0216 多谢指点,太久没碰算法了!(◎_◎;)
        17
    Dwayne   2016-11-18 11:36:10 +08:00 via iPhone
    归并排序.. 可以拿来求逆序数对
        18
    bazingaterry   2016-11-18 11:38:16 +08:00
    归并排序用来找逆序对数,刚学算法的时候愣是一天没写出来。
        19
    dtfm   2016-11-18 11:39:49 +08:00
    我仿佛已经听到面试官爽朗的笑声
        20
    fyooo   2016-11-18 11:42:27 +08:00
    Orz

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

    楼主很厉害了
        21
    zonyitoo   2016-11-18 11:46:49 +08:00
    楼主这也敢面 Google
        22
    ishamo   2016-11-18 12:09:39 +08:00 via Android
    原址归并还是有点麻烦的吧
        23
    vitovan   2016-11-18 12:12:47 +08:00
    r#13 @starvedcat
    @shsf4

    google foobar
        24
    vitovan   2016-11-18 12:13:05 +08:00
    r#19 @dtfm 哈哈~
        25
    Sasasu   2016-11-18 12:16:33 +08:00 via Android
    你刷过了 foobar 但不知道归并排序?
        26
    vitovan   2016-11-18 12:34:38 +08:00
    r#25 @Sasasu 野路子出身的弊端呀~回头补补算法概念去~
        27
    beimenjun   2016-11-18 12:37:48 +08:00
    不过换个角度,虽然是阴沟翻船了,但是能拿到电面,楼主必有过人之处吧。

    (不过这个 Google 一下很多结果啊)
        28
    tairan2006   2016-11-18 12:39:45 +08:00 via Android
    哈哈哈
        29
    Cbdy   2016-11-18 13:01:43 +08:00
    很常用的稳定排序算法
    t.cn/RfIplc0
        30
    327beckham   2016-11-18 13:16:02 +08:00
    面 google 的话,好歹刷一刷基本算法
        31
    humor66   2016-11-18 13:34:11 +08:00
    不要浪费机会, 好歹算法导论看几遍, leetcode 刷几遍, 祝楼主好运
        32
    v9ox   2016-11-18 13:36:48 +08:00
    运气爆表, 为毛我面试股沟题那么难.
        33
    ljcarsenal   2016-11-18 13:37:07 +08:00 via Android
    @vitovan foobar 啥东西
        34
    easing   2016-11-18 13:42:03 +08:00
    楼主是不想去 google 觉得太 low 了吧?不然都有面试机会为毛假装说不知道 merge sort
        35
    mortonnex   2016-11-18 13:44:21 +08:00 via iPhone
    归并排序

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

    有个图,就很简单了~

    不过楼主不是来活跃气氛的?面 G 还不得翻来覆去刷算法?
        36
    ynyounuo   2016-11-18 13:46:43 +08:00
    @ljcarsenal
    之前为了推广图灵传电影搞得一个隐形招聘
    可以通过一个 IP 触发,也可以通过搜索随机的字串来自动触发
        37
    jiang42   2016-11-18 14:33:13 +08:00 via iPhone
    其实吧,就算知道归并排序也是会被刷的 233333

    我还知道桶排序, Tim Sort ,照样电面被刷😂😂
        38
    aussieweever   2016-11-18 14:45:20 +08:00 via Android
    当年 google 还在国内的时候也拿到过电面,可惜技能值太低
        39
    macemers   2016-11-18 15:39:21 +08:00 via Android
    hahahaha
        40
    firehot   2016-11-18 15:40:42 +08:00
    面 Google 不刷算法也是心大
        41
    dunn   2016-11-18 16:02:34 +08:00
    haha 最后居然录取了
        42
    Powered   2016-11-18 16:24:01 +08:00 via iPhone
    @vitovan
    @dunn

    结果拿到 offer 了吗?
        43
    timestamp   2016-11-18 16:28:54 +08:00
    归并排序,我这个学化学出生的都知道, hahaha
        44
    iFlicker   2016-11-18 16:52:39 +08:00
    😂😂😂 希望下边能看到楼主说:"我被录用了!"的消息~
        45
    KaoN   2016-11-18 17:07:45 +08:00 via iPhone
    lz 一定是被录取了才发帖的!
        46
    limitsy   2016-11-18 17:36:09 +08:00
    只有我觉得楼主不是不知道归并 而是不知道 Merge Sort 是 归并么。。
        47
    vitovan   2016-11-18 18:41:23 +08:00
    r#46 @limitsy 我也不知道归并,数据结构课一节只上过一节,其他全窝在宿舍抠 VB 了,我真是......
        48
    arnofeng   2016-11-18 19:41:29 +08:00
    haha 最后居然录取了
        49
    wintercoder   2016-11-18 21:58:50 +08:00
    。。。你居然能到面试,我都挂笔试了
        50
    suliuyes   2016-11-18 22:33:05 +08:00
    我这种糙汉一看都知道是归并排序(平常常说 merge 分支什么的)……讲道理,楼主到底怎么拿到面试机会的……:)
        51
    n6DD1A640   2016-11-18 23:39:11 +08:00
    一会楼主附言说已入职,打脸啪啪啪
        52
    snnn   2016-11-18 23:42:14 +08:00
    他是开玩笑的。 google foobar 的题挺难的,最简单的也是类似于最大流最小割这种难度的。我刷完了所有题。
        53
    20015jjw   2016-11-19 06:35:41 +08:00 via Android
    至少数据结构 /基本算法 /lc 刷一边吧... 基本的尊重呢...
    google 的题是真的好玩不过
        54
    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.
        55
    vitovan   2016-11-19 08:22:48 +08:00
    r#54 @Ahri I haven't signed anything.
        56
    vitovan   2016-11-19 08:24:35 +08:00
    r#53 @20015jjw 只是想拯救一下小兔子~没想到...
        57
    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.
        58
    wwhc   2016-11-19 08:48:07 +08:00
    @Ahri 电话面试有签有不签的
        59
    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?
    😎
        60
    aprikyblue   2016-11-19 09:09:24 +08:00 via Android
    ha ha ha
        61
    lts9165   2016-11-19 09:20:05 +08:00
    根本不敢说话,怕被 lz 转身入职打脸
        62
    cxshun   2016-11-19 09:26:03 +08:00
    merge sort 就是归并排序哦,话说楼主是怎么拿到面试机会的啊?

    谷歌的面试基本就要靠算法啦,算法牛怎么都行,算法烂怎么都不行。
        63
    mauve   2016-11-19 11:08:20 +08:00
    type it in your website google.com and you 'll get it
        64
    Tangdixi   2016-11-19 12:33:50 +08:00 via iPhone
    这个真的要好好反省下了楼主 题都不刷 …
        65
    huntzhan   2016-11-19 12:36:06 +08:00
    根本不敢说话,怕被 lz 转身入职打脸
        66
    haihan   2016-11-19 13:09:30 +08:00   ♥ 1
    个人感觉这就是文化问题。既然想进去,就得从面试开始适应对面的文化。
        67
    cppgohan   2016-11-19 15:37:24 +08:00
    楼主在国内, 还是在国外?

    面试官是歪果仁? 也会说 HaHa 蛤蛤
        68
    cppgohan   2016-11-19 15:41:53 +08:00   ♥ 1
    可以参考 homebrew 作者, 白板编程反转二叉树, 然后就没有然后. :|
        69
    hantsy   2016-11-19 16:16:19 +08:00
    刚毕业的时候面这些应该都没问题,这些排序以前用 C 语言都写过。。。现在嘛,我也只能 Haha 了。
        70
    vitovan   2016-11-19 18:59:52 +08:00 via Android
    @cppgohan 「哈哈」应该是全球通用的吧,哈哈大笑不分种族性别及国籍的,私以为。
        71
    snoopygao   2016-11-19 20:07:50 +08:00
    @aias 又见魔性狗头,混 v2 的就这么几个人么
        72
    aias   2016-11-19 22:40:21 +08:00
        73
    Yc1992   2016-11-20 12:55:06 +08:00 via Android
    一场和老外的尬聊
        74
    wyx   2016-11-20 21:11:47 +08:00
    在线等,很急!
        75
    leeyiw   2016-11-21 23:43:43 +08:00
    haha
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3216 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 32ms · UTC 10:43 · PVG 18:43 · LAX 03:43 · JFK 06:43
    ♥ Do have faith in what you're doing.