How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Count clusters covered by dashers | DoorDash Coding Question

Quick Overview

Count clusters covered by dashers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Count clusters covered by dashers

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given two m×n binary matrices of equal size: D for dasher availability and U for user presence. A cell value 1 indicates presence; 0 indicates absence. In U, define a cluster as a maximal group of horizontally or vertically adjacent 1-cells (4-neighborhood; diagonal adjacency does not connect). Task: Return the number of clusters in U such that every cell (i, j) in the cluster also has D[i][j] = 1 (i.e., every user in that cluster has a dasher at the same position). Describe your algorithm and analyze time and space complexity. Follow-up: For each qualifying cluster, output the list of its member coordinates (row, col) in a consistent order (e.g., increasing row, then column), and discuss how this affects complexity and memory usage.

Quick Answer: Count clusters covered by dashers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given two m x n binary matrices of equal size: `D` for dasher availability and `U` for user presence. A cell value of `1` indicates presence; `0` indicates absence. In `U`, a **cluster** is a maximal group of horizontally or vertically adjacent `1`-cells (4-neighborhood; diagonal adjacency does NOT connect cells). Return the number of clusters in `U` such that **every** cell `(i, j)` in the cluster also has `D[i][j] == 1` — i.e., every user in the cluster has a dasher at the same position. Write a function `countCoveredClusters(D, U)` that returns this count. **Example** ``` D = [[1,1], [1,1]] U = [[1,0], [0,1]] ``` There are two clusters in U (the single cell (0,0) and the single cell (1,1)). Both are fully covered by D, so the answer is `2`. **Approach.** Scan every cell of `U`. When you find an unvisited user cell, flood-fill (BFS or DFS) its whole connected component using only 4-directional moves, marking each cell visited. While exploring, check whether every member cell also has `D == 1`. If the entire cluster is covered, increment the count. Each cell is visited once, giving O(m·n) time and O(m·n) space for the visited grid and the traversal frontier. **Follow-up.** For each qualifying cluster, you could additionally collect its member coordinates `(row, col)`. Sorting them by increasing row then column adds O(k log k) per cluster of size k (or O(m·n) total if you collect in scan order). Memory grows by the total number of qualifying user cells stored.

Constraints

1 <= m, n (matrices may also be empty, in which case return 0)
D and U have identical dimensions m x n
Every cell of D and U is 0 or 1
Clusters use 4-directional (horizontal/vertical) adjacency only; diagonals do not connect
A cluster qualifies only if EVERY one of its cells has D == 1

Examples

Input: ([[1,1],[1,1]], [[1,0],[0,1]])

Expected Output: 2

Explanation: Two single-cell clusters at (0,0) and (1,1); both have D==1, so both qualify.

Input: ([[1,0],[1,1]], [[1,1],[1,1]])

Expected Output: 0

Explanation: All four user cells form one cluster, but D[0][1]==0, so the cluster is not fully covered.

Input: ([[1,1,1],[1,0,1],[1,1,1]], [[1,1,0],[0,0,0],[0,1,1]])

Expected Output: 2

Explanation: Cluster {(0,0),(0,1)} is covered (D both 1) and cluster {(2,1),(2,2)} is covered (D both 1); both qualify.

Input: ([[1,1],[1,1]], [[1,1],[1,1]])

Expected Output: 1

Explanation: All user cells form a single connected cluster fully covered by dashers.

Input: ([], [])

Expected Output: 0

Explanation: Empty matrices contain no clusters.

Input: ([[0]], [[1]])

Expected Output: 0

Explanation: The lone user cell has no dasher (D==0), so it does not qualify.

Input: ([[1]], [[1]])

Expected Output: 1

Explanation: A single covered user cell forms one qualifying cluster.

Input: ([[1,0,1],[0,0,0],[1,0,1]], [[1,1,1],[0,0,0],[1,0,1]])

Expected Output: 2

Explanation: Top-row cluster fails (D[0][1]==0), but isolated cells (2,0) and (2,2) each qualify (D==1).

Input: ([[1,1,1,1]], [[1,0,1,1]])

Expected Output: 2

Explanation: Two clusters in the row: {(0,0)} and {(0,2),(0,3)} (the 0 at column 1 separates them); both are fully covered.

Hints

Iterate over all cells; when you hit an unvisited user cell (U==1), it is the seed of a new cluster — flood-fill it.
Use BFS or DFS with only the 4 orthogonal neighbors. Mark cells visited as you push them so you never count a cluster twice.
Track a boolean for the current cluster: it stays true only if every visited cell also satisfies D[i][j]==1. Don't break early — you must mark the whole component visited even if it already fails coverage.
Edge cases: empty matrix returns 0; a single user cell with no dasher under it does not qualify.

Quick Overview