## Problem A social graph is represented as an undirected adjacency list. Given two users `src` and `dst`, find the shortest path between them and return the list of user IDs along that path (inclusive). If no path exists, return an empty list. ```python def friendship_path( friends: dict[str, list[str]], src: str, dst: str ) -> list[str]: ``` ## Example ``` friends = { "alice": ["bob", "carol"], "bob": ["alice", "dave"], "carol": ["alice"], "dave": ["bob"] } friendship_path(friends, "carol", "dave") -> ["carol", "alice", "bob", "dave"] ``` ## Follow-ups 1. How does BFS guarantee the shortest path here (vs. DFS)? 2. The graph has 500M edges (LinkedIn scale). What algorithmic approaches handle bidirectional BFS? 3. Return ALL shortest paths, not just one. 4. Extend to return the "degrees of separation" only, without the full path, for a large-scale system. How would you precompute this?

InterviewDB Question

Friendship Path - Shortest Mutual Connection Between Two Users

phone

Question Details

Problem A social graph is represented as an undirected adjacency list. Given two users src and dst, find the shortest path between them and return the list of user IDs along that path (inclusive). If no path exists, return an empty list. Example Foll…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding Onsite Phone

More from Amazon

Reddit 175 k remote offer or 300 k in Bay Area Reddit Done with 3 rounds of On-site Amazon SDE 1 interview , but no communication after that. What to do? Reddit Nned direction for future prepration. Reddit Have an Amazon. SDE1 interview in 4 days, need tips Reddit After many years in the industry, I still struggle with textbook definitions in interviews

← All Amazon questions Amazon Software Engineer Questions → All Graph Questions →