Instacart software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
processingTime and an arrivalTime. Workers process one job at a time. When a...Input: Listtransaction_id, cost,...Input: Graph (nodes and edges)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:null.null.s with TTL d, return the value only when timestamp < s + d. The expiration boundary is exclusive.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 signatureTimestampedCache() — 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.{
"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]
]
}[null, null, null, "4.49", null, "4.99", null, "4.79"]
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:{
"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]
]
}[null, null, "in_stock", null, null, "limited", null, null, "in_stock"]
12 + 3 = 15; the older unlimited-lifetime value at time 5 does not reappear. The version at time 18 restores availability.Constraints:200,000 public method calls; at most 200,000 distinct stored versions across all keys.1 through 100; values are never null.0 <= timestamp <= 10^12.None or an integer satisfying 1 <= ttl <= 10^12.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?Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free