At Meta, services such as News Feed, Ads Delivery, and Graph API can depend on other internal systems. Given a directed graph of system dependencies and a starting system, implement breadth-first search (BFS) to return the order in which systems are discovered, grouped by dependency distance.
A directed edge A -> B means system A depends directly on system B. Starting from start, traverse all reachable systems using BFS. Return two results:
start.graph: a dictionary mapping each system name (string) to a list of directly dependent systems (list of strings)start: a string representing the starting systemorder: list of strings in BFS visitation orderlevels: list of lists of strings, grouped by BFS depthExample 1
Input: graph = {"Feed": ["GraphAPI", "Cache"], "GraphAPI": ["Storage"], "Cache": ["Storage", "Metrics"], "Storage": [], "Metrics": []}, start = "Feed"
Output: {"order": ["Feed", "GraphAPI", "Cache", "Storage", "Metrics"], "levels": [["Feed"], ["GraphAPI", "Cache"], ["Storage", "Metrics"]]}
Explanation: Feed is visited first, then its direct dependencies, then dependencies two hops away.
Example 2
Input: graph = {"Ads": ["Ranking", "Logging"], "Ranking": ["Models"], "Logging": [], "Models": []}, start = "Logging"
Output: {"order": ["Logging"], "levels": [["Logging"]]}
Explanation: Logging has no outgoing dependencies, so traversal stops immediately.
1 <= len(graph) <= 10^4start is guaranteed to exist in graph