预祝俺的MU明天冲破８号阻力，站到8.2号小山头。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

预祝俺的MU明天冲破８号阻力，站到8.2号小山头。

预祝俺的MU明天冲破８号阻力，站到8.2号小山头。# Stock

f*n2010-10-28 07:10

1 楼

老中面试官，问了个这个题目：
Find all connected components in an undirected graph.
我尝试了DFS和BFS，不知道对不对，最后挂了。
大家有啥好解法？

g*72010-10-28 07:10

2 楼

加油。。。。。。。

s*x2010-10-28 07:10

3 楼

lintcode上有啊

【在 f**********n 的大作中提到】

: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？

h*r2010-10-28 07:10

4 楼

I have only 4 calls @0.25 and just support you. I hope I can got some from
mu to buy some Hallowen stuff for my kids. If it is not double, I will let
it rot away.

【在 g**********7 的大作中提到】

: 加油。。。。。。。

f*n2010-10-28 07:10

5 楼

没刷那个，刷了leetcode。。。

【在 s********x 的大作中提到】

: lintcode上有啊

S*t2010-10-28 07:10

6 楼

做硬件的都涨了。。。

s*x2010-10-28 07:10

7 楼

Find the Connected Component in the Undirected Graph
Find the number connected component in the undirected graph. Each node in
the graph contains a label and a list of its neighbors. (a connected
component (or just component) of an undirected graph is a subgraph in which
any two vertices are connected to each other by paths, and which is
connected to no additional vertices in the supergraph.)
Example
Given graph:
A------B C
| |
| |
| |
| |
D E
Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B
,D}, {C,E}
Find the Weak Connected Component in the Directed Graph
Find the number Weak Connected Component in the directed graph. Each node in
the graph contains a label and a list of its neighbors. (a connected set of
a directed graph is a subgraph in which any two vertices are connected by
direct edge path.)
Example
Given graph:
A----->B C
| |
| |
| |
v v
->D E Return {A,B,D}, {C,E,F}. Since there are two connected component which are {
A,B,D} and {C,E,F}
Note
Sort the element in the set in increasing order

【在 f**********n 的大作中提到】

: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？

g*72010-10-28 07:10

8 楼

I have 30, 1/4 of my call holdings. MU will make it!

【在 h********r 的大作中提到】

: I have only 4 calls @0.25 and just support you. I hope I can got some from
: mu to buy some Hallowen stuff for my kids. If it is not double, I will let
: it rot away.

S*n2010-10-28 07:10

9 楼

这题能挂，一定是沟通有问题。不能从面试官那就挑毛病，一定要找自己的问题。现在
是弱势，没办法。
比如这题，dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完
code了再说。要根据面试官的讨论反馈决定写哪个。
同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
述图，都是有可能的。
说的push一点，最好还是你自己带节奏，不是面试官带节奏。祝好运

g*72010-10-28 07:10

10 楼

yeah!希望能站稳啊，呵呵

【在 g**********7 的大作中提到】

: 加油。。。。。。。

h*62010-10-28 07:10

11 楼

你就是那个面试官吧？

【在 S**********n 的大作中提到】

: 这题能挂，一定是沟通有问题。不能从面试官那就挑毛病，一定要找自己的问题。现在
: 是弱势，没办法。
: 比如这题，dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完
: code了再说。要根据面试官的讨论反馈决定写哪个。
: 同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
: 述图，都是有可能的。
: 说的push一点，最好还是你自己带节奏，不是面试官带节奏。祝好运

f*n2010-10-28 07:10

12 楼

面试官说了input是一堆edge，没有node，要是用node我就很轻松做出来了。

which

【在 s********x 的大作中提到】

: Find the Connected Component in the Undirected Graph
: Find the number connected component in the undirected graph. Each node in
: the graph contains a label and a list of its neighbors. (a connected
: component (or just component) of an undirected graph is a subgraph in which
: any two vertices are connected to each other by paths, and which is
: connected to no additional vertices in the supergraph.)
: Example
: Given graph:
: A------B C
: | |

f*n2010-10-28 07:10

13 楼

我没有挑面试官的问题吧？
我当时问了面试官input是什么样的，面试官说一堆edges，DFS或者BFS走的话每一步都
要遍历现有没走过的edge，反正没有直接给node简洁。
我记得我最后写了个DFS的解法，但也提到了图太大容易栈溢出，用BFS就没有这个问题。
hashset的话我用了一个boolean array来存visited的信息。
不过确实略紧张，状态不是最好。
至于说弱势，我并不觉得。。我觉得大部分换工作的人应该跟我一样，不是非Google不
去，只是试试这个机会罢了。
只是感叹一下，面试了一堆公司，大的小的都有，面试官烙印小白难的简单的都过了电
面拿到onsite了，onsite的都拿到offer了，唯一一个中国人面的却挂了。
多谢祝福。

【在 S**********n 的大作中提到】

S*n2010-10-28 07:10

14 楼

