Graph Traversal DSA | Dataford Interview Questions

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

Duolingo models prerequisite relationships between lessons as a directed graph. Given the graph, a starting lesson, and a target lesson, return the shortest valid prerequisite path from start to target.

Formal Specification

Implement shortest_lesson_path(lessons, start, target), where:

lessons is a dictionary mapping each lesson ID to a list of lesson IDs that can be taken next.
start and target are strings representing lesson IDs.
Return a list containing the lesson IDs on the shortest path, including both start and target.
Return [] if the target cannot be reached from the start.
If start == target, return [start].

Use the number of directed edges as the path length. The graph may contain cycles, and a lesson may have multiple outgoing edges. You may assume every referenced lesson ID is present as a key in lessons.

Constraints

1 <= len(lessons) <= 10^5
The total number of directed edges is at most 2 * 10^5
Lesson IDs are non-empty strings
Each lesson ID appears at most once in an adjacency list
A shortest path, when one exists, is unique

Function Signature

def shortest_lesson_path(lessons, start, target):