Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Uber SWE coding round, one problem the whole session. It looked like a grid puzzle at first glance but the gravity mechanic at the end is what trips people up if they're not careful about order of operations.

Questions Asked (1)

Given a 2D grid where each cell holds a color value or zero, implement one round of a game mechanic: first identify all cells that should explode (a nonzero cell explodes if at least two of its four orthogonal neighbors share its value), set those cells to zero simultaneously, then apply gravity so nonzero values in each column fall to the bottom while preserving their relative order. Return the resulting grid and analyze the time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The explosion detection part was fine, I flagged the cells in a separate pass so I wouldn't modify the board mid-scan.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases. Then, outline a two-phase algorithm: identify exploding cells using a simultaneous check, and apply gravity column-wise. Finally, analyze time and space complexity, and discuss potential optimizations or trade-offs.

Pro tip: Mention that you can combine the explosion and gravity steps by processing each column bottom-up, but emphasize that simultaneous explosion requires a separate pass or careful in-place marking to avoid cascading effects.

1. Clarify requirements and edge cases

Ask about grid dimensions, value ranges, and whether explosions can cascade. Confirm that only one round is needed and that gravity applies after all explosions.

2. Design explosion detection

Iterate through each cell, count orthogonal neighbors with the same nonzero value. Mark cells to explode without modifying the grid yet to ensure simultaneous explosion.

3. Apply explosions and gravity

Set marked cells to zero. Then, for each column, collect nonzero values from bottom to top and rewrite the column with zeros at the top and values at the bottom in original order.

4. Analyze complexity

State time complexity O(R*C) for both phases, and space complexity O(R*C) if using a separate grid or O(C) for column processing with in-place marking.

5. Discuss optimizations and trade-offs

Mention potential to combine passes or use in-place marking, and discuss trade-offs between clarity and efficiency.

Key Points to Mention

Simultaneous explosion requires a two-pass approach or careful in-place marking to avoid cascading effects.
Gravity can be implemented by processing each column independently, preserving relative order of nonzero values.
Time complexity is O(R*C) as each cell is visited a constant number of times.
Space complexity can be O(1) extra if using in-place marking, but O(R*C) if using a separate grid for clarity.
Edge cases: empty grid, all zeros, no explosions, full columns.
Trade-off: in-place marking saves space but may complicate code; separate grid is simpler but uses more memory.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.