Frontend School

Myntra Delivery Route

DSA
easy

Myntra Delivery Route

Easy
Graph
BFS
Grid

Overview

At Myntra, efficient logistics are crucial for timely deliveries. Imagine a large warehouse where delivery agents navigate through aisles and storage areas. This problem simulates a scenario where an agent needs to pick up a package component from a specific station before heading to the final delivery drop-off point, all while avoiding obstacles. Your task is to find the most efficient route.

What you need to do / Task

Implement a function findMinDeliverySteps that calculates the minimum number of steps required for a delivery agent to complete a specific route in a warehouse.

  1. The agent starts at 'S' (Start).
  2. They must first travel to 'P' (Pickup Station) to collect a package component.
  3. After collecting, they then travel from 'P' to 'D' (Destination) to deliver the package.
  4. Movement is restricted to cardinal directions (up, down, left, right).
  5. Obstacles '#' cannot be traversed. Empty paths '.' can be traversed.
  6. Each move to an adjacent cell counts as one step.
  7. If it's impossible to complete the entire route (S to P, or P to D), return -1.

Input & Output

Input:

  • warehouseLayout: A string[][] (or char[][]) representing the 2D grid of the warehouse.
    • 'S': Starting point of the agent. (Guaranteed exactly one 'S')
    • 'P': Pickup station, must be visited. (Guaranteed exactly one 'P')
    • 'D': Final delivery destination. (Guaranteed exactly one 'D')
    • '#': Obstacle.
    • '.': Empty path.

Output:

  • An number representing the minimum total steps required to travel from 'S' to 'P' and then from 'P' to 'D'. Return -1 if any part of the journey is impossible.

Examples

1

Example 1

Input:

warehouseLayout = [["S", ".", "."], [".", "#", "P"], [".", ".", "D"]]

Output:

4

Note:

Path S->P: S(0,0) -> (0,1) -> (0,2) -> P(1,2) takes 3 steps. Path P->D: P(1,2) -> D(2,2) takes 1 step. Total steps: 3 + 1 = 4.

2

Example 2

Input:

warehouseLayout = [["S", "#", "."], ["#", "#", "P"], [".", "#", "D"]]

Output:

-1

Note:

It's impossible to reach 'P' from 'S' due to obstacles.

3

Example 3

Input:

warehouseLayout = [["S", ".", ".", "."], [".", "#", ".", "P"], ["#", ".", ".", "."], [".", ".", ".", "D"]]

Output:

6

Note:

Path S->P: S(0,0) -> (0,1) -> (0,2) -> (0,3) -> P(1,3) takes 4 steps. Path P->D: P(1,3) -> (2,3) -> D(3,3) takes 2 steps. Total steps: 4 + 2 = 6.

Constraints

Constraints & assumptions

  • warehouseLayout will have M rows and N columns.
  • 1 <= M, N <= 100
  • Each cell in warehouseLayout will contain one of 'S', 'P', 'D', '#', '.'.
  • There will be exactly one 'S', one 'P', and one 'D'.
  • Movement is restricted to 4 cardinal directions (up, down, left, right).
  • Cells with '#' are impassable.

Out of scope

  • Diagonal movement.
  • Multiple 'S', 'P', or 'D' locations.
  • Time-varying obstacles or dynamic warehouse layouts.
  • Calculating optimal path if 'P' could be visited at any point, not necessarily first. (The problem explicitly states "must first travel to 'P'")

What interviewers evaluate

  • Correctness: Does the solution accurately calculate the minimum steps for all valid and invalid paths?
  • Algorithm Choice: Is an appropriate graph traversal algorithm (BFS/DFS) used for shortest path on an unweighted graph?
  • Edge Case Handling: Does the solution correctly handle scenarios where paths are impossible or grid boundaries are reached?
  • Code Structure & Readability: Is the code clean, well-organized, and easy to understand, with meaningful variable names?

Loading editor...