Instacart Software Engineer Interview Questions

I recently completed the interview process at Instacart (Toronto), starting with an online assessment, followed by a recruiter call, two coding rounds, a system design round, and a behavioral intervie

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 You are given a hand of exactly 3 cards, each as `(rank, suit)` where rank is 2-14 (14=Ace) and suit is one of `H/D/C/S`. Evaluate the hand and return its category. Categories in descending order: 1. `STRAIGHT_FLUSH` — three consecutive ranks, same suit 2. `THREE_OF_A_KIND` — all same rank 3. `STRAIGHT` — three consecutive ranks, mixed suits 4. `FLUSH` — same suit, not consecutive 5. `PAIR` — exactly two same rank 6. `HIGH_CARD` — none of the above ```python from typing import NamedTuple class Card(NamedTuple): rank: int # 2-14 suit: str # H/D/C/S def evaluate_hand(cards: list[Card]) -> str: ... ``` ``` Input: [(10,'H'),(11,'H'),(12,'H')] -> "STRAIGHT_FLUSH" Input: [(7,'H'),(7,'D'),(7,'C')] -> "THREE_OF_A_KIND" Input: [(2,'H'),(5,'D'),(3,'C')] -> "STRAIGHT" Input: [(9,'H'),(3,'H'),(6,'H')] -> "FLUSH" Input: [(9,'H'),(9,'D'),(2,'C')] -> "PAIR" Input: [(2,'H'),(7,'D'),(K,'C')] -> "HIGH_CARD" ``` ## Follow-ups 1. Ace can be low (A-2-3) or high (Q-K-A). How do you handle both cases in your straight detection? 2. Given two hands of the same category, how do you compare them to determine a winner (tiebreaker logic)? 3. Extend to 5-card poker hands. How does your architecture change? 4. How would you generate all possible 3-card hands from a standard 52-card deck and count hands per category?

## Problem You have a transit log of tap-in and tap-out events. Each event is `[customer_id, station, timestamp]`. A trip is completed when a customer taps in at station A then taps out at station B. Compute the average travel time for each unique `(start_station, end_station)` pair. ```python def average_travel_time( events: list[tuple[str, str, int]] # (customer_id, station, timestamp) ) -> dict[tuple[str,str], float]: ... ``` ``` Events: ("C1", "A", 100), ("C2", "B", 110), ("C1", "C", 150), ("C2", "D", 200), ("C1", "A", 300), ("C1", "C", 360) Trips: C1: A->C (50), A->C (60) => avg 55.0 C2: B->D (90) => avg 90.0 Output: {("A","C"): 55.0, ("B","D"): 90.0} ``` ## Follow-ups 1. Your implementation must handle events arriving out of chronological order. How does this affect your approach? 2. What happens if a customer taps in twice without tapping out? How do you handle malformed data? 3. The transit authority wants a live dashboard: as events stream in, update averages without recomputing from scratch. How do you maintain a running average? 4. A customer makes 10,000 trips on the same route. How do you keep your running average numerically stable (avoid floating point drift)?

## 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 A password was encoded with the following steps applied in order: 1. Reverse the string. 2. Replace each letter with the letter `k` positions forward in the alphabet (wrapping: z+1=a). `k` is given. 3. Swap each pair of adjacent characters (swap index 0-1, 2-3, etc.; if odd length, last char stays). Given the encoded string and `k`, return the original password. ```python def decode_password(encoded: str, k: int) -> str: ... ``` ``` Original: "hello" Step 1 (reverse): "olleh" Step 2 (shift +2): "qnnhj" Step 3 (swap pairs): "nqnjh" Encoded: "nqnjh" decode_password("nqnjh", 2) -> "hello" ``` ## Follow-ups 1. Walk through each decode step in reverse order. What is the inverse of each operation? 2. What edge cases matter: `k=0`, `k=26`, an empty string, non-letter characters? 3. If the encoding scheme had 10 steps, how would you structure your decoder to make it easy to add/remove steps? 4. This encoding is symmetric for step 3 (swap is its own inverse). How does that simplify your decode logic?

## 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?

## Problem Evaluate a mathematical or logical expression string, handling operator precedence and parentheses. Classic stack-based parsing problem. ## Likely LeetCode equivalent No direct match. ## Tags stack, strings, parsing, coding

## Problem Given a sequence of integers, determine if it has a repeating pattern of period `p` (for any p from 1 to n/2). If yes, return the shortest repeating unit and the next `k` predicted elements. If no pattern exists, return an empty list. ```python def find_pattern( sequence: list[int], k: int ) -> tuple[list[int], list[int]]: """Returns (pattern_unit, next_k_elements). pattern_unit=[] if none found.""" ... ``` ``` Input: sequence=[1,2,3,1,2,3,1,2,3], k=4 Pattern found: [1,2,3] (period 3) Next 4: [1,2,3,1] Output: ([1,2,3], [1,2,3,1]) Input: sequence=[1,2,3,4], k=2 No repeating pattern. Output: ([], []) Input: sequence=[5,5,5,5], k=3 Pattern: [5] (period 1) Output: ([5], [5,5,5]) ``` ## Follow-ups 1. How do you verify a candidate period `p`? What is the time complexity of checking all periods? 2. What if the sequence is only approximately periodic (some elements differ by at most 1)? How do you define "close enough"? 3. Can you use the KMP failure function to detect periodicity efficiently? Describe how. 4. If the sequence is a time series of stock prices, what limitations does strict periodicity detection have, and what alternatives would you use?

## Problem Implement a key-value store that supports get and set operations with timestamps, returning the value at or before a given time. ## Likely LeetCode equivalent LC 981 - time-based-key-value-store ## Tags hash_table, binary_search, design, coding

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