Dependency Traversal Function | Dataford Interview Questions

Your question is Dependency Traversal Function. 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

Vanta control workflows can depend on other controls or prerequisite checks. Given a collection of control records and a desired control ID, return every transitive dependency in dependency-first order, followed by the desired ID itself.

Formal Specification

Implement get_dependency_order(records, desired_id).

records is a list of dictionaries. Each dictionary has a unique string id and a dependencies list containing string IDs.
Every dependency ID refers to another record in records.
desired_id is the ID of an existing record.
Return a list of IDs containing all records reachable from desired_id, with each ID appearing exactly once.
A dependency must appear before any record that depends on it.
If the reachable dependency graph contains a cycle, raise ValueError.

The input may contain records unrelated to desired_id; exclude them from the result.

Constraints

1 <= len(records) <= 10^5
Each record has a unique non-empty string ID
The total number of dependency references is at most 2 * 10^5
Every dependency ID refers to a record in records
The reachable dependency graph is acyclic for valid non-error cases

Function Signature

def get_dependency_order(records, desired_id):