FB 프로필 연결

Question

인터뷰에서 한 가지 문제에 대한 답을 찾으려고 노력했습니다. 그러나 아무 해결책도 얻지 않았다. 누구든지이 질문에서 나를 도울 수 있습니까? 여기에 문제가있다 설명 :

주어진 두 사람의 이름 A & B. 둘 다 FB에 존재한다는 것을 알고있다. 그들 사이에 어떤 연결이 있는지를 말해야합니다. 연결이 있으면 연결의 정확한 경로를 말해야합니다. 연결성이란 B가 A의 친구 인 C의 친구가 될 수 있음을 의미합니다. 이 방법으로 A는 & B 사이의 연결이며 경로는 A -> B -> C

Answer 1

Bidirectional search을 사용할 수 있습니다.

주요 아이디어 :

1. AGroup = {A}, {B = BGroup}.

   2.1은 아직 확장하지 않은 AGroup에서 모든 사람을 확장하고 AGroup에 결과를 삽입 :

2. 동안은 (AGroup, BGroup) = 하늘 세트를 교차.

   2.2 아직 확장하지 않은 BGroup의 모든 사용자를 확장하고 결과 BGroup을 삽입하십시오.

   2.3 AGroup 및 BGroup이 변경되지 않은 경우 "A와 B가 연결되지 않음"을 반환합니다.

3. AGroup과 BGroup의 사람을 나타냅니다. > ...-> S - -> ...-> B

이제 S A에서 경로 및 S.

반환 A와 B에서의 경로를 가지고있다.