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

谷歌电面,什么是 Merge Sort ?

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

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

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

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

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

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

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

    有个图,就很简单了~

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

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

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

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

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