← Instacart Interview InsightsSoftware Engineer

Instacart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Instacart software engineer interview with a grid placement problem that sounds deceptively simple until you actually try to implement the greedy logic correctly for non-rectangular shapes. Took me longer than I'd like to admit to get the T-shape handling right.

Questions Asked (1)

Q1

Given an empty 2D grid and four fixed shapes (each defined as a small 2D binary mask), place all four shapes onto the grid such that no two shapes overlap and each shape is placed at the lexicographically smallest valid (row, col) origin in order. One of the shapes is a T-shape (not a rectangle). Return the final grid or the chosen origin for each shape.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The greedy part seemed straightforward but the T-shape tripped me up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and define the lexicographic order for placement. Then, iterate through each shape in the given order, scanning the grid row by row and column by column to find the first valid origin where the shape fits without overlapping previously placed shapes. Place the shape and continue until all shapes are placed.

Pro tip: Demonstrate awareness of edge cases such as shapes that cannot be placed due to insufficient space, and discuss how to handle them (e.g., return an error or backtrack). Also, mention that the T-shape requires careful handling because it's not a rectangle, so simple bounding box checks are insufficient.

1. Clarify the problem

Ask questions to confirm the grid size, shape definitions, and the exact meaning of 'lexicographically smallest valid origin'. Ensure you understand the order of placement and what to return.

2. Define the placement algorithm

For each shape in order, scan the grid from top-left to bottom-right. For each cell, check if the shape can be placed with that cell as its top-left origin without overlapping existing shapes.

3. Implement overlap checking

For a given origin, iterate over the shape's mask and verify that all cells are within the grid and not already occupied. If any cell is invalid, move to the next origin.

4. Place the shape and continue

Once a valid origin is found, mark the grid cells as occupied and record the origin. Proceed to the next shape.

5. Handle edge cases and return result

If a shape cannot be placed, discuss possible actions (e.g., return an error, backtrack, or skip). Finally, return the grid or the list of origins as required.

Key Points to Mention

  • Lexicographic order: row-major order (top to bottom, left to right) for scanning origins.
  • Overlap detection: use a boolean grid or set of occupied cells to efficiently check collisions.
  • Shape representation: use a list of relative coordinates or a binary mask for each shape.
  • T-shape handling: ensure the algorithm works for non-rectangular shapes by checking each cell of the mask.
  • Time complexity: O(N * M * K) where N and M are grid dimensions and K is the total number of cells across all shapes.
  • Edge cases: shapes that don't fit, grid too small, or overlapping constraints that make placement impossible.

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