就算你不是非google不去，也得装出一副非google不去的态度。
就算你有别的很好的offer在手，面试任何其他家的时候也得表现出非你家不去的状态
。这是面试的基本职业表现。否则别人凭什么去beat你已有的offer呢。别人为什么不
能也像你的思路一样: 我不是非招你不可呢？
说面试的是弱势，是因为除了沉着冷静的解题之外，还要讨好面试官额外加分。真正的
behavioral，都是在解题的同时考察的。考察依据只有一条，面试官爽不爽你。
这道题，你要是有时间，搜一下union-find

b*52010-10-28 07:10

15 楼

什么时候用DFS，什么时候用BFS呢？

【在 S**********n 的大作中提到】

j*82010-10-28 07:10

16 楼

老中面老中有必要这么认认真真的吗

【在 S**********n 的大作中提到】

: 就算你不是非google不去，也得装出一副非google不去的态度。
: 就算你有别的很好的offer在手，面试任何其他家的时候也得表现出非你家不去的状态
: 。这是面试的基本职业表现。否则别人凭什么去beat你已有的offer呢。别人为什么不
: 能也像你的思路一样: 我不是非招你不可呢？
: 说面试的是弱势，是因为除了沉着冷静的解题之外，还要讨好面试官额外加分。真正的
: behavioral，都是在解题的同时考察的。考察依据只有一条，面试官爽不爽你。
: 这道题，你要是有时间，搜一下union-find

b*52010-10-28 07:10

17 楼

twitter， FB面我的老中，可认真了。。我还他妈的胸大屁股大的。。就是脸难看
。。。

【在 j*****8 的大作中提到】

: 老中面老中有必要这么认认真真的吗

j*82010-10-28 07:10

18 楼

这个好说
去韩国整整估计你就成面霸了

【在 b**********5 的大作中提到】

: twitter， FB面我的老中，可认真了。。我还他妈的胸大屁股大的。。就是脸难看
: 。。。

c*t2010-10-28 07:10

19 楼

兄弟，题还是没刷好啊。
没关系，会有大offer的。
这么简单的题，五分钟秒掉。
union find听说过没？去看看普林斯顿那本算法书。

【在 f**********n 的大作中提到】

: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？

d*s2010-10-28 07:10

20 楼

这题为什么没人提topological sort呢

r*g2010-10-28 07:10

21 楼

union find, 维护每个节点的parent

c*m2010-10-28 07:10

22 楼

不知道楼上们讨论的union find怎么做法？如何建立parent信息？
topological sort如果有环做不了吧？
"同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
述图，都是有可能的。"=>hashset是用来访问已经访问过的节点的吧？

f*n2010-10-28 07:10

23 楼

了然了。就是一个知识点遗漏了。多谢指点！

【在 c*******t 的大作中提到】

: 兄弟，题还是没刷好啊。
: 没关系，会有大offer的。
: 这么简单的题，五分钟秒掉。
: union find听说过没？去看看普林斯顿那本算法书。

S*n2010-10-28 07:10

24 楼

楼主第一次发帖并没有把题目描述清楚，给的信息量也很少，只说了是graph，然后自
己给出的是dfs和bfs两种针对用adjcency list或者adjacency matrix的标准解答。看
似答得中规中矩，应该给过的。
说的hashset，和楼主说的Boolean array是一回事。是用数学来映射点时的简化。
然后楼主说图是用edges来描述。那就是另外一个问题，用edges复原构造图的问题了。
这种题没什么好说的，背union find答案应该都给过。
这两种问题都是应该直接背答案，面试官接下来直接给过的。
难题是要根据题目构造图的点和边，进而构造一个图，然后用现有的关于图的算法得到
答案。构造图的过程没法背答案，每道题都不一样。但是你一旦发现了可以构造一张图
，接下来是希望你直接默写代码模板，然后面试官和你皆大欢喜的

z*y2010-10-28 07:10

25 楼

最后在统计cluster的时候应该是指向自己的才是该cluster的root，所以条件应该是
if（clusters[i] == -1）
cluster_no ++;

【在 f**********n 的大作中提到】

: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？

r*72010-10-28 07:10

26 楼

这一题为毛要用union find？就bfs/dfs就行了

【在 c*******t 的大作中提到】

: 兄弟，题还是没刷好啊。
: 没关系，会有大offer的。
: 这么简单的题，五分钟秒掉。
: union find听说过没？去看看普林斯顿那本算法书。

b*52010-10-28 07:10

27 楼

为什么读了你的帖子，总有一种操你妈，操你老婆，操你全家的感觉？

【在 S**********n 的大作中提到】

