Instacart logo

Instacart Software Engineer System Design Questions

14 practice questions for Instacart Software Engineer 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

No verified questions yet for Instacart.

system design Medium binary search #1

1. Design RetailerCatalogHistory — a timestamped store for retailer-specific product availability


Background
Instacart displays retailer-specific prices and availability, and investigating a historical shopping session requires knowing what catalog state was visible at a particular time. Implement an in-memory class that models this historical lookup. This exercise adapts the timestamped key-value store reported in an Instacart interview; the catalog schema, expiration rules, and listing API are extensions for this practice problem.
Requirements
1. Identify a product by (retailer_id, sku). Store timestamped versions containing a price in integer cents and an available quantity. Different retailers may have different versions of the same SKU.
2. Accept mutations in any timestamp order. A mutation at an existing timestamp replaces the previous mutation at that timestamp, including a deletion. Mutations affect subsequent queries immediately; queries are evaluated against the currently stored history.
3. A lookup at as_of selects the mutation with the greatest timestamp less than or equal to as_of. Return None if no such mutation exists or if the selected mutation is a deletion.
4. A product version may have a positive time-to-live. A version written at timestamp with ttl_seconds = t is visible only while as_of < timestamp + t. An expired selected version returns None; never fall back to an older version. A missing TTL means no expiration. A quantity of zero is still a valid, retrievable product version.
5. Deleting a product records a timestamped tombstone rather than erasing its history. A deletion remains effective until superseded by a later mutation. An out-of-order write before the tombstone does not resurrect the product after the deletion timestamp.
6. Listing a retailer's available products returns the visible versions whose quantity is greater than zero, sorted by SKU in ascending lexicographic order. Returned snapshots must be immutable or detached from internal state.
Class API
  • RetailerCatalogHistory() — construct an empty store.

  • set_product(retailer_id: str, sku: str, timestamp: int, price_cents: int, quantity: int, ttl_seconds: Optional[int] = None) -> None — insert or replace a timestamped product version.

  • delete_product(retailer_id: str, sku: str, timestamp: int) -> None — insert or replace a timestamped deletion, including for a previously unknown product.

  • get_product(retailer_id: str, sku: str, as_of: int) -> Optional[ProductSnapshot] — retrieve the visible version at the requested time.

  • list_available(retailer_id: str, as_of: int) -> List[ProductSnapshot] — retrieve visible, positive-quantity products in SKU order.

  • ProductSnapshot has typed fields sku: str, price_cents: int, and quantity: int.


Example 1:
Input sequence:
catalog = RetailerCatalogHistory()
catalog.set_product("r1", "milk", 10, 499, 6)
catalog.set_product("r1", "milk", 20, 549, 2, 5)
catalog.get_product("r1", "milk", 19)
catalog.get_product("r1", "milk", 24)
catalog.get_product("r1", "milk", 25)
catalog.get_product("r1", "milk", 9)

Output for the four queries, with snapshots serialized as JSON:
[
  {"sku": "milk", "price_cents": 499, "quantity": 6},
  {"sku": "milk", "price_cents": 549, "quantity": 2},
  null,
  null
]

Explanation: At time 19, the mutation at 10 is selected. At time 24, the mutation at 20 is selected and has not expired. Its expiration boundary is 20 + 5 = 25, so the lookup at 25 returns null without reviving the version at 10. No version exists at time 9.
Example 2:
Input sequence:
catalog = RetailerCatalogHistory()
catalog.set_product("r1", "milk", 10, 499, 6)
catalog.delete_product("r1", "milk", 30)
catalog.set_product("r1", "milk", 20, 529, 3)
catalog.set_product("r1", "apples", 15, 199, 4)
catalog.set_product("r1", "bread", 15, 399, 0)
catalog.set_product("r2", "milk", 10, 459, 8)
catalog.list_available("r1", 25)
catalog.get_product("r1", "milk", 35)
catalog.set_product("r1", "milk", 30, 559, 1)
catalog.list_available("r1", 35)
catalog.get_product("r2", "milk", 35)

Output for the four queries:
[
  [
    {"sku": "apples", "price_cents": 199, "quantity": 4},
    {"sku": "milk", "price_cents": 529, "quantity": 3}
  ],
  null,
  [
    {"sku": "apples", "price_cents": 199, "quantity": 4},
    {"sku": "milk", "price_cents": 559, "quantity": 1}
  ],
  {"sku": "milk", "price_cents": 459, "quantity": 8}
]

Explanation: The out-of-order write at 20 is visible at 25, but the tombstone at 30 initially hides milk at 35. Writing a product at timestamp 30 replaces that tombstone. Bread is excluded from listings because its quantity is zero. Retailer r2 is independent.
Constraints
  • At most 100,000 total method calls and 100,000 distinct product keys; at most 2,000 distinct mutation timestamps per product key.

  • Retailer IDs and SKUs are nonempty ASCII strings of length at most 64; all inputs satisfy the documented bounds.

  • Timestamps and query times are integer seconds in [0, 10^12]; prices and quantities are integers in [0, 10^9]; TTL is either absent or an integer in [1, 10^9].

  • Execution is single-threaded. No persistence, networking, historical pruning, or real wall-clock access is required.

  • Point lookups must use logarithmic search within a product's history. Out-of-order insertion may take linear time in that history; listing may inspect every known SKU for the requested retailer.
Want to practise this one?
Create a free account to open the full question and practise Instacart questions with AI.
Sign up free

Related Instacart Software Engineer interview prep

Start practicing Instacart questions

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

Get Started Free