Shortest Time to Treasure in a Time-Scheduled Maze

A maze where every room has four doors, each opening clockwise on a schedule keyed to time mod 4; starting from a given initial door/treasure configuration at time 0, find the minimum time to collect all k treasures in the maze and then reach the end room.

Asked in the Onsite coding stage. Candidate attempted BFS and DP approaches but could not complete a working solution in the interview.

Implement minimum_time(doors, start, end, k, treasure_masks, initial_doors). doors[r][d] is the destination through room r's door d, or -1; at time t, door (initial_doors[r] + t) % 4 is open. A move or a wait takes one unit of time. treasure_masks[r] identifies treasures in room r. Return the minimum time, or -1 if impossible.

Constraints

1 <= len(doors) <= 100
Each room has exactly four door entries
0 <= start, end < len(doors)
0 <= k <= 15
Each destination is -1 or a valid room index
Each treasure mask uses only the lowest k bits
0 <= initial_doors[r] < 4
A room may contain multiple treasures

Function Signature

def minimum_time(doors, start, end, k, treasure_masks, initial_doors):

Your question is Shortest Time to Treasure in a Time-Scheduled Maze. 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

Asked in the Onsite coding stage. Candidate attempted BFS and DP approaches but could not complete a working solution in the interview.

Constraints

1 <= len(doors) <= 100
Each room has exactly four door entries
0 <= start, end < len(doors)
0 <= k <= 15
Each destination is -1 or a valid room index
Each treasure mask uses only the lowest k bits
0 <= initial_doors[r] < 4
A room may contain multiple treasures

Function Signature

def minimum_time(doors, start, end, k, treasure_masks, initial_doors):

Your question is Shortest Time to Treasure in a Time-Scheduled Maze. 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.