Efficient Traversal of Complex Structures | Dataford Interview Questions

Bloomberg Terminal content can be organized as nested topic folders and instruments. Given the root of a tree and a target identifier, return the path from the root to the first matching node using an efficient traversal.

Each node is represented as a dictionary with an id string and an optional children list containing child nodes. The hierarchy is a tree, node identifiers are unique, and children must be searched from left to right. Return an empty list if the target does not exist.

Formal Specification

Implement find_path(root, target).

Input: root, a dictionary representing the root node, and target, a string identifier.
Output: A list of node identifiers from the root through the matching node, or [] when no match exists.
The search must stop as soon as the first matching node is found.

Constraints

1 <= number of nodes <= 10^5
Each node contains an id string and may contain zero or more children
Node identifiers are unique
The hierarchy is a valid tree

Function Signature

def find_path(root, target):

Your question is Efficient Traversal of Complex Structures. 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