Quick Overview

This question evaluates graph traversal and connected-components detection on grids, measuring competence in grid-based algorithms, neighbor connectivity, and algorithmic analysis of time and space complexity.

Count connected delivery zones

Company: Uber

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an m x n grid representing a service area, each cell is either 'Z' (deliverable zone) or '#' (blocked). Two 'Z' cells belong to the same zone if they are 4-directionally adjacent. Implement countZones(grid: List[List[char]]) -> int that returns the number of connected zones. Follow-up: return the sizes of all zones in descending order. Analyze time and space complexity, and then optimize for minimal extra space.

Overview: This question evaluates graph traversal and connected-components detection on grids, measuring competence in grid-based algorithms, neighbor connectivity, and algorithmic analysis of time and space complexity.

Read the full Uber Machine Learning Engineer interview experience this question came from

Count connected delivery zones

You are given an `m x n` grid representing a service area. Each cell is either `'Z'` (a deliverable zone) or `'#'` (blocked). Two `'Z'` cells belong to the same zone if they are 4-directionally adjacent (up, down, left, right). Implement `countZones(grid)` that returns the number of connected zones (connected components of `'Z'` cells). This is the classic "Number of Islands" problem framed as a delivery service area. To minimize extra space, flip each visited `'Z'` to `'#'` in place instead of using a separate visited set. Example: ``` grid = [['Z','Z','#','#','#'], ['Z','Z','#','#','#'], ['#','#','Z','#','#'], ['#','#','#','Z','Z']] countZones(grid) -> 3 ``` There are three zones: the 2x2 block in the top-left, the single cell in the middle, and the pair in the bottom-right.

Constraints

  • 1 <= m, n; the grid may be empty (return 0).
  • Each cell is either 'Z' or '#'.
  • Connectivity is 4-directional only (no diagonals).
  • The input grid may be mutated in place by the reference solution.

Examples

Input: ([['Z','Z','#','#','#'],['Z','Z','#','#','#'],['#','#','Z','#','#'],['#','#','#','Z','Z']],)

Expected Output: 3

Explanation: Three components: the top-left 2x2 block, the single middle cell, and the bottom-right pair.

Input: ([['Z','Z','Z','Z'],['Z','#','#','Z'],['Z','Z','Z','Z']],)

Expected Output: 1

Explanation: A single ring-shaped component surrounding two blocked cells is still one connected zone.

Hints

  1. This is 'Number of Islands' with 'Z' as land and '#' as water.
  2. Scan every cell; when you hit an unvisited 'Z', increment the count and flood-fill the whole component.
  3. Instead of a visited set, overwrite each visited 'Z' with '#' to use O(1) extra marking space — that is the minimal-space optimization the follow-up asks for.

Delivery zone sizes in descending order

Follow-up to 'Count connected delivery zones'. Given the same `m x n` grid of `'Z'` (deliverable zone) and `'#'` (blocked) cells, implement `zoneSizes(grid)` that returns a list of the sizes of all connected zones (4-directionally connected components of `'Z'` cells), sorted in descending order. Example: ``` grid = [['Z','Z','#','#','#'], ['Z','Z','#','#','#'], ['#','#','Z','#','#'], ['#','#','#','Z','Z']] zoneSizes(grid) -> [4, 2, 1] ``` The top-left block has 4 cells, the bottom-right pair has 2, and the middle cell has 1.

Constraints

  • 1 <= m, n; the grid may be empty (return []).
  • Each cell is either 'Z' or '#'.
  • Connectivity is 4-directional only (no diagonals).
  • The result must be sorted in descending order by size.
  • The input grid may be mutated in place by the reference solution.

Examples

Input: ([['Z','Z','#','#','#'],['Z','Z','#','#','#'],['#','#','Z','#','#'],['#','#','#','Z','Z']],)

Expected Output: [4, 2, 1]

Explanation: Sizes 4 (top-left block), 2 (bottom-right pair), and 1 (middle cell), sorted descending.

Input: ([['Z','Z','Z','Z'],['Z','#','#','Z'],['Z','Z','Z','Z']],)

Expected Output: [10]

Explanation: One connected ring-shaped zone of 10 cells.

Hints

  1. Reuse the flood-fill from countZones, but count the cells in each component instead of just incrementing a component counter.
  2. Collect each component's size as you finish flooding it.
  3. Sort the collected sizes in descending order before returning.

Loading coding console...