Question Details
Problem
A grid of colored bubbles is represented as a 2D array of characters. When a player pops a bubble at (r, c), all connected bubbles of the same color (4-directional flood fill) are removed. Remaining bubbles above the removed region fall down to fill the gap (gravity: bubbles fall straight down, not diagonally).
Simulate a sequence of pops and return the grid state after all pops.
python
def simulate_pops(grid: list[list[str]], pops: list[tuple[int,int]]) -> list[list[str]]:
# '.' represents empty space
...
Example:
grid = [
['R','B','R'],
['R','B','B'],
['G','G','B']
]
pops = [(0,0)] # pop 'R' at (0,0), connected R's: (0,0),(1,0)
After flood fill remove:
[['.',B','R'],
['.','B','B'],
['G','G','B']]
After gravity:
[['.','B','R'],
['G','B','B'],
['.','G','B']]
Follow-ups
- What is the time complexity per pop operation?
- How do you handle chain reactions (removed bubbles expose new connected groups of size >= 3 that auto-pop)?
- Extend to 3D (cube grid) -- how does gravity change?
Full Details
Problem
A grid of colored bubbles is represented as a 2D array of characters. When a player pops a bubble at (r, c), all connected bubbles of the same color (4-directional flood fill) are removed. Remaining bubbles above the removed region fall down to fill the gap (gravity: bubbles fall straight down, not diagonally).
Simulate a sequence of pops and return the grid state after all pops.
python
def simulate_pops(grid: list[list[str]], pops: list[tuple[int,int]]) -> list[list[str]]:
# '.' represents empty space
...
Example:
grid = [
['R','B','R'],
['R','B','B'],
['G','G','B']
]
pops = [(0,0)] # pop 'R' at (0,0), connected R's: (0,0),(1,0)
After flood fill remove:
[['.',B','R'],
['.','B','B'],
['G','G','B']]
After gravity:
[['.','B','R'],
['G','B','B'],
['.','G','B']]
Follow-ups
- What is the time complexity per pop operation?
- How do you handle chain reactions (removed bubbles expose new connected groups of size >= 3 that auto-pop)?
- Extend to 3D (cube grid) -- how does gravity change?
About This Question
This is a reported interview question from a codesignal interview.
It covers the following topics: General Coding Assessment, Q3, Coding, Arrays, Matrix .