Breadth-First Search Level Order | Dataford Interview Questions

Delta DIAView can represent relationships among industrial assets such as controllers, sensors, and gateways. Given this relationship graph and a starting asset, return all reachable assets grouped in breadth-first level order.

Formal Specification

Implement bfs_levels(graph, start). The input graph is a dictionary mapping each asset ID to a list of directly connected asset IDs. Treat edges as directed from each key to its listed neighbors. The start asset is guaranteed to exist in graph. Return a list of lists, where the first list contains start, and each subsequent list contains the assets at the corresponding shortest edge distance from start.

Visit each asset at most once. Preserve the order in which neighbors appear in the input lists. Assets that are not reachable from start must not appear in the result.

Constraints

1 <= number of assets <= 10^5
0 <= total number of directed edges <= 2 * 10^5
Asset IDs are unique hashable values
Every listed neighbor is a key in graph
Neighbor lists may contain repeated IDs or self-loops

Function Signature

def bfs_levels(graph, start):

Your question is Breadth-First Search Level Order. 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