问道G题(3)# JobHunting - 待字闺中
s*n
1 楼
This is an old G onsite question about one year back.
Find a connection between two people if there is one, or return false.
Everyone has father and mother and the connection means if there are any
common relatives.
My idea is as following:
The relative social network should be represented as graphs instead of
binary trees. One way to solve this problem is to use BFS. Specifically, we
can do BFS for person1 and person2 for their ancestors/descendants
simultaneously. We can use a hashtable to record every ancestor/descendant
that find along the BFS. If a common ancestor/descendant is found or person1
/person2 is found to be person2/person1’s ancestor/descendant, then they
have a connection. If they do not have any common ancestor/descendant, then
return false.
I was wondering if there is any better solution?
Find a connection between two people if there is one, or return false.
Everyone has father and mother and the connection means if there are any
common relatives.
My idea is as following:
The relative social network should be represented as graphs instead of
binary trees. One way to solve this problem is to use BFS. Specifically, we
can do BFS for person1 and person2 for their ancestors/descendants
simultaneously. We can use a hashtable to record every ancestor/descendant
that find along the BFS. If a common ancestor/descendant is found or person1
/person2 is found to be person2/person1’s ancestor/descendant, then they
have a connection. If they do not have any common ancestor/descendant, then
return false.
I was wondering if there is any better solution?