Navigate unknown maze to find target

Q: Navigate unknown maze to find target

This question evaluates understanding of graph traversal and exploration algorithms, representation of visited state and frontiers, path optimality, and complexity analysis in an environment constrained to local actions.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an exploration interface for an unknown 2D maze that exposes only local actions (e.g., move(up/down/left/right) -> bool indicating success, position() -> (r,c), and atCheese() -> bool). Starting from an initial cell, design an algorithm to find the cheese with the fewest steps if it is reachable, minimizing redundant moves. You may adapt/override the interface to enable breadth-first exploration on the fly (e.g., by building a discovered map and backtracking). Specify visited-state representation, frontier management, termination conditions, and complexity in terms of reachable cells. Follow-up: Propose unit tests, including obstacles at start, multiple cheeses, unreachable cheese, loops, unknown bounds, and large open areas.

Navigate unknown maze to find target

Overview

Comments (0)