Capital One·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Capital One SWE coding round, one question about simulating Tetris-like piece placement on a grid. Pretty niche problem, not your usual leetcode fare.

Questions Asked (1)

Given an n x m grid initialized to all zeros and an ordered list of Tetris-like shapes (five fixed types), place each shape at the first valid top-left position in row-major order where all its cells fit within bounds and land on empty grid cells. Mark each placed shape's cells with its 1-based index. Return the final grid.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent way too long just parsing the shape definitions before even thinking about the placement logic.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the five shape definitions and the placement rule, then simulate the process by scanning the grid in row-major order for each shape. For each shape, check every candidate top-left position in order, verify all cells are in-bounds and empty, and mark the first valid placement with the shape's 1-based index.

Pro tip: Precompute each shape's relative cell offsets and iterate candidate positions efficiently; mention that the worst-case time is O(k * n * m * s) where k is the number of shapes and s is the max shape size, and that early termination on the first valid position keeps it practical.

1. Clarify assumptions and constraints

Confirm the exact five shape types, their orientations, and that placement uses the first valid top-left position in row-major order. Ask about grid size limits and whether shapes can be rotated.

2. Represent shapes and grid

Define each shape as a list of relative (row, col) offsets from its top-left anchor. Initialize the n x m grid with zeros and plan to mark cells with the 1-based shape index.

3. Search for valid placement

For each shape in order, iterate top-left positions row by row, column by column. For each position, check that every shape cell is within bounds and currently zero; stop at the first valid position.

4. Place and mark the shape

Once a valid position is found, set each corresponding grid cell to the shape's 1-based index. If no valid position exists, skip the shape (or handle per problem statement).

5. Return final grid and analyze complexity

After processing all shapes, return the grid. State the time complexity O(k * n * m * s) and space complexity O(n * m + k * s), and discuss possible optimizations like early exit or tracking occupied cells.

Key Points to Mention

Row-major order scanning for candidate top-left positions
Representing shapes as relative cell offsets for easy validation
Bounds checking and emptiness checking for all shape cells
Marking cells with the 1-based shape index
Handling shapes that cannot be placed (skip or error per spec)
Time and space complexity analysis with potential optimizations

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