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

来来 show 智商的来做笔试题

  •  
  •   rootzeal · 2019-03-30 22:04:54 +08:00 via Android · 2555 次点击
    这是一个创建于 1824 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这是一道我们公司的笔试题 那天遇到了连我都做不起是不是要被开了呀 各位是时候展现真正的实力了 靠你们了
    https://mp.weixin.qq.com/s/ZG90qxnenoJuRUDezNbgEQ
    第 1 条附言  ·  2019-04-01 09:23:57 +08:00
    果然 v 友们都很牛 B 呀 然鹅来面试的应届生至今没有一个能做的 甚至看懂题目的 不多😂 惆怅呀 可能题没有这个文章上的这么明显
    还有大家考虑下 分布式和 sql 的实现
    第 2 条附言  ·  2019-04-01 09:24:10 +08:00
    果然 v 友们都很牛 B 呀 然鹅来面试的应届生至今没有一个能做的 甚至看懂题目的 不多 惆怅呀 可能题没有这个文章上的这么明显
    还有大家考虑下 分布式和 sql 的实现
    18 条回复    2019-04-01 10:36:44 +08:00
    brainfxxk
        1
    brainfxxk  
       2019-03-30 22:11:22 +08:00
    无向图找连通分量?
    AlisaDestiny
        2
    AlisaDestiny  
       2019-03-30 22:18:38 +08:00
    并查集?
    casparchen
        3
    casparchen  
       2019-03-30 22:29:33 +08:00   ❤️ 1
    并查集统计森林中树的个数,活着直接遍历搜索。这是个简单题啊
    also24
        4
    also24  
       2019-03-30 22:40:01 +08:00
    第一反应并查集,但是感觉这么常规的题目很没意思阿。

    仔细一看题目还贴心的区分了 c p 两类,那应该还有办法优化下效率(只需要重点关注连接了多条道路的城市就够了),不过懒得细想了哈哈哈哈
    mixz
        5
    mixz  
       2019-03-30 22:45:43 +08:00
    很简单的题目,也可以用 dfs 套循环来代替并查集。
    RingoTC
        6
    RingoTC  
       2019-03-30 22:51:42 +08:00 via Android
    @casparchen 不应该是树吧,是图的连通子图。
    stevenbipt
        7
    stevenbipt  
       2019-03-30 23:01:17 +08:00
    第一想法是并查集
    mikeguan
        8
    mikeguan  
       2019-03-30 23:03:04 +08:00 via Android
    例子中的 c0 为什么不是独立的
    also24
        9
    also24  
       2019-03-30 23:19:25 +08:00
    @stevenbipt #7 例子是没错的阿
    stevenbipt
        10
    stevenbipt  
       2019-03-30 23:32:01 +08:00
    @also24 老铁你可能艾特错人了
    casparchen
        11
    casparchen  
       2019-03-30 23:33:01 +08:00   ❤️ 1
    @RingoTC #6 不是说了转成并查集问题么,并查集不是树是什么。
    also24
        12
    also24  
       2019-03-30 23:38:16 +08:00 via Android
    @stevenbipt 咦… 我的错我的错… 看来现在手越来越不稳了啊
    yswb
        13
    yswb  
       2019-03-31 00:12:39 +08:00
    这个题目内容就有问题吧,图上有 6 条连线,但是数据只给了 5 个关系,按这个数据来看的话 c0 是孤立的了
    necomancer
        14
    necomancer  
       2019-03-31 11:52:25 +08:00
    嗯……根据这个做个邻接表然后 DFS ?非科班想的笨办法。P.S. 你的数据少一组 [c2, p2] 吧?
    qqor
        15
    qqor  
       2019-03-31 22:00:49 +08:00 via Android
    404 ?
    原来我屏蔽这个网址了,哈!
    rootzeal
        16
    rootzeal  
    OP
       2019-04-01 08:33:40 +08:00 via Android
    @brainfxxk 对是这个意思 有没有办法在分布式或者 sql 环境下解决这个问题
    zdkk
        17
    zdkk  
       2019-04-01 10:25:58 +08:00
    @yswb c2 和 c0 少一个关系,不知道是题目这样设计,还是楼主疏忽
    rootzeal
        18
    rootzeal  
    OP
       2019-04-01 10:36:44 +08:00 via Android
    @zdkk 我得错😂
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4337 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:12 · PVG 18:12 · LAX 03:12 · JFK 06:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.