Service Dependency Graph Traversal

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Service Dependency Graph Traversal. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

Given a directed graph of service dependencies represented as a dictionary graph, where each key is a service name and its value is a list of dependent services, implement a traversal starting from start_service. Return the services visited in traversal order using either breadth-first search (BFS) or depth-first search (DFS), based on a method parameter equal to "bfs" or "dfs". If a service appears multiple times through different paths, visit it only once.

Constraints

1 <= number of services <= 10^5
0 <= total dependencies <= 2 * 10^5
Service names are non-empty strings
method is either "bfs" or "dfs"

Function Signature

def traverse_dependencies(graph, start_service, method):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output