Graph Traversal Implementation | Dataford Interview Questions

Your question is Graph Traversal Implementation. 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.

Problem

Guardian Life models dependencies between internal services as a directed graph. Given a starting service and a destination service, determine whether the destination is reachable by following one-way dependency edges.

Implement can_reach(graph, start, target) using breadth-first search or depth-first search. The graph is represented as an adjacency list, where each key is a service name and its value is a list of directly dependent services. Return true if target can be reached from start, including when both names are the same. Return false when no path exists.

Formal Specification

Input: graph, a dictionary mapping strings to lists of strings; start and target, service-name strings.
Output: A boolean indicating whether a directed path exists from start to target.
The graph may contain cycles, self-loops, disconnected services, and services that appear only as neighbors.

Constraints

1 <= number of services <= 10^5
0 <= number of directed edges <= 2 * 10^5
Service names are non-empty strings
The graph may contain cycles, self-loops, disconnected services, and repeated edges

Function Signature

def can_reach(graph, start, target):

Your question is Graph Traversal Implementation. 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.

Formal Specification

Input: graph, a dictionary mapping strings to lists of strings; start and target, service-name strings.
Output: A boolean indicating whether a directed path exists from start to target.
The graph may contain cycles, self-loops, disconnected services, and services that appear only as neighbors.

Constraints

1 <= number of services <= 10^5
0 <= number of directed edges <= 2 * 10^5
Service names are non-empty strings
The graph may contain cycles, self-loops, disconnected services, and repeated edges

Function Signature

def can_reach(graph, start, target):