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 Take-home Project rounds at Rippling.

What role is this question designed for?

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

Find bounding boxes of connected houses | Rippling Coding Question

Q: Find bounding boxes of connected houses

This question evaluates grid traversal and connected-component identification skills, specifically handling ragged 2D arrays, 4-directional adjacency, axis-aligned bounding-box computation, and index-to-label coordinate encoding.

Find bounding boxes of connected houses

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a 2D grid representing a map, where each cell is either `1` (part of a house) or `*` (empty). A **house** is a maximal group of `1` cells connected **4-directionally** (up, down, left, right). Unlike a standard matrix, the grid is **ragged**: each row may have a different number of columns. ### Task Return the bounding rectangle of every house as a pair: - **top-left** coordinate (minimum row, minimum column among the house’s cells) - **bottom-right** coordinate (maximum row, maximum column among the house’s cells) Coordinates must be formatted like spreadsheet cells: - Rows are labeled with uppercase letters: `A` for row 0, `B` for row 1, … - Columns are labeled with 1-based numbers: column 0 → `1`, column 1 → `2`, … So row `0`, col `1` is `A2`. ### Input - A list of rows, where each row is a list (or string) of characters from `{ '1', '*' }`. - Rows can have different lengths. ### Output - A list of house bounding boxes, each represented as a pair of strings: `[topLeft, bottomRight]`. - The order of houses may be arbitrary unless otherwise specified. ### Example Grid (ragged): - Row A: `[* * * * 1 1 1 * *]` - Row B: `[* 1 1 * *]` - Row C: `[* * 1 1 * * *]` Interpretation: a cell exists only where a row has that column index. ### Notes / Edge cases - A neighbor cell is valid only if it is within the bounds of its row. - A house may consist of a single cell. - Assume the number of rows can exceed 26; specify how you will label rows beyond `Z` (e.g., `AA`, `AB`, ...) or state that inputs are limited to 26 rows. ### Constraints (you may assume) - Total number of cells across all rows is up to a reasonable limit (e.g., `<= 2e5`). Design an algorithm to find all houses and their bounding boxes.

Quick Answer: This question evaluates grid traversal and connected-component identification skills, specifically handling ragged 2D arrays, 4-directional adjacency, axis-aligned bounding-box computation, and index-to-label coordinate encoding.

You are given a ragged 2D grid representing a map. Each existing cell contains either '1' (part of a house) or '*' (empty land). A house is a maximal group of '1' cells connected 4-directionally: up, down, left, and right. Because the grid is ragged, a neighbor is valid only if that column index exists in the neighboring row. For every house, return its bounding rectangle as a pair [topLeft, bottomRight], where topLeft is the smallest row and column occupied by that house, and bottomRight is the largest row and column occupied by that house. Coordinates use spreadsheet-style labels: - Rows are labeled A, B, ..., Z, AA, AB, ... - Columns are 1-based, so column 0 becomes 1, column 1 becomes 2, and so on. For deterministic output, sort the bounding boxes by their numeric coordinates: top row, then left column, then bottom row, then right column.

Constraints

1 <= total number of existing cells across all rows <= 2 * 10^5, or grid may be empty
Each existing cell is either '1' or '*'
Rows may have different lengths, including length 0

Examples

Input: ['****111**', '*11**', '**11***']

Expected Output: [['A5', 'A7'], ['B2', 'C4']]

Explanation: There are two houses. The top row cluster spans A5 to A7. The lower ragged cluster spans from B2 to C4.

Input: []

Expected Output: []

Explanation: An empty grid contains no houses.

Input: ['', '1', '***']

Expected Output: [['B1', 'B1']]

Explanation: There is exactly one house, consisting of a single cell at row 1, column 0.

Input: [['1', '1', '*', '1'], ['1', '*', '*', '1'], ['1', '1', '1', '*']]

Expected Output: [['A1', 'C3'], ['A4', 'B4']]

Explanation: The left house forms an irregular connected shape bounded by A1 and C3. The right house is a vertical pair bounded by A4 and B4.

Input: ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '11', '11']

Expected Output: [['AA1', 'AB2']]

Explanation: Rows beyond Z continue as AA, AB, and so on. The only house occupies rows AA and AB, columns 1 through 2.

Input: ['*1', '*', '*1']

Expected Output: [['A2', 'A2'], ['C2', 'C2']]

Explanation: The two '1' cells are not connected because the middle row does not have a column 1 cell, so no vertical neighbor exists there.

Hints

Run BFS or DFS from every unvisited '1' cell to discover one entire house at a time.
While exploring a house, keep track of the minimum and maximum row and column indices you see.

Quick Overview

This question evaluates grid traversal and connected-component identification skills, specifically handling ragged 2D arrays, 4-directional adjacency, axis-aligned bounding-box computation, and index-to-label coordinate encoding.