Simulate bubble elimination and maximize common prefix
Quick Overview
This multi-task question evaluates simulation and array manipulation skills for the grid elimination task and scalable string-processing and prefix-search techniques for the longest common prefix task, testing competency in state updates, pattern detection, and efficient data-structure use.
You are given two independent coding tasks (as in a multi-question OA). Solve each.
Task A — Grid “bubble/candy” elimination simulation
You are given an m x n grid board of integers.
Repeatedly apply the following steps until the board becomes stable (no more eliminations):
-
Mark for elimination
: Any cell that is part of a
horizontal or vertical
run of
3 or more equal values
is marked.
- Marking is done based on the board state at the start of the round (i.e., all eliminations in a round happen simultaneously).
-
Eliminate
: Set all marked cells to
0. -
Gravity
: For each column independently, let all
non-zero
values “fall” toward the bottom, preserving their relative order, and fill the remaining cells at the top with
0(equivalently: “zeros float up”).
Output: Return the final stable grid.
Assumptions/constraints (typical OA):
-
1 <= m, n <= 50(or similar) -
Cell values are non-negative integers;
0represents empty.
Task B — Maximum longest common prefix length from two lists
You are given two lists of strings: A and B.
Choose one string a from A and one string b from B. Let lcp(a, b) be the length of the longest common prefix between a and b.
Output: Return the maximum possible value of lcp(a, b) over all pairs (a, b).
Constraints (to rule out brute force):
-
|A|and|B|can be large (e.g., up to1e5total strings) -
Total length of all strings can be large (e.g., up to
1e6) - Lowercase English letters (or ASCII) for simplicity
Your solution should be efficient enough that checking all pairs is too slow.