Instacart logo

Instacart Hard Interview Questions

3 hard-level practice questions for Instacart technical interviews

Instacart software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.

Software Engineer Backend Engineer Frontend Engineer Full Stack Engineer Mobile Engineer Data Engineer Data Scientist ML Engineer DevOps Engineer DevOps Engineer Product Manager SRE Security Engineer Engineering Manager Data Analyst UX/UI Designer QA Engineer
coding Hard Verified Question #1

1. Minimum Workers For Average Task Time


Category: Algorithm coding problem
A manufacturing plant has workers processing jobs. Each job has a processingTime and an arrivalTime. Workers process one job at a time. When a...
Input: List
Output: Integer
Want to practise this one?
Create a free account to open the full question and practise Instacart questions with AI.
Sign up free
coding Hard Verified Question #2

2. Analytics Pivot Query


Category: Graph coding problem
An e-commerce analytics platform stores transaction records in a data warehouse. Each record contains at least the columns transaction_id, cost,...
Input: Graph (nodes and edges)
Output: Computed result
coding Hard tree #1

1. [Caching] — Query an out-of-order timestamped cache with expiration and deletions


Background
Instacart's storefront needs retailer-specific product information, including prices and availability. A timestamped cache can support historical debugging when updates arrive late or are corrected; this exercise models that requirement rather than claiming to reproduce Instacart's production architecture.
Problem statement
Implement an online timestamped key-value cache. Each key has a history of versions indexed by an integer timestamp. Calls may arrive in any order, including writes whose timestamps are earlier than previously inserted versions. You cannot inspect future calls or preprocess the complete operation sequence.
A set operation inserts a value at a timestamp, optionally with a time-to-live. A delete operation inserts a tombstone at a timestamp; it does not physically remove older versions. Either operation replaces any existing version for the same key at exactly the same timestamp.
For get(key, timestamp), first find the version with the greatest timestamp less than or equal to the query timestamp:
  • If no such version exists, return null.

  • If that version is a tombstone, return null.

  • If it is a value written at time s with TTL d, return the value only when timestamp < s + d. The expiration boundary is exclusive.

  • Otherwise, return its value.


An expired version or tombstone never causes an older value to reappear. A later version can make the key available again. Late writes change the results of subsequent historical queries; previously returned answers are not revised.
Support each public operation in expected O(log(v + 1)) time or better, where v is the number of distinct timestamps stored for that key. Use O(N) total space for N stored versions. A sorted array with linear-time insertion does not meet the requirement. Implement the ordered structure yourself using only the language's standard library.
Function or class signature
  • TimestampedCache() — construct an empty cache.

  • set(key: str, value: str, timestamp: int, ttl: int | None = None) -> None — insert or replace a value version; None means no expiration.

  • delete(key: str, timestamp: int) -> None — insert or replace a tombstone, even if the key has never been written.

  • get(key: str, timestamp: int) -> str | None — retrieve the value using the rules above.


Example 1:
Input:
{
  "operations": [
    ["set", "retailer17:milk:price", "4.99", 20, null],
    ["set", "retailer17:milk:price", "4.49", 10, 5],
    ["get", "retailer17:milk:price", 9],
    ["get", "retailer17:milk:price", 12],
    ["get", "retailer17:milk:price", 15],
    ["get", "retailer17:milk:price", 25],
    ["set", "retailer17:milk:price", "4.79", 14, null],
    ["get", "retailer17:milk:price", 15]
  ]
}

Output:
[null, null, null, "4.49", null, "4.99", null, "4.79"]

Explanation: The value at time 10 expires at 10 + 5 = 15. The version at time 20 does not apply to earlier queries. After a late write at time 14, the query at time 15 selects that new historical version instead. Outputs for writes are null.
Example 2:
Input:
{
  "operations": [
    ["set", "retailer17:eggs:availability", "in_stock", 5, null],
    ["delete", "retailer17:eggs:availability", 12],
    ["get", "retailer17:eggs:availability", 11],
    ["get", "retailer17:eggs:availability", 12],
    ["set", "retailer17:eggs:availability", "limited", 12, 3],
    ["get", "retailer17:eggs:availability", 14],
    ["get", "retailer17:eggs:availability", 15],
    ["set", "retailer17:eggs:availability", "in_stock", 18, null],
    ["get", "retailer17:eggs:availability", 18]
  ]
}

Output:
[null, null, "in_stock", null, null, "limited", null, null, "in_stock"]

Explanation: The write at time 12 replaces the tombstone at the same timestamp. Its value expires at 12 + 3 = 15; the older unlimited-lifetime value at time 5 does not reappear. The version at time 18 restores availability.
Constraints:
  • At most 200,000 public method calls; at most 200,000 distinct stored versions across all keys.

  • Keys and values are strings of length 1 through 100; values are never null.

  • 0 <= timestamp <= 10^12.

  • TTL is either None or an integer satisfying 1 <= ttl <= 10^12.

  • Operations are single-threaded. Historical queries may use any valid timestamp, including times earlier than all writes or later than all writes.


Follow-up:
Add compact(cutoff: int) -> None. After compaction, queries and writes earlier than cutoff are forbidden, but all permitted future operations must behave exactly as before. Which version preceding the cutoff must be retained, and how would you remove older nodes efficiently?
Want to practise this one?
Create a free account to open the full question and practise Instacart questions with AI.
Sign up free

Start practicing Instacart questions

Sign up for free to access walkthroughs, AI-generated questions, and more.

Get Started Free