: 楼主第一次发帖并没有把题目描述清楚，给的信息量也很少，只说了是graph，然后自
: 己给出的是dfs和bfs两种针对用adjcency list或者adjacency matrix的标准解答。看
: 似答得中规中矩，应该给过的。
: 说的hashset，和楼主说的Boolean array是一回事。是用数学来映射点时的简化。
: 然后楼主说图是用edges来描述。那就是另外一个问题，用edges复原构造图的问题了。
: 这种题没什么好说的，背union find答案应该都给过。
: 这两种问题都是应该直接背答案，面试官接下来直接给过的。
: 难题是要根据题目构造图的点和边，进而构造一个图，然后用现有的关于图的算法得到
: 答案。构造图的过程没法背答案，每道题都不一样。但是你一旦发现了可以构造一张图
: ，接下来是希望你直接默写代码模板，然后面试官和你皆大欢喜的

b*52010-10-28 07:10

28 楼

主要是有一堆傻逼，但自以为很牛的中国面试人。。。像stonecoldman那样的傻逼

【在 r****7 的大作中提到】

: 这一题为毛要用union find？就bfs/dfs就行了

b*52010-10-28 07:10

29 楼

你的code，总觉得不对啊。就用二个node，然后有一个edge connect这两个node，
你的好像output 2？

【在 f**********n 的大作中提到】

: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？

U*A2010-10-28 07:10

30 楼

哈哈，挺会自嘲的
祝好运

【在 b**********5 的大作中提到】

: twitter， FB面我的老中，可认真了。。我还他妈的胸大屁股大的。。就是脸难看
: 。。。

f*n2010-10-28 07:10

31 楼

赞！我那里失误了。已经改好了。

【在 z********y 的大作中提到】

: 最后在统计cluster的时候应该是指向自己的才是该cluster的root，所以条件应该是
: if（clusters[i] == -1）
: cluster_no ++;

f*n2010-10-28 07:10

32 楼

我用了DFS，面试官没给过，感觉就是想考union find。。呵呵。

【在 r****7 的大作中提到】

: 这一题为毛要用union find？就bfs/dfs就行了

f*n2010-10-28 07:10

33 楼

我刚刚过了一遍，输出是1诶。
假设: n=2
edges = [[0, 1]]
clusters数组刚刚开始是
[-1, -1]
跑完union后变成
[1, -1]
扫描一遍，cluster_no变成1。
因为 if (edges.length < n-1) 不满足，直接返回1。

，

【在 b**********5 的大作中提到】

: 你的code，总觉得不对啊。就用二个node，然后有一个edge connect这两个node，
: 你的好像output 2？

b*52010-10-28 07:10

34 楼

不对吧。你是在IDE里面跑的？
一开始cluster是 [-1,-1],
两个find后是[0,1]
union后是[1,1]
Anyways, the purpose of union is to set the corresponding index in cluster
to the same Number

【在 f**********n 的大作中提到】

: 我刚刚过了一遍，输出是1诶。
: 假设: n=2
: edges = [[0, 1]]
: clusters数组刚刚开始是
: [-1, -1]
: 跑完union后变成
: [1, -1]
: 扫描一遍，cluster_no变成1。
: 因为 if (edges.length < n-1) 不满足，直接返回1。
:

S*n2010-10-28 07:10

35 楼

你都被这么多面试操了这么多次了，然后只能蒙着个脸在网上用嘴巴操人。你怎么就不
想想办法让自己现实中少挨操呢。至少不被操的那么狠也行啊。
这道题，楼主是表现的极差。从他的题目描述就看得出他的准备多不到位。但也没什么
啊，他在网上被我酸几句，至少这辈子不会再载在这道题上。
至于操牛肉，还是让牛肉用嘴操，好像怎么都不吃亏。

：主要是有一堆傻逼，但自以为很牛的中国面试人。。。像stonecoldman那样的傻逼
：【在 raul07 (utopian) 的大作中提到: 】

S*n2010-10-28 07:10

36 楼

你要舔，我肯定是拦不住你的。
古今中外都没人在骂人的时候往这个方向想的。你能脱口而出，一定在你妈屁眼那实践
到心口和一了吧

：还是回家舔你妈的AIDS infested屁眼去吧
：

r*72010-10-28 07:10

37 楼

OK，如果给的只是edge，是可以用类似生成树的算法

【在 f**********n 的大作中提到】

: 我用了DFS，面试官没给过，感觉就是想考union find。。呵呵。

n*e2010-10-28 07:10

38 楼

这题用DFS或BFS会比union find更快吧?
我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV).
是这样吗?

r*s2010-10-28 07:10

39 楼

Union-Find is O(alpha(E)*E).
the process is
foreach edge in edges:
union(edge.source, edge.target) //undirected... you can name whatever..
The complexity of union is not O(1) but O(alpha) which grows very slowly.
Comparing with DFS/BFS it might actually have performance advantage because
of compact implementation (implies smaller "constant" multiplier).

【在 n*******e 的大作中提到】

: 这题用DFS或BFS会比union find更快吧?
: 我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV).
: 是这样吗?

f*n2010-10-28 07:10

40 楼

这题已经进leetcode了。不知道是不是看我的帖子。哈哈

【在 n*******e 的大作中提到】

: 这题用DFS或BFS会比union find更快吧?
: 我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV).
: 是这样吗?