Instacart Software Engineer Onsite Coding Questions

LeetCode #1701: Average Waiting Time. Difficulty: Medium. Topics: Array, Simulation. Asked at Instacart in the last 6 months.

LeetCode #34: Find First and Last Position of Element in Sorted Array. Difficulty: Medium. Topics: Array, Binary Search. Asked at Instacart in the last 6 months.

LeetCode #49: Group Anagrams. Difficulty: Medium. Topics: Array, Hash Table, String, Sorting. Asked at Instacart in the last 6 months.

## Problem Given a list of records with dimensions and a metric, produce a pivot table. Rows are indexed by one dimension, columns by another, and cells contain an aggregated metric (sum or average). ```python def pivot_table( records: list[dict], row_dim: str, col_dim: str, metric: str, agg: str = "sum" # "sum" or "avg" ) -> dict[str, dict[str, float]]: ... ``` ``` Records: [{"region":"North","product":"A","sales":100}, {"region":"North","product":"B","sales":200}, {"region":"South","product":"A","sales":150}, {"region":"South","product":"A","sales": 50}] pivot_table(records, row_dim="region", col_dim="product", metric="sales", agg="sum") Output: { "North": {"A": 100, "B": 200}, "South": {"A": 200} # 150+50 } ``` ## Follow-ups 1. How do you handle missing combinations (e.g., South has no product B)? Return 0, null, or omit the key? 2. Add a `totals=True` option that appends row totals and a grand total column. Walk through the implementation. 3. Support a third dimension as a page filter (e.g., filter to only `year=2024` before pivoting). How does the function signature change? 4. If records come from a SQL database, write the equivalent SQL `GROUP BY` query with `CASE WHEN` column pivoting.

## Problem You are given an `(m+1) x (n+1)` matrix where the last row contains the XOR of each column and the last column contains the XOR of each row. One cell in the original `m x n` region is corrupted (flipped bits). Find the coordinates of the corrupted cell and restore its correct value. ```python def find_and_fix_corrupted( matrix: list[list[int]] ) -> tuple[int, int, int]: """Return (row, col, corrected_value).""" ... ``` ``` Original 2x2 (with checksums as 3x3): 1 2 3 <- 3 = XOR of row 0 4 5 1 <- 1 = XOR of row 1 5 7 <- col XOR checksums Corrupt cell (0,1): 2 -> 9 1 9 3 4 5 1 5 12 Column 1 checksum: 9 XOR 5 = 12, expected 7 -> mismatch -> col=1 Row 0 checksum: 1 XOR 9 = 10, expected 3 -> mismatch -> row=0 Corrected value: 9 XOR 10 XOR 3 = 2 Output: (0, 1, 2) ``` ## Follow-ups 1. Prove that XOR of a row and its checksum equals 0 when uncorrupted. How does corruption change this? 2. What if two cells are corrupted? Can you still detect and fix them with this scheme? 3. How does this relate to RAID-5 parity? Describe the analogy. 4. Extend to 3D: a cube with checksum planes on all three faces. How do you locate a single corrupted voxel?

Design and implement an **in-memory database** keyed by `key` (unique per record). Each record contains multiple `field -> value` pairs, where both `field` and `value` are strings. Implement the foll

Given an integer array `nums` (may contain negative numbers), count how many **contiguous subarrays** have strictly alternating parity between adjacent elements. Formally, a subarray `nums[l..r]` is

Given an array of strings `arr`, transform each string `s` as follows and return the resulting array: - If both the first and last characters of `s` are vowels, reverse (mirror) the inner substring o

You are given a data structure consisting of nested maps (dictionaries/JSON objects). The data has the notion of “Level 1” and “Level 2” (corresponding to two specific nesting layers). Compute and ou

Implement a bus boarding simulator with regular riders, priority boarding, and wheelchair constraints. Design and implement functions/classes to support the following (progressive) requirements: ##

Given a string `expr` representing an arithmetic expression, evaluate it. **Rules** - `expr` contains non-negative integers, operators `+ - * /`, parentheses `(` `)`, and spaces. - Operator precedenc

Given an encoded string `s` with the rule: - The encoding format is `k[encoded_string]`, meaning `encoded_string` is repeated exactly `k` times. - `k` is a positive integer. - `encoded_string` may it

## Problem: In-Memory Database with Backup and Restore Design and implement a simplified in-memory database that supports read/write on key-values and also supports **backup** and **restore**. ### D

Write a program that reads a password byte by byte from a file. The first password is always valid, and encountering a duplicated index indicates the start of the second password. Ensure the program c

Design a system to calculate average time for specific operations with the following functionalities: 1. Record start time of an operation; 2. Record end time; 3. Query average time for specific opera

Design a password management system with the following functionalities: 1. Create password groups; 2. Store and update passwords within groups; 3. Query expired passwords. Provide detailed API design.

Implement a banking system with the following capabilities: 1. `transfer`: Implement the money transfer functionality. 2. `schedule payment`: Implement the scheduled payment feature, allowing users t

### Problem Overview - Given a forest array and a start index bird, output the indices of sticks the bird collects in order while alternating right then left until the total length is at least 100. -

### Problem Overview - Simulate a bubble-popping game on a 2D grid and return the final grid after all operations. - Inputs: a grid of bubble colors and a list of pop coordinates; Output: the grid sta

### Problem Overview - Process coloring updates on a balloon queue and after each, report the number of adjacent same-color pairs. - Input: length (positions 0..length-1) and queries of (index, color)