Graph Traversal for Related Communities | Dataford Interview Questions

Given community->follower and follower->community maps, return all communities related to an input community (sharing followers); BFS.

Asked in the code screen stage.

Implement a function that takes a starting community and two maps, then returns every community reachable by repeatedly moving from a community to its followers, and from each follower to the communities they follow. Exclude the input community from the result. Return each related community once, in any order.

Function Input

start_community: the community to begin from
community_to_followers: dict mapping community id to a list of follower ids
follower_to_communities: dict mapping follower id to a list of community ids

Output

A list of related community ids

Constraints

1 <= number of communities + number of followers <= 10^5
A community may have zero or more followers
A follower may follow zero or more communities
The graph may contain cycles
Return each related community at most once

Function Signature

def related_communities(start_community, community_to_followers, follower_to_communities):

Your question is Graph Traversal for Related Communities. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem