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

What role is this question designed for?

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

Determine Balloon Popping Time | Bloomberg Coding Question

Determine Balloon Popping Time

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a rectangular 2D grid representing a field of balloons. Each cell contains exactly one of the following values: - `0`: empty cell - `1`: inflated balloon - `2`: already popped balloon Popping can spread only in the four cardinal directions: up, down, left, and right. Empty cells do not contain balloons and cannot spread popping. Answer the following related questions: 1. **Can all balloons pop?** - An inflated balloon eventually pops if it is connected through adjacent inflated balloons to at least one initially popped balloon. - Return `true` if every inflated balloon can eventually pop; otherwise return `false`. 2. **How long does popping take with uniform spread time?** - Now assume that every popped balloon takes exactly `1` minute to pop each adjacent inflated balloon. - Return the number of minutes required for all inflated balloons to pop. - If at least one inflated balloon can never pop, return `-1`. 3. **How long does popping take with variable spread times?** - You are also given a matrix `spreadTime` with the same dimensions as `grid`. - If a balloon at cell `(r, c)` has already popped, then after `spreadTime[r][c]` minutes, it can pop each adjacent inflated balloon. - Different balloons may have different spread times, such as `1` minute or `5` minutes. - Return the earliest total time at which all inflated balloons have popped. - If at least one inflated balloon can never pop, return `-1`.

Quick Answer: This question evaluates understanding of grid-to-graph modeling, reachability and propagation dynamics, and handling heterogeneous spread times within the Coding & Algorithms domain.

Part 1: Can All Balloons Pop?

You are given a 2D grid representing a field of balloons. Each cell contains one value: 0 for an empty cell, 1 for an inflated balloon, or 2 for an already popped balloon. Popping spreads only in the four cardinal directions and cannot pass through empty cells. Starting from every cell that is already popped, determine whether repeated spreading can eventually reach every inflated balloon. Return True if all inflated balloons can eventually pop; otherwise return False. If the grid is empty, return True.

Constraints

0 <= number of rows, number of columns <= 200
Each grid cell is one of 0, 1, or 2
For a non-empty grid, all rows have the same length

Examples

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

Expected Output: True

Explanation: Starting from the popped balloon at the top-left, the spread can travel through connected non-zero cells and eventually reach every inflated balloon.

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

Expected Output: False

Explanation: The balloon at the bottom-left is isolated by empty cells, so it can never be reached.

Input: [[1,1],[1,1]]

Expected Output: False

Explanation: There are inflated balloons but no already popped balloon to start the spread.

Input: []

Expected Output: True

Explanation: An empty grid has no inflated balloons to reach.

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

Expected Output: True

Explanation: There are no inflated balloons at all, so the condition is already satisfied.

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

Expected Output: True

Explanation: Two separate popped balloons act as two sources, and together they can reach both inflated balloons.

Hints

Think of every cell containing 2 as a starting point in one multi-source graph traversal.
You only need to know whether every 1 is reachable from some 2 without crossing a 0.

Part 2: Minutes Until All Balloons Pop

You are given a 2D grid representing a field of balloons. Each cell contains one value: 0 for an empty cell, 1 for an inflated balloon, or 2 for an already popped balloon. Every popped balloon takes exactly 1 minute to pop each adjacent inflated balloon in the four cardinal directions. Empty cells never spread popping. Return the number of minutes required for all inflated balloons to pop. If at least one inflated balloon can never pop, return -1. If the grid has no inflated balloons, return 0.

Constraints

0 <= number of rows, number of columns <= 200
Each grid cell is one of 0, 1, or 2
For a non-empty grid, all rows have the same length

Examples

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

Expected Output: 4

Explanation: The popping spreads outward from the initial popped balloon and reaches the last inflated balloon after 4 minutes.

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

Expected Output: -1

Explanation: The inflated balloon in the bottom-left region is blocked by empty cells and can never be reached.

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

Expected Output: 0

Explanation: There are no inflated balloons at the start, so no time is needed.

Input: ([[1]],)

Expected Output: -1

Explanation: There is an inflated balloon but no popped balloon to start the chain reaction.

Input: ([],)

Expected Output: 0

Explanation: An empty grid contains no inflated balloons, so the answer is 0.

Hints

All initially popped balloons start spreading at the same time, so think multi-source BFS.
Each BFS level corresponds to one minute of spreading.

Part 3: Earliest Time with Variable Spread Speeds

You are given a 2D grid representing a field of balloons and a second matrix spreadTime of the same size. Each grid cell contains 0 for empty, 1 for inflated, or 2 for already popped. All cells containing 2 are popped at time 0. If a balloon at cell (r, c) has already popped, then after spreadTime[r][c] minutes it can pop each adjacent inflated balloon in the four cardinal directions. Different cells may have different spread times. Return the earliest total time at which all inflated balloons have popped, or -1 if some inflated balloon can never pop. If there are no inflated balloons, return 0.

Constraints

0 <= number of rows, number of columns <= 200
grid and spread_time have the same dimensions
Each grid cell is one of 0, 1, or 2
0 <= spread_time[r][c] <= 10^9
For a non-empty grid, all rows have the same length

Examples

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

Expected Output: 7

Explanation: The popping times are 0 -> 1 -> 3 -> 7 along the row, so the last balloon pops at time 7.

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

Expected Output: 3

Explanation: The two adjacent balloons pop at time 1. Then the bottom-right balloon is reached faster from the top-right cell: 1 + 2 = 3.

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

Expected Output: -1

Explanation: The inflated balloon is separated by an empty cell, so the popping cannot spread to it.

Input: ([[0, 2], [0, 0]], [[5, 1], [7, 3]])

Expected Output: 0

Explanation: There are no inflated balloons to pop, so the answer is 0.

Input: ([[2, 1, 1], [1, 1, 0]], [[0, 2, 3], [4, 1, 0]])

Expected Output: 2

Explanation: The source cell has spread time 0, so two neighbors pop immediately. From there, the remaining balloons are reached by time 2.

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

Expected Output: -1

Explanation: There is an inflated balloon but no already-popped balloon to start the chain.

Hints

When spreading costs are not all equal, plain BFS is no longer enough.
Model each non-empty cell as a node. Moving from one popped cell to an adjacent balloon costs spread_time of the current cell, so a priority queue is useful.

Quick Overview

This question evaluates understanding of grid-to-graph modeling, reachability and propagation dynamics, and handling heterogeneous spread times within the Coding & Algorithms domain.