# Solution Alignment The improved prompt asks for a structured answer that states assumptions, covers edge cases, and explains trade-offs. The answer below preserves the original solution content while making the expected interview coverage explicit. ## Interview Framing - Start by restating the goal and the assumptions you need. - Work through the main approach in the same order as the prompt. - Call out trade-offs, edge cases, and validation steps before finalizing the recommendation. ## Detailed Answer This is a data-aggregation and ranking exercise. Model the inputs explicitly, then solve each part with the right data structure. **Data model** - `Restaurant { id, location: (lat, lng), menu: Map<itemId, price> }` - `Order { id, restaurantId, items: List<(itemId, qty)>, total, timestamp }` --- **Part 1 — Cheapest restaurant and nearest restaurant** The desired order is a set of menu items (optionally with quantities). For each restaurant, check it can supply every requested item; if so its order cost is `sum(price[item] * qty)`. Track the minimum. ```python import math def cheapest_and_nearest(restaurants, wanted_items, user_loc): best_cost, cheapest = math.inf, None best_dist, nearest = math.inf, None for r in restaurants: # cheapest: must offer every requested item if all(item in r.menu for item, _ in wanted_items): cost = sum(r.menu[item] * qty for item, qty in wanted_items) if cost < best_cost: best_cost, cheapest = cost, r # nearest: independent of menu d = haversine(user_loc, r.location) if d < best_dist: best_dist, nearest = d, r return cheapest, nearest def haversine(a, b): R = 6371.0 # km lat1, lng1 = map(math.radians, a) lat2, lng2 = map(math.radians, b) dlat, dlng = lat2 - lat1, lng2 - lng1 h = math.sin(dlat/2)**2 + math.cos(lat1)*math.cos(lat2)*math.sin(dlng/2)**2 return 2 * R * math.asin(math.sqrt(h)) ``` Use the haversine (great-circle) distance for real lat/lng; if coordinates are planar, plain Euclidean distance is fine. Both scans are O(R). If "nearest" must be answered repeatedly for many user locations, preprocess restaurant locations into a spatial index (k-d tree / geohash buckets) to get O(log R) or near-constant lookups instead of O(R) per query. --- **Part 2 — Time-window aggregates** Filter orders whose timestamp falls in `[start, end)`, then aggregate. Compute each order's total from item prices if it isn't pre-stored. ```python def window_stats(orders, prices, start, end): total, count = 0.0, 0 for o in orders: if start <= o.timestamp < end: order_total = sum(prices[item] * qty for item, qty in o.items) total += order_total count += 1 avg = total / count if count else 0.0 return {"total": total, "count": count, "avg": avg} ``` This is O(N) over the orders in the window. If orders are kept sorted by timestamp, binary-search the window bounds to scan only the relevant slice. For many repeated window queries, a prefix-sum array over (total, count) by time bucket lets you answer each window in O(1)/O(log N). --- **Part 3 — Top-K orders and Top-K menu items** Within the same window, (a) rank orders by total price, and (b) rank menu items by units sold. For Top-K, a min-heap of size K is the standard answer: O(N log K), better than sorting the whole list (O(N log N)) when K << N. ```python import heapq from collections import defaultdict def top_k(orders, prices, start, end, k): item_volume = defaultdict(int) order_heap = [] # min-heap of (total, order_id) for o in orders: if not (start <= o.timestamp < end): continue order_total = sum(prices[item] * qty for item, qty in o.items) if len(order_heap) < k: heapq.heappush(order_heap, (order_total, o.id)) elif order_total > order_heap[0][0]: heapq.heapreplace(order_heap, (order_total, o.id)) for item, qty in o.items: item_volume[item] += qty top_orders = sorted(order_heap, reverse=True) # K largest, desc top_items = heapq.nlargest(k, item_volume.items(), key=lambda kv: kv[1]) # by volume return top_orders, top_items ``` Top-K orders: maintain a size-K min-heap; pop/replace when a larger total arrives → O(N log K). Top-K menu items: aggregate per-item volume in a hash map during the same pass, then take the K largest with `heapq.nlargest` → O(M log K) over M distinct items. The whole part is one linear pass plus the heap work. --- **Discussion points the interviewer is probing** - Choosing data structures: hash maps for aggregation, heaps for Top-K, spatial index for nearest-neighbor. - Distinguishing one-shot vs. repeated queries → when preprocessing (prefix sums, k-d tree, sorted timestamps) pays off. - Edge cases: empty window (avoid divide-by-zero on the average), ties in Top-K, restaurants missing a requested item, K larger than the candidate set. ## Checks and Follow-ups - Verify that the answer addresses every requested part of the prompt. - Identify the highest-risk assumption and explain how you would validate it. - Be ready to discuss an alternative approach and why you did not choose it first.

Three independent data-processing tasks over restaurant/order data. Part 1 is two linear scans (cheapest by summed menu prices; nearest by geo distance), upgradable to a spatial index for repeated queries. Part 2 is a windowed aggregation (sum/count/average), with prefix sums for repeated windows. Part 3 uses a size-K min-heap for Top-K orders and a hash-map count plus heap for Top-K menu items, all in one pass. The interviewer is evaluating data-structure choice and recognizing when preprocessing beats per-query scans.