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 Pinterest.

What role is this question designed for?

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

Solve Two Grid Search Problems | Pinterest Coding Question

Solve Two Grid Search Problems

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following two coding problems. 1. **Count disconnected land regions** - You are given an `m x n` grid of characters where `'1'` represents land and `'0'` represents water. - A region is formed by connecting land cells horizontally or vertically. - Return the number of distinct land regions in the grid. 2. **Compute infection time in a grid** - You are given an `m x n` grid where: - `0` = empty cell - `1` = fresh item - `2` = infected item - Every minute, each infected item spreads infection to its adjacent fresh items in the four cardinal directions. - Return the minimum number of minutes required until no fresh item remains. - If it is impossible to infect all fresh items, return `-1`. The interview note suggests medium-to-upper-medium difficulty and primarily tests graph traversal on grids, especially DFS, BFS, and multi-source BFS.

Quick Answer: This question evaluates proficiency in graph traversal on grids, specifically competencies in identifying connected components and modeling propagation dynamics using DFS, BFS, and multi-source BFS concepts.

Part 1: Count Disconnected Land Regions

You are given a rectangular grid of characters where '1' represents land and '0' represents water. Land cells belong to the same region if they are connected horizontally or vertically. Count how many distinct land regions exist in the grid.

Constraints

0 <= m, n <= 300
Each grid[r][c] is either '0' or '1'
Connectivity is 4-directional only: up, down, left, right

Examples

Input: [["1","1","0","0"],["1","0","0","1"],["0","0","1","1"]]

Expected Output: 2

Explanation: There are two connected groups of land: one in the top-left and one on the right side.

Input: [["1","0","1"],["0","1","0"],["1","0","1"]]

Expected Output: 5

Explanation: All five land cells are only diagonally adjacent, so each one forms its own region.

Input: [["0","0"],["0","0"]]

Expected Output: 0

Explanation: There is no land at all.

Input: [["1"]]

Expected Output: 1

Explanation: A single land cell counts as one region.

Input: []

Expected Output: 0

Explanation: An empty grid contains no land regions.

Hints

When you find an unvisited land cell, treat it as the start of a new region and traverse all land reachable from it.
A BFS or DFS over the grid works well; remember that diagonal neighbors do not connect regions.

Part 2: Compute Infection Time in a Grid

You are given a rectangular grid where 0 means an empty cell, 1 means a fresh item, and 2 means an infected item. Every minute, each infected item spreads infection to its adjacent fresh items in the four cardinal directions. Return the minimum number of minutes needed until no fresh item remains, or -1 if some fresh items can never be infected.

Constraints

0 <= m, n <= 200
Each grid[r][c] is one of 0, 1, or 2
Infection spreads only in 4 directions: up, down, left, right

Examples

Input: [[2,1,1],[1,1,0],[0,1,1]]

Expected Output: 4

Explanation: The infection spreads outward layer by layer and reaches all fresh items in 4 minutes.

Input: [[2,1,1],[0,1,1],[1,0,1]]

Expected Output: -1

Explanation: At least one fresh item is blocked off and can never be infected.

Input: [[0,2]]

Expected Output: 0

Explanation: There are no fresh items to infect, so the answer is 0.

Input: [[1]]

Expected Output: -1

Explanation: There is a fresh item but no infected item to start the spread.

Input: []

Expected Output: 0

Explanation: An empty grid has no fresh items remaining.

Hints

Start BFS from all initially infected cells at once rather than from just one source.
Track how many fresh items remain; when BFS ends, if that count is still positive, the answer is -1.

Quick Overview

This question evaluates proficiency in graph traversal on grids, specifically competencies in identifying connected components and modeling propagation dynamics using DFS, BFS, and multi-source BFS concepts.