来来 show 智商的来做笔试题

V2EX = way to explore

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

现在注册

已注册用户请登录

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

这是一道我们公司的笔试题那天遇到了连我都做不起是不是要被开了呀各位是时候展现真正的实力了靠你们了
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 的实现

笔试

来来

智商

show

18 条回复 • 2019-04-01 10:36:44 +08:00

brainfxxk

2019-03-30 22:11:22 +08:00

无向图找连通分量？

AlisaDestiny

2019-03-30 22:18:38 +08:00

并查集？

casparchen

2019-03-30 22:29:33 +08:00

并查集统计森林中树的个数，活着直接遍历搜索。这是个简单题啊

also24

2019-03-30 22:40:01 +08:00

第一反应并查集，但是感觉这么常规的题目很没意思阿。

仔细一看题目还贴心的区分了 c p 两类，那应该还有办法优化下效率（只需要重点关注连接了多条道路的城市就够了），不过懒得细想了哈哈哈哈

mixz

2019-03-30 22:45:43 +08:00

很简单的题目，也可以用 dfs 套循环来代替并查集。

RingoTC

2019-03-30 22:51:42 +08:00 via Android

@casparchen 不应该是树吧，是图的连通子图。

stevenbipt

2019-03-30 23:01:17 +08:00

第一想法是并查集

mikeguan

2019-03-30 23:03:04 +08:00 via Android

例子中的 c0 为什么不是独立的

also24

2019-03-30 23:19:25 +08:00

@stevenbipt #7 例子是没错的阿

stevenbipt

2019-03-30 23:32:01 +08:00

@also24 老铁你可能艾特错人了

casparchen

2019-03-30 23:33:01 +08:00

@RingoTC #6 不是说了转成并查集问题么，并查集不是树是什么。

also24

2019-03-30 23:38:16 +08:00 via Android

@stevenbipt 咦… 我的错我的错… 看来现在手越来越不稳了啊

yswb

2019-03-31 00:12:39 +08:00

这个题目内容就有问题吧，图上有 6 条连线，但是数据只给了 5 个关系，按这个数据来看的话 c0 是孤立的了

necomancer

2019-03-31 11:52:25 +08:00

嗯……根据这个做个邻接表然后 DFS ？非科班想的笨办法。P.S. 你的数据少一组 [c2, p2] 吧？

qqor

2019-03-31 22:00:49 +08:00 via Android

404 ？
原来我屏蔽这个网址了，哈！

rootzeal

2019-04-01 08:33:40 +08:00 via Android

@brainfxxk 对是这个意思有没有办法在分布式或者 sql 环境下解决这个问题

zdkk

2019-04-01 10:25:58 +08:00

@yswb c2 和 c0 少一个关系，不知道是题目这样设计，还是楼主疏忽

rootzeal

2019-04-01 10:36:44 +08:00 via Android

@zdkk 我得错😂