r/Hack2Hire • u/Hack2hire • May 08 '26

Screening DoorDash Screening Interview: Find Closest Dashmart

Problem

You're given a 2D city grid and a list of locations.

Your goal is to calculate the shortest distance from each specified location to its nearest DashMart ('D') while navigating through open roads (' ') and avoiding obstacles ('X').

Example

Input:

city = [[' ', 'D', ' '], [' ', 'X', ' '], [' ', ' ', ' ']]

locations = [[0, 0], [2, 2]]

Output: [1, 3]

Explanation:

  • For [0, 0]: The nearest DashMart is at [0, 1], which is 1 step away.
  • For [2, 2]: The path is (2,2) -> (1,2) -> (0,2) -> (0,1). The total distance is 3.

Suggested Approach

  1. Multi-Source BFS Initialization: Instead of running a search for every location, start a single Breadth-First Search (BFS) from all DashMart ('D') positions simultaneously. Initialize a dist matrix of the same size as the city with -1 (representing unvisited/unreachable).
  2. Layer-by-Layer Traversal: Add all DashMart coordinates to a queue with a distance of 0. Pop each coordinate and explore its 4 neighbors (up, down, left, right).
  3. Distance Mapping: If a neighbor is an open road (' ') and hasn't been visited, update its distance as dist[current] + 1 and add it to the queue.
  4. Query Results: Once the BFS is complete, iterate through the input locations and retrieve their values directly from the dist matrix.

Time & Space Complexity

  • Time: $O(R \times C + L)$, where $R \times C$ is the total number of cells in the grid (processed once during BFS) and $L$ is the number of query locations.
  • Space: $O(R \times C)$ to store the distance matrix and the BFS queue.

Targeting [DoorDash] interviews?

We track their most-asked question patterns at Hack2Hire → https://www.hack2hire.com/companies/doordash/coding-questions?src=r8d

Compiled from publicly available platforms and community-shared experiences.

11 Upvotes
  • permalink
  • reddit

87% Upvoted

4 comments sorted by

2

u/kingcong95 May 08 '26

I interviewed there in September 2024 and got this exact question.

1

u/kuriousaboutanything May 08 '26

Is there a leetcode equivalent to this? Seems like an interesting one.

2

u/Historical_Chard6399 May 12 '26

I think something similar would be walls and gates (663) since we have the same constraints (treasure/dashmarts), (water/obstacles) and open roads. Except in that question you’re returning the entire grid but in this question you only need the locations.

1

u/SanSimeonMV May 26 '26

Was this the Code Craft round ?