Multi-Source BFS with Obstacles and Variable Weights
Given a grid with trucks, obstacles, and boundary dispatch points, find the minimum time to dispatch all trucks using BFS propagation. Follow-up involves weighted propagation where each cell has different dispatch delays, requiring shortest-path algorithms instead of uniform BFS.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid February, 2026
Mid-level
Problem (Warehouse Dispatch Readiness) You are given an m x n grid representing a warehouse yard. Each cell can contain 0 (no truck present), 1 (a truck that is ready to be dispatched), or -1 (an obstacle that blocks movement). Dispatch operations start simultaneously from all boundary cells that contain trucks (1), since those trucks can directly exit the warehouse and initiate dispatch for others. Every minute, a dispatched truck enables its adjacent trucks (up, down, left, right only) to dispatch as well, provided there is no obstacle in between. The task is to compute the minimum time required to dispatch all trucks in the grid. If some trucks can never be reached because they are blocked by obstacles, return -1. Follow-up (Variable Dispatch Time) Now assume each truck takes a different amount of time to prepare for dispatch. Instead of every propagation taking 1 minute, each cell has an associated dispatch delay, and the time to dispatch spreads based on that delay. The goal becomes finding the minimum total time required for all trucks to be dispatched considering these non-uniform times, which changes the problem from a level-by-level spread to a shortest-time propagation problem (multi-source weighted traversal).
Hello Interview Premium
Your account is free and you can post anonymously if you choose.