InterviewDB
Question
Friend Chain - Shortest Social Connection Path Between Two Users
phone
Question Details
Problem
Given a social network represented as an adjacency list {user_id: [friend_ids]}, find the shortest chain of connections between two users start and end.
Return the path as a list of user IDs, or an empty list if no path exists.
python
def friend_chain(
network: dict, # {user_id: List[user_id]}
start: str,
end: str
) -> List[str]:
...
Example:
network = {
"Alice": ["Bob", "Carol"],
"Bob": ["Alice", "Dave"],
"Carol": ["Alice", "Eve"],
"Dave": ["Bob"],
"Eve": ["Carol", "Frank"],
"Frank": ["Eve"]
}
friend_chain(network, "Alice", "Frank") -> ["Alice", "Carol", "Eve", "Frank"]
Follow-ups
- What is the time and space complexity of BFS on a graph with V users and E friendships?
- How would you find the shortest path between all pairs of users efficiently?
- If the graph has 500M users (like a real social network), how do you scale this?
- How would you compute the "degrees of separation" distribution across the whole network?
Full Details
Problem
Given a social network represented as an adjacency list {user_id: [friend_ids]}, find the shortest chain of connections between two users start and end.
Return the path as a list of user IDs, or an empty list if no path exists.
python
def friend_chain(
network: dict, # {user_id: List[user_id]}
start: str,
end: str
) -> List[str]:
...
Example:
network = {
"Alice": ["Bob", "Carol"],
"Bob": ["Alice", "Dave"],
"Carol": ["Alice", "Eve"],
"Dave": ["Bob"],
"Eve": ["Carol", "Frank"],
"Frank": ["Eve"]
}
friend_chain(network, "Alice", "Frank") -> ["Alice", "Carol", "Eve", "Frank"]
Follow-ups
- What is the time and space complexity of BFS on a graph with V users and E friendships?
- How would you find the shortest path between all pairs of users efficiently?
- If the graph has 500M users (like a real social network), how do you scale this?
- How would you compute the "degrees of separation" distribution across the whole network?
Free preview. Unlock all Two Sigma questions →
About This Question
This is a reported interview question from a two sigma interview during the phone round.
It covers the following topics: Coding, Graph, Phone, Onsite .
More Two Sigma Interview Questions
1p3a
Two Sigma Quant Research Intern Onsite Interview Experience and Insights
1p3a
Two Sigma Quant Finance Intern Tech Phone Screen Interview Experience
1p3a
Twosigma QSE/SWE Interview Process for General Hiring
LeetCode
Two Sigma | Quantitative Software Engineer | Apr 2020 [Reject]
LeetCode
#43 Multiply Strings