Monday, September 24, 2012
You have N computers and [Ca, Cb] means a is connected to b and this connectivity is symmetric and transitive. then write a program which checks that all computers are interconnected and talk two each other
I Believe there are multiple way to solve this problem
1. Here is my approach since graph is connected there will be path from each source to destination vertex , isn't it ?
so we can simply run a dfs or bfs for all computers to check if all such path exist , finally we can return & of all operation that means all computer are inter connected and can talk to each other .
PS.Since graph is undirected if there exist path from u to v then vice-verse also true so we wont calculate it again.
Labels:Data
Adobe Question
,
Google Interview
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment