f**********n
发帖数: 46 | 1 老中面试官，问了个这个题目：
Find all connected components in an undirected graph.
我尝试了DFS和BFS，不知道对不对，最后挂了。
大家有啥好解法？ |
s********x
发帖数: 914 | 2 lintcode上有啊
【在 f**********n 的大作中提到】
: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？
|
f**********n
发帖数: 46 | 3 没刷那个，刷了leetcode。。。
【在 s********x 的大作中提到】
: lintcode上有啊
|
s********x
发帖数: 914 | 4 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 <- F
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，不知道对不对，最后挂了。
: 大家有啥好解法？
|
S**********n
发帖数: 250 | 5 这题能挂，一定是沟通有问题。不能从面试官那就挑毛病，一定要找自己的问题。现在
是弱势，没办法。
比如这题，dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完
code了再说。要根据面试官的讨论反馈决定写哪个。
同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
述图，都是有可能的。
说的push一点，最好还是你自己带节奏，不是面试官带节奏。祝好运 |
h******6
发帖数: 2697 | 6
你就是那个面试官吧？
【在 S**********n 的大作中提到】
: 这题能挂，一定是沟通有问题。不能从面试官那就挑毛病，一定要找自己的问题。现在
: 是弱势，没办法。
: 比如这题，dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完
: code了再说。要根据面试官的讨论反馈决定写哪个。
: 同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
: 述图，都是有可能的。
: 说的push一点，最好还是你自己带节奏，不是面试官带节奏。祝好运
|
f**********n
发帖数: 46 | 7 面试官说了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**********n
发帖数: 46 | 8 我没有挑面试官的问题吧？
我当时问了面试官input是什么样的，面试官说一堆edges，DFS或者BFS走的话每一步都
要遍历现有没走过的edge，反正没有直接给node简洁。
我记得我最后写了个DFS的解法，但也提到了图太大容易栈溢出，用BFS就没有这个问题。
hashset的话我用了一个boolean array来存visited的信息。
不过确实略紧张，状态不是最好。
至于说弱势，我并不觉得。。我觉得大部分换工作的人应该跟我一样，不是非Google不
去，只是试试这个机会罢了。
只是感叹一下，面试了一堆公司，大的小的都有，面试官烙印小白难的简单的都过了电
面拿到onsite了，onsite的都拿到offer了，唯一一个中国人面的却挂了。
多谢祝福。
【在 S**********n 的大作中提到】
: 这题能挂，一定是沟通有问题。不能从面试官那就挑毛病，一定要找自己的问题。现在
: 是弱势，没办法。
: 比如这题，dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完
: code了再说。要根据面试官的讨论反馈决定写哪个。
: 同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
: 述图，都是有可能的。
: 说的push一点，最好还是你自己带节奏，不是面试官带节奏。祝好运
|
S**********n
发帖数: 250 | 9 就算你不是非google不去，也得装出一副非google不去的态度。
就算你有别的很好的offer在手，面试任何其他家的时候也得表现出非你家不去的状态
。这是面试的基本职业表现。否则别人凭什么去beat你已有的offer呢。别人为什么不
能也像你的思路一样: 我不是非招你不可呢？
说面试的是弱势，是因为除了沉着冷静的解题之外，还要讨好面试官额外加分。真正的
behavioral，都是在解题的同时考察的。考察依据只有一条，面试官爽不爽你。
这道题，你要是有时间，搜一下union-find |
b**********5
发帖数: 7881 | 10 什么时候用DFS， 什么时候用BFS呢？
【在 S**********n 的大作中提到】
: 这题能挂，一定是沟通有问题。不能从面试官那就挑毛病，一定要找自己的问题。现在
: 是弱势，没办法。
: 比如这题，dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完
: code了再说。要根据面试官的讨论反馈决定写哪个。
: 同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
: 述图，都是有可能的。
: 说的push一点，最好还是你自己带节奏，不是面试官带节奏。祝好运
|
|
|
j*****8
发帖数: 3635 | 11 老中面老中有必要这么认认真真的吗
【在 S**********n 的大作中提到】
: 就算你不是非google不去，也得装出一副非google不去的态度。
: 就算你有别的很好的offer在手，面试任何其他家的时候也得表现出非你家不去的状态
: 。这是面试的基本职业表现。否则别人凭什么去beat你已有的offer呢。别人为什么不
: 能也像你的思路一样: 我不是非招你不可呢？
: 说面试的是弱势，是因为除了沉着冷静的解题之外，还要讨好面试官额外加分。真正的
: behavioral，都是在解题的同时考察的。考察依据只有一条，面试官爽不爽你。
: 这道题，你要是有时间，搜一下union-find
|
b**********5
发帖数: 7881 | 12 twitter， FB面我的老中， 可认真了。。 我还他妈的胸大屁股大的。。 就是脸难看
。。。
【在 j*****8 的大作中提到】
: 老中面老中有必要这么认认真真的吗
|
j*****8
发帖数: 3635 | 13 这个好说
去韩国整整估计你就成面霸了
【在 b**********5 的大作中提到】
: twitter， FB面我的老中， 可认真了。。 我还他妈的胸大屁股大的。。 就是脸难看
: 。。。
|
c*******t
发帖数: 123 | 14 兄弟，题还是没刷好啊。
没关系，会有大offer的。
这么简单的题，五分钟秒掉。
union find听说过没？去看看普林斯顿那本算法书。
【在 f**********n 的大作中提到】
: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？
|
d*******s
发帖数: 65 | 15 这题为什么没人提topological sort呢 |
r*******g
发帖数: 1335 | 16 union find, 维护每个节点的parent |
c*****m
发帖数: 271 | 17 不知道楼上们讨论的union find怎么做法？如何建立parent信息？
topological sort如果有环做不了吧？
"同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
述图，都是有可能的。"=>hashset是用来访问已经访问过的节点的吧？ |
f**********n
发帖数: 46 | 18 了然了。就是一个知识点遗漏了。多谢指点！
【在 c*******t 的大作中提到】
: 兄弟，题还是没刷好啊。
: 没关系，会有大offer的。
: 这么简单的题，五分钟秒掉。
: union find听说过没？去看看普林斯顿那本算法书。
|
S**********n
发帖数: 250 | 19 楼主第一次发帖并没有把题目描述清楚，给的信息量也很少，只说了是graph，然后自
己给出的是dfs和bfs两种针对用adjcency list或者adjacency matrix的标准解答。看
似答得中规中矩，应该给过的。
说的hashset，和楼主说的Boolean array是一回事。是用数学来映射点时的简化。
然后楼主说图是用edges来描述。那就是另外一个问题，用edges复原构造图的问题了。
这种题没什么好说的，背union find答案应该都给过。
这两种问题都是应该直接背答案，面试官接下来直接给过的。
难题是要根据题目构造图的点和边，进而构造一个图，然后用现有的关于图的算法得到
答案。构造图的过程没法背答案，每道题都不一样。但是你一旦发现了可以构造一张图
，接下来是希望你直接默写代码模板，然后面试官和你皆大欢喜的 |
z********y
发帖数: 17 | 20 最后在统计cluster的时候应该是指向自己的才是该cluster的root，所以条件应该是
if（clusters[i] == -1）
cluster_no ++;
【在 f**********n 的大作中提到】
: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？
|
|
|
r****7
发帖数: 2282 | 21 这一题为毛要用union find？就bfs/dfs就行了
【在 c*******t 的大作中提到】
: 兄弟，题还是没刷好啊。
: 没关系，会有大offer的。
: 这么简单的题，五分钟秒掉。
: union find听说过没？去看看普林斯顿那本算法书。
|
b**********5
发帖数: 7881 | 22 为什么读了你的帖子， 总有一种操你妈， 操你老婆， 操你全家的感觉？
【在 S**********n 的大作中提到】
: 楼主第一次发帖并没有把题目描述清楚，给的信息量也很少，只说了是graph，然后自
: 己给出的是dfs和bfs两种针对用adjcency list或者adjacency matrix的标准解答。看
: 似答得中规中矩，应该给过的。
: 说的hashset，和楼主说的Boolean array是一回事。是用数学来映射点时的简化。
: 然后楼主说图是用edges来描述。那就是另外一个问题，用edges复原构造图的问题了。
: 这种题没什么好说的，背union find答案应该都给过。
: 这两种问题都是应该直接背答案，面试官接下来直接给过的。
: 难题是要根据题目构造图的点和边，进而构造一个图，然后用现有的关于图的算法得到
: 答案。构造图的过程没法背答案，每道题都不一样。但是你一旦发现了可以构造一张图
: ，接下来是希望你直接默写代码模板，然后面试官和你皆大欢喜的
|
b**********5
发帖数: 7881 | 23 主要是有一堆傻逼， 但自以为很牛的中国面试人。。。 像stonecoldman那样的傻逼
【在 r****7 的大作中提到】
: 这一题为毛要用union find？就bfs/dfs就行了
|
b**********5
发帖数: 7881 | 24 你的code， 总觉得不对啊。 就用二个node， 然后有一个edge connect这两个node，
你的好像output 2？
【在 f**********n 的大作中提到】
: 老中面试官，问了个这个题目：
: Find all connected components in an undirected graph.
: 我尝试了DFS和BFS，不知道对不对，最后挂了。
: 大家有啥好解法？
|
U***A
发帖数: 849 | 25 哈哈，挺会自嘲的
祝好运
【在 b**********5 的大作中提到】
: twitter， FB面我的老中， 可认真了。。 我还他妈的胸大屁股大的。。 就是脸难看
: 。。。
|
f**********n
发帖数: 46 | 26 赞！我那里失误了。已经改好了。
【在 z********y 的大作中提到】
: 最后在统计cluster的时候应该是指向自己的才是该cluster的root，所以条件应该是
: if（clusters[i] == -1）
: cluster_no ++;
|
f**********n
发帖数: 46 | 27 我用了DFS，面试官没给过，感觉就是想考union find。。呵呵。
【在 r****7 的大作中提到】
: 这一题为毛要用union find？就bfs/dfs就行了
|
f**********n
发帖数: 46 | 28 我刚刚过了一遍，输出是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**********5
发帖数: 7881 | 29 不对吧。你是在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**********n
发帖数: 250 | 30 你都被这么多面试操了这么多次了，然后只能蒙着个脸在网上用嘴巴操人。你怎么就不
想想办法让自己现实中少挨操呢。至少不被操的那么狠也行啊。
这道题，楼主是表现的极差。从他的题目描述就看得出他的准备多不到位。但也没什么
啊，他在网上被我酸几句，至少这辈子不会再载在这道题上。
至于操牛肉，还是让牛肉用嘴操，好像怎么都不吃亏。
：主要是有一堆傻逼， 但自以为很牛的中国面试人。。。 像stonecoldman那样的傻逼
：【 在 raul07 (utopian) 的大作中提到: 】 |
|
|
S**********n
发帖数: 250 | 31 你要舔，我肯定是拦不住你的。
古今中外都没人在骂人的时候往这个方向想的。你能脱口而出，一定在你妈屁眼那实践
到心口和一了吧
：还是回家舔你妈的AIDS infested屁眼去吧
： |
r****7
发帖数: 2282 | 32 OK，如果给的只是edge，是可以用类似生成树的算法
【在 f**********n 的大作中提到】
: 我用了DFS，面试官没给过，感觉就是想考union find。。呵呵。
|
n*******e
发帖数: 37 | 33 这题用DFS或BFS会比union find更快吧?
我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV).
是这样吗? |
r*****s
发帖数: 1815 | 34 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**********n
发帖数: 46 | 35 这题已经进leetcode了。不知道是不是看我的帖子。哈哈
【在 n*******e 的大作中提到】
: 这题用DFS或BFS会比union find更快吧?
: 我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV).
: 是这样吗?
|
