Delivery Heatmap Grid | Dataford Interview Questions

Your question is Delivery Heatmap Grid. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

DoorDash wants to estimate delivery demand across an n x n service area. Each restaurant contributes one expected delivery to every grid cell within its delivery range.

Given the grid size and restaurant locations, return a heatmap where heatmap[r][c] equals the number of restaurants whose delivery range includes cell (r, c). A restaurant at (rr, cc) with range d covers a cell when abs(r - rr) + abs(c - cc) <= d.

Design an algorithm that is faster than processing every restaurant-cell pair.

Formal Specification

Implement heatmap(n, restaurants):

n is an integer.
restaurants is a list of [row, column, range] arrays.
Rows and columns are zero-indexed.
Return an n x n list of integers.
Each restaurant contributes independently, so overlapping delivery ranges increase the count.

Constraints

1 <= n <= 2,000
0 <= len(restaurants) <= 100,000
0 <= row, column < n
0 <= range <= 2 * n - 2
The output contains exactly n rows and n columns

Function Signature

def heatmap(n, restaurants):