Instacart software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
pattern and a log string, both consisting of uppercase letters and the wildcard character *. The * wildcard matches...Input: StringprocessingTime 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?['apple', 'banana', 'apple', 'orange', 'banana', 'banana']), write a function most_frequent_item(cart: List[str]) -> Tuple[str, int] that returns the item that appears most frequently in the cart and its count. If multiple items have the same count, return any one of them.most_frequent_item(cart: List[str]) -> Tuple[str, int]['apple', 'banana', 'apple', 'orange', 'banana', 'banana'] ('banana', 3) ['grape', 'apple', 'grape', 'orange', 'apple'] ('grape', 2) n deliveries and a total available time T, return the maximum number of deliveries that can be completed.def max_deliveries(delivery_times: List[int], total_time: int) -> int:, total_time = 7, total_time = 5weights, where each value represents the weight of a grocery item. The total weight of any batch cannot exceed a limit maxWeight. Write a function that finds the maximum number of items you can include in a single batch while respecting the maxWeight. Key constraints are that the items must be taken in order from the weights array.def max_items_in_batch(weights: List[int], maxWeight: int) -> int:weights = [2, 3, 5, 2, 8], maxWeight = 10 4 [2, 3, 5], and one additional item with weight 2 which totals 10 (i.e., 2 + 3 + 5 = 10).weights = [1, 1, 1, 1, 1], maxWeight = 3 3 1 each totaling 3.1 <= len(weights) <= 10001 <= weights[i] <= 1001 <= maxWeight <= 10001 and open paths by 0, write a function to find the shortest path from the starting point to the destination. The function should return the minimum number of steps needed to reach the destination, or -1 if the destination cannot be reached.def shortest_delivery_path(store: List[List[int]], start: Tuple[int, int], destination: Tuple[int, int]) -> int: store = [[0,0,0],[0,1,0],[0,0,0]], start = (0, 0), destination = (2, 2) 4 [(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)], with 4 steps.store = [[0,1],[0,0]], start = (0, 0), destination = (1, 1) 2 [(0,0) -> (1,0) -> (1,1)], with 2 steps.1 <= len(store) <= 100 1 <= len(store[i]) <= 100 deliveryPoints representing the sequence of delivery locations and an integer maxStops which represents the maximum number of stops a shopper can make, write a function that returns the shortest route for the shopper that includes all the delivery points up to maxStops. Each delivery point has a distance associated with it. You can assume that the list is already sorted by the distance from the store. def shortest_delivery_route(deliveryPoints: List[int], maxStops: int) -> List[int]:deliveryPoints = [2, 3, 5, 8, 10], maxStops = 3[2, 3, 5] deliveryPoints = [1, 4, 6, 7], maxStops = 2[1, 4] 1 <= len(deliveryPoints) <= 1001 <= deliveryPoints[i] <= 10^61 <= maxStops <= len(deliveryPoints)items that represent customer orders, each an item in a string format, and an integer k, write a function to return the k most frequently purchased items in order of their frequency. If two items have the same frequency, return them in the order they first appeared in the list.def top_k_frequent(items: List[str], k: int) -> List[str]:items = ['apple', 'banana', 'apple', 'orange', 'banana', 'banana'], k = 2['banana', 'apple']items = ['carrot', 'carrot', 'potato', 'onion', 'carrot', 'potato'], k = 1['carrot']1 <= len(items) <= 10^41 <= k <= len(items)def longest_consecutive_items(items: List[int]) -> int:[1, 3, 2, 4, 5] 5 1, 2, 3, 4, 5 form a consecutive subarray.[10, 2, 3, 11, 4, 5, 1] 5 1, 2, 3, 4, 5 form a consecutive subarray. 1 <= len(items) <= 1000 10^6.Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free