Breadth-First Search for Knowledge Graphs | Dataford Interview Questions

KPMG Clara can represent relationships between business concepts as a directed knowledge graph. Given an adjacency-list graph, a starting concept, and a target concept, return the shortest path from the start to the target using breadth-first search.

Formal Specification

Implement bfs_knowledge_path(graph, start, target).

graph is a dictionary where each key is a string node and its value is a list of directly connected string nodes.
Edges are directed and must be followed in the listed order.
start and target are strings. They may refer to nodes that have no outgoing-edge entry.
Return a list containing the nodes on the shortest path, including start and target.
Return [] when the target is unreachable.
If start == target, return [start].

Each node should be visited at most once, even when the graph contains cycles.

Constraints

1 <= number of nodes <= 10^5
0 <= number of directed edges <= 2 * 10^5
Node names are non-empty strings
The graph may contain cycles and disconnected components
Neighbor order must be respected when multiple shortest paths exist

Function Signature

def bfs_knowledge_path(graph, start, target):

Your question is Breadth-First Search for Knowledge Graphs. Start with the requirements in the Question tab.

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

Problem