Simulate bubble elimination and maximize common prefix
You are presented with two independent coding tasks. Solve each task efficiently and correctly.
Task A: Grid Bubble/Candy Elimination Simulation
You are given an m x n grid, board, containing non-negative integers. 0 represents an empty cell.
Repeatedly apply the following three steps until the board becomes stable (i.e., no more eliminations occur in a round):
- Mark for Elimination: Identify any cell that is part of a horizontal or vertical run of three or more identical non-zero values. All such cells are marked for elimination based on the board's state at the beginning of the current round. This means all eliminations within a single round are determined simultaneously.
- Eliminate: Set all cells that were marked in step 1 to
0. - Gravity: For each column independently, all non-zero values "fall" towards the bottom of the column, preserving their relative order. The empty cells created at the top of the column are filled with
0.
Output: Return the final stable grid.
Constraints:
1 <= m, n <= 50- Cell values are non-negative integers.
0represents an empty cell.
Task B: Maximum Longest Common Prefix Length from Two Lists
You are given two lists of strings, A and B.
Your goal is to choose one string a from list A and one string b from list B such that the length of their longest common prefix, lcp(a, b), is maximized.
Output: Return the maximum possible value of lcp(a, b) over all possible pairs (a, b).
Constraints:
- The number of strings in list
A(|A|) and listB(|B|) can be large, up to1e5each. - The total length of all strings across both lists can be large, up to
1e6. - Strings consist of lowercase English letters (or ASCII characters for simplicity).
- Your solution must be efficient enough to avoid checking all possible pairs, as this would be too slow given the constraints.
AI interview prep
Core dilemma
Designing efficient algorithms for distinct problem types under tight performance constraints, demonstrating mastery of simulation logic and advanced string data structures.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Simulate bubble elimination and maximize common prefix
You are presented with two independent coding tasks. Solve each task efficiently and correctly.
Task A: Grid Bubble/Candy Elimination Simulation
You are given an m x n grid, board, containing non-negative integers. 0 represents an empty cell.
Repeatedly apply the following three steps until the board becomes stable (i.e., no more eliminations occur in a round):
- Mark for Elimination: Identify any cell that is part of a horizontal or vertical run of three or more identical non-zero values. All such cells are marked for elimination based on the board's state at the beginning of the current round. This means all eliminations within a single round are determined simultaneously.
- Eliminate: Set all cells that were marked in step 1 to
0. - Gravity: For each column independently, all non-zero values "fall" towards the bottom of the column, preserving their relative order. The empty cells created at the top of the column are filled with
0.
Output: Return the final stable grid.
Constraints:
1 <= m, n <= 50- Cell values are non-negative integers.
0represents an empty cell.
Task B: Maximum Longest Common Prefix Length from Two Lists
You are given two lists of strings, A and B.
Your goal is to choose one string a from list A and one string b from list B such that the length of their longest common prefix, lcp(a, b), is maximized.
Output: Return the maximum possible value of lcp(a, b) over all possible pairs (a, b).
Constraints:
- The number of strings in list
A(|A|) and listB(|B|) can be large, up to1e5each. - The total length of all strings across both lists can be large, up to
1e6. - Strings consist of lowercase English letters (or ASCII characters for simplicity).
- Your solution must be efficient enough to avoid checking all possible pairs, as this would be too slow given the constraints.