Mouse and Valid Move API | Dataford Interview Questions

Help a mouse find cheese given only an API that tells you whether a move is valid (no grid or coordinates)

Asked in the coding stage. Implement the search using only movement operations and cheese detection after the API is initialized from the test representation.

Input and Output

find_cheese(edges, start, cheese) receives directed movement records [from_node, direction, to_node], a starting node ID, and a list of cheese node IDs. Each listed move is reversible using the opposite direction. Return a list of direction strings leading to any cheese node, or None if no cheese is reachable. Valid directions are U, R, D, and L.

Constraints

Node IDs are non-empty strings.
Each direction is one of U, R, D, or L.
Each listed movement is reversible using the opposite direction.
The graph contains at most 10^4 nodes and 4 * 10^4 movement records.

Function Signature

def find_cheese(edges, start, cheese):

Your question is Mouse and Valid Move API. 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