f**********n 发帖数: 46 | 1 老中面试官,问了个这个题目:
Find all connected components in an undirected graph.
我尝试了DFS和BFS,不知道对不对,最后挂了。
大家有啥好解法? |
s********x 发帖数: 914 | 2 lintcode上有啊
【在 f**********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中面试官,问了个这个题目: : Find all connected components in an undirected graph. : 我尝试了DFS和BFS,不知道对不对,最后挂了。 : 大家有啥好解法?
|
f**********n 发帖数: 46 | 3 没刷那个,刷了leetcode。。。
【在 s********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中面试官,问了个这个题目: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题能挂,一定是沟通有问题。不能从面试官那就挑毛病,一定要找自己的问题。现在 : 是弱势,没办法。 : 比如这题,dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完 : code了再说。要根据面试官的讨论反馈决定写哪个。 : 同时关键字一个hashset也要主动提出来。如果面试官想放水,不用adjancy list来描 : 述图,都是有可能的。 : 说的push一点,最好还是你自己带节奏,不是面试官带节奏。祝好运
|
f**********n 发帖数: 46 | 7 面试官说了input是一堆edge,没有node,要是用node我就很轻松做出来了。
which
【在 s********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题能挂,一定是沟通有问题。不能从面试官那就挑毛病,一定要找自己的问题。现在 : 是弱势,没办法。 : 比如这题,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题能挂,一定是沟通有问题。不能从面试官那就挑毛病,一定要找自己的问题。现在 : 是弱势,没办法。 : 比如这题,dfs和bfs都是正确的。但什么时候用哪个。你得第一时间说。千万不能写完 : code了再说。要根据面试官的讨论反馈决定写哪个。 : 同时关键字一个hashset也要主动提出来。如果面试官想放水,不用adjancy list来描 : 述图,都是有可能的。 : 说的push一点,最好还是你自己带节奏,不是面试官带节奏。祝好运
|
|
|
j*****8 发帖数: 3635 | 11 老中面老中有必要这么认认真真的吗
【在 S**********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就算你不是非google不去,也得装出一副非google不去的态度。 : 就算你有别的很好的offer在手,面试任何其他家的时候也得表现出非你家不去的状态 : 。这是面试的基本职业表现。否则别人凭什么去beat你已有的offer呢。别人为什么不 : 能也像你的思路一样: 我不是非招你不可呢? : 说面试的是弱势,是因为除了沉着冷静的解题之外,还要讨好面试官额外加分。真正的 : behavioral,都是在解题的同时考察的。考察依据只有一条,面试官爽不爽你。 : 这道题,你要是有时间,搜一下union-find
|
b**********5 发帖数: 7881 | 12 twitter, FB面我的老中, 可认真了。。 我还他妈的胸大屁股大的。。 就是脸难看
。。。
【在 j*****8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中面老中有必要这么认认真真的吗
|
j*****8 发帖数: 3635 | 13 这个好说
去韩国整整估计你就成面霸了
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : twitter, FB面我的老中, 可认真了。。 我还他妈的胸大屁股大的。。 就是脸难看 : 。。。
|
c*******t 发帖数: 123 | 14 兄弟,题还是没刷好啊。
没关系,会有大offer的。
这么简单的题,五分钟秒掉。
union find听说过没?去看看普林斯顿那本算法书。
【在 f**********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中面试官,问了个这个题目: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 兄弟,题还是没刷好啊。 : 没关系,会有大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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中面试官,问了个这个题目: : Find all connected components in an undirected graph. : 我尝试了DFS和BFS,不知道对不对,最后挂了。 : 大家有啥好解法?
|
|
|
r****7 发帖数: 2282 | 21 这一题为毛要用union find?就bfs/dfs就行了
【在 c*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 兄弟,题还是没刷好啊。 : 没关系,会有大offer的。 : 这么简单的题,五分钟秒掉。 : union find听说过没?去看看普林斯顿那本算法书。
|
b**********5 发帖数: 7881 | 22 为什么读了你的帖子, 总有一种操你妈, 操你老婆, 操你全家的感觉?
【在 S**********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主第一次发帖并没有把题目描述清楚,给的信息量也很少,只说了是graph,然后自 : 己给出的是dfs和bfs两种针对用adjcency list或者adjacency matrix的标准解答。看 : 似答得中规中矩,应该给过的。 : 说的hashset,和楼主说的Boolean array是一回事。是用数学来映射点时的简化。 : 然后楼主说图是用edges来描述。那就是另外一个问题,用edges复原构造图的问题了。 : 这种题没什么好说的,背union find答案应该都给过。 : 这两种问题都是应该直接背答案,面试官接下来直接给过的。 : 难题是要根据题目构造图的点和边,进而构造一个图,然后用现有的关于图的算法得到 : 答案。构造图的过程没法背答案,每道题都不一样。但是你一旦发现了可以构造一张图 : ,接下来是希望你直接默写代码模板,然后面试官和你皆大欢喜的
|
b**********5 发帖数: 7881 | 23 主要是有一堆傻逼, 但自以为很牛的中国面试人。。。 像stonecoldman那样的傻逼
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这一题为毛要用union find?就bfs/dfs就行了
|
b**********5 发帖数: 7881 | 24 你的code, 总觉得不对啊。 就用二个node, 然后有一个edge connect这两个node,
你的好像output 2?
【在 f**********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中面试官,问了个这个题目: : Find all connected components in an undirected graph. : 我尝试了DFS和BFS,不知道对不对,最后挂了。 : 大家有啥好解法?
|
U***A 发帖数: 849 | 25 哈哈,挺会自嘲的
祝好运
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : twitter, FB面我的老中, 可认真了。。 我还他妈的胸大屁股大的。。 就是脸难看 : 。。。
|
f**********n 发帖数: 46 | 26 赞!我那里失误了。已经改好了。
【在 z********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后在统计cluster的时候应该是指向自己的才是该cluster的root,所以条件应该是 : if(clusters[i] == -1) : cluster_no ++;
|
f**********n 发帖数: 46 | 27 我用了DFS,面试官没给过,感觉就是想考union find。。呵呵。
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这一题为毛要用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我刚刚过了一遍,输出是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我用了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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题用DFS或BFS会比union find更快吧? : 我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV). : 是这样吗?
|
f**********n 发帖数: 46 | 35 这题已经进leetcode了。不知道是不是看我的帖子。哈哈
【在 n*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题用DFS或BFS会比union find更快吧? : 我认为DFS和BFS的time complexity会是O(E), 而Union-find会是O(ElogV). : 是这样吗?
|