Food Delivery System (Multi-Level Coding)

A multi-part onsite coding round around a food / restaurant delivery system. Early levels exercise hash-map plumbing (registering restaurants, dishes, orders); later levels add binary search on price history, shortest-route variants, and a knapsack-flavored final follow-up. The interviewer-defined level count varies — finishing levels 1–3 cleanly is the realistic bar. Food Delivery System Problem Summary You need to build a food delivery system. This system manages restaurants, menus, and user orders. It helps users find the cheapest food and the nearest restaurants. Later, you will add features to track order statistics and rank the best orders. You will build this step-by-step. Part 1: Finding Food The Task You are given a user's location, a list of restaurants with their coordinates, and a menu of items with prices. You need to write a FoodDeliverySystem class with two main methods: Find the cheapest: Locate the restaurant that sells a specific item for the lowest price. Find the nearest: Locate the closest restaurant that sells a specific item. class FoodDeliverySystem: def __init__(self, user_x: float, user_y: float, restaurants: list[tuple[int, float, float]], menu: list[tuple[int, str, float]]): """ Setup the system. Args: user_x: User's x-coordinate user_y: User's y-coordinate restaurants: List of (restaurant_id, x, y) menu: List of (restaurant_id, item_name, price) """ pass def find_cheapest(self, item_name: str) -> tuple[int, float] | None: """ Find the restaurant with the lowest price for this item. Args: item_name: The name of the food (e.g., "Burger") Returns: A tuple of (restaurant_id, price). Return None if no one sells it. """ pass def find_nearest(self, item_name: str) -> tuple[int, float] | None: """ Find the closest restaurant that sells this item. Args: item_name: The name of the food Returns: A tuple of (restaurant_id, distance). Return None if no one sells it. Notes: - Use Euclidean distance from the user. """ pass Example Usage user_x, user_y = 3.0, 1.5 restaurants = [ (1, 4.5, 6.8), (2, 3.11, 8.89), (3, 34.5, 6.2), (4, 21.4, 7.23) ] menu = [ (1, "Burger", 8), (1, "Pizza", 10), (2, "Burger", 6), (2, "Sushi", 15), (3, "Burger", 9), (3, "Pizza", 7), (4, "Sushi", 12) ] system = FoodDeliverySystem(user_x, user_y, restaurants, menu) print(system.find_cheapest("Burger")) # (2, 6) — Restaurant 2 is cheapest ($6) print(system.find_cheapest("Sushi")) # (4, 12) print(system.find_cheapest("Taco")) # None print(system.find_nearest("Burger")) # (1, ...) — Restaurant 1 is closest print(system.find_nearest("Sushi")) # (2, ...) — Restaurant 2 is closer than 4 Part 1 Solution and Explanation To solve this efficiently, we organize the data during the setup (__init__). We store restaurant coordinates in a dictionary for easy lookup. We map every item_name to a list of restaurants that sell it. When we search: Cheapest: We look at the list of restaurants for that item and pick the one with the minimum price. Nearest: We look at the list of restaurants for that item, calculate the distance for each, and pick the minimum distance. import math class FoodDeliverySystem: def __init__(self, user_x: float, user_y: float, restaurants: list[tuple[int, float, float]], menu: list[tuple[int, str, float]]): self.user_x = user_x self.user_y = user_y # restaurant_id -> (x, y) self.restaurant_coords = {} for r_id, x, y in restaurants: self.restaurant_coords[r_id] = (x, y) # item_name -> [(restaurant_id, price)] self.item_to_restaurants = {} for r_id, item_name, price in menu: if item_name not in self.item_to_restaurants: self.item_to_restaurants[item_name] = [] self.item_to_restaurants[item_name].append((r_id, price)) def _distance(self, r_id: int) -> float: x, y = self.restaurant_coords[r_id] return math.sqrt((x - self.user_x) ** 2 + (y - self.user_y) ** 2) def find_cheapest(self, item_name: str) -> tuple[int, float] | None: if item_name not in self.item_to_restaurants: return None entries = self.item_to_restaurants[item_name] # Find entry with lowest price best = min(entries, key=lambda e: e[1]) return best def find_nearest(self, item_name: str) -> tuple[int, float] | None: if item_name not in self.item_to_restaurants: return None entries = self.item_to_restaurants[item_name] best_r_id = None best_dist = float('inf') for r_id, _ in entries: dist = self._distance(r_id) if dist < best_dist: best_dist = dist best_r_id = r_id return (best_r_id, best_dist) Complexity Analysis: Method Time Space __init__ O(M) O(M) find_cheapest O(K) O(1) find_nearest O(K) O(1) Here, M is the total number of items in the menu, and K is the number of restaurants selling the specific item you asked for. Part 2: Order Statistics The Task Interviewer: "Now we have order data coming in. We need to calculate statistics for a specific time range." You receive a list of orders. Each order has an ID, price, and timestamp. You must write a function to calculate the total revenue and count the orders within a start and end time. def load_orders(self, orders: list[tuple[int, int, float, int]]) -> None: """ Save order data into the system. Args: orders: List of (order_id, item_id, total_price, timestamp) """ pass def get_order_analytics(self, start: int, end: int) -> tuple[int, float, float]: """ Calculate stats for the time range [start, end]. Args: start: Start timestamp end: End timestamp Returns: (order_count, total_revenue, average_order_value) Notes: - order_count is the number of unique order IDs. - total_revenue is the sum of all prices. """ pass Example Usage orders = [ (1, 101, 10.0, 1), # Order 1: $10, time 1 (1, 102, 5.0, 1), # Order 1: $5, time 1 (same order, different item) (2, 101, 30.0, 3), # Order 2: $30, time 3 (3, 103, 20.0, 5), # Order 3: $20, time 5 (4, 101, 15.0, 8), # Order 4: $15, time 8 ] system.load_orders(orders) print(system.get_order_analytics(1, 5)) # (3, 65.0, 21.67) # 3 orders (1, 2, 3). Total = 10+5+30+20 = 65. Avg = 65/3. print(system.get_order_analytics(10, 20)) # (0, 0.0, 0.0) Part 2 Solution and Explanation We store the orders in a dictionary (HashMap). The key is the order_id. The value stores the timestamp and the total cost of that order. When we need analytics: We loop through all the stored orders. We check if the order's timestamp is inside the requested range. If it is, we add it to our totals. class FoodDeliverySystem: # ... (Part 1 code) ... def load_orders(self, orders: list[tuple[int, int, float, int]]) -> None: # order_id -> { "timestamp": int, "total": float } self.orders = {} for order_id, item_id, total_price, timestamp in orders: if order_id not in self.orders: self.orders[order_id] = {"timestamp": timestamp, "total": 0.0} self.orders[order_id]["total"] += total_price def get_order_analytics(self, start: int, end: int) -> tuple[int, float, float]: count = 0 total_revenue = 0.0 for order_id, data in self.orders.items(): if start <= data["timestamp"] <= end: count += 1 total_revenue += data["total"] if count == 0: return (0, 0.0, 0.0) return (count, total_revenue, total_revenue / count) Complexity Analysis: Method Time Space load_orders O(L) O(N) get_order_analytics O(N) O(1) Here, L is the number of line items (rows in the input), and N is the number of unique orders. Optimization Note: If we run this query very often, it is slow to loop through everything (O(N)). Instead, we could sort the orders by time. Then we can use Binary Search to find the start and end of the range quickly. Part 3: Best Orders by Revenue The Task Interviewer: "Now, find the top K orders with the highest total revenue in a specific time range." def top_k_orders(self, start: int, end: int, k: int) -> list[tuple[int, float]]: """ Find the top K orders by revenue in the time range [start, end]. Returns: A list of (order_id, total_revenue) sorted by revenue (highest first). """ pass Example Usage # Using the same orders from Part 2 print(system.top_k_orders(1, 8, 2)) # [(2, 30.0), (3, 20.0)] # Order 2 is #1 ($30), Order 3 is #2 ($20) Part 3 Solution and Explanation There are two main ways to solve this. Approach 1: Simple Sorting Collect all valid orders, sort them by price, and return the top K. Time: O(N log N) Pros: Easy to write. Cons: Slower if N is very large. Approach 2: Min-Heap (Better) We use a Min-Heap to keep track of the top K largest orders. Iterate through orders. If the heap has fewer than K items, push the order onto it. If the heap is full and the current order is bigger than the smallest one in the heap, replace the smallest one. Time: O(N log K) — This is faster because K is usually much smaller than N. import heapq def top_k_orders(self, start: int, end: int, k: int) -> list[tuple[int, float]]: min_heap = [] # Stores (total_revenue, order_id) for order_id, data in self.orders.items(): if start <= data["timestamp"] <= end: # If heap is not full, add it if len(min_heap) < k: heapq.heappush(min_heap, (data["total"], order_id)) # If heap is full, check if current is bigger than smallest in heap elif data["total"] > min_heap[0][0]: heapq.heapreplace(min_heap, (data["total"], order_id)) # Sort the result highest to lowest result = [(order_id, total) for total, order_id in min_heap] result.sort(key=lambda x: x[1], reverse=True) return result Part 4: Most Popular Items (Bonus) The Task Interviewer: "One more — find the top K items by total sales volume across all orders in a time range." This is different from Part 3. In Part 3, we looked at whole orders. Now, we need to look at specific items (like "Burger" or "Item 101"). def top_k_items(self, start: int, end: int, k: int) -> list[tuple[int, float]]: """ Find the top K items by total sales volume. """ pass Example Usage print(system.top_k_items(1, 8, 2)) # [(101, 55.0), (103, 20.0)] # Item 101 was sold for $10, $30, and $15. Total = $55. Part 4 Solution and Explanation To solve this, we need to save the raw line items in load_orders so we can see individual item details later. Filter items that fall in the time range. Add up the sales for each item ID using a dictionary. Use a Min-Heap (like Part 3) to find the top K items. import heapq from collections import defaultdict class FoodDeliverySystem: # ... (Parts 1-3 code) ... def load_orders(self, orders: list[tuple[int, int, float, int]]) -> None: # Keep raw items for item-level queries self.line_items = orders # Keep aggregated orders for Part 2 & 3 self.orders = {} for order_id, item_id, total_price, timestamp in orders: if order_id not in self.orders: self.orders[order_id] = {"timestamp": timestamp, "total": 0.0} self.orders[order_id]["total"] += total_price def top_k_items(self, start: int, end: int, k: int) -> list[tuple[int, float]]: # Calculate total volume per item in the time range item_volume = defaultdict(float) for order_id, item_id, total_price, timestamp in self.line_items: if start <= timestamp <= end: item_volume[item_id] += total_price # Use min-heap to find top K min_heap = [] for item_id, volume in item_volume.items(): if len(min_heap) < k: heapq.heappush(min_heap, (volume, item_id)) elif volume > min_heap[0][0]: heapq.heapreplace(min_heap, (volume, item_id)) result = [(item_id, volume) for volume, item_id in min_heap] result.sort(key=lambda x: x[1], reverse=True) return result Complexity Analysis: Method Time Space top_k_items O(L + I log K) O(I) Here, L is the total line items, and I is the number of distinct items found in that time range. Interview Discussion Points Preprocessing vs. Calculating on the fly: Should we sort the data when we load it (__init__) or when we search? Example: If we pre-sort restaurants by price for every item, find_cheapest becomes O(1) (instant). But loading data takes longer. Heap vs. Sort: Heap: Best when K is small (e.g., "Top 5 out of 1 million"). Complexity is O(N log K). Sort: Okay when K is close to N. Complexity is O(N log N). Real-time Scaling: If orders come in every second, looping through all of them is too slow. We might need "Sliding Windows" or specialized databases to handle the analytics. Advanced Variant (Knapsack Problem): The interviewer might ask: "Given a budget of $20, what is the best combination of items I can buy?" This turns the problem into a "Knapsack Problem," which is a classic dynamic programming challenge. Big-O Complexity Cheat Sheet Method Time Space find_cheapest O(R) O(1) find_nearest O(R) O(1) get_order_analytics O(N) O(1) top_k_orders (heap) O(N log K) O(K) top_k_items (heap) O(L + I log K) O(I) Legend: R = restaurants per item N = total orders K = Top-K parameter (e.g., top 10) L = total line items I = distinct items Candidate-Report Notes For getAveragePrice, store per-dish (timestamp, price) in a sorted list; binary search both endpoints and compute a prefix-sum over price (or a Fenwick if mutations are allowed). The shortest-route follow-up is usually Dijkstra on an item-and-restaurant bipartite graph; for the "all items" variant, the canonical reduction is a TSP-flavored bitmask DP — say so verbally, then implement only as far as the interviewer demands. The last knapsack-flavored follow-up is the same recipe as Mining Block: state DP / 0-1 knapsack as the optimal answer, fall back to a ratio greedy if the interviewer pushes for "production realism." No starter scaffolding. Spend 5 minutes on the data model up front; rebuilding mid-round is the most common time sink. Preparation Drill the getAveragePrice-style "sorted history + binary search on time window" pattern; it shows up in food delivery, in cash-flow ledger problems, and in OA-level "return average X over time range Y" prompts. Practice writing the level-1 / level-2 plumbing under 12 minutes total so the latter levels actually get attention. Have the bitmask-DP one-liner ready for the "deliver all items" follow-up even if you only sketch it: dp[mask][i] = min cost ending at restaurant i with mask of items collected.