Compute prices, distances, and Top-K for orders

Build functions for a food‑delivery analytics module. Data:

• Restaurants: id, (x, y) location, menu mapping item -> price.
• Orders: id, restaurantId, timestamp (Unix ms), line items: (item, quantity). Tasks: (a) Given the user's (x, y) and a target item, return the restaurant (s) offering the lowest price for that item and, among ties, the nearest by Euclidean distance (return id and distance). (b) For a time window [start, end), compute total revenue, order count, and average order value. (c) For a time window [start, end), return Top K orders by total price (id, total) and Top K items by quantity sold (item, quantity). Specify tie‑breaking rules, chosen data structures, and complexity.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Part 1: Lowest-Price Nearest Restaurant for an Item

You are given restaurants represented by aligned arrays: restaurant_ids[i], locations[i], and menus[i] describe the same restaurant. Each menu is a mapping from item name to price. Given a user's location and a target item, return the restaurant or restaurants that offer the lowest price for that item. If several restaurants have that lowest price, keep only the nearest restaurant(s) by Euclidean distance. If multiple restaurants are still tied with the exact same price and distance, return all of them sorted by restaurant id. Assumption: restaurant ids are unique strings, menu item names are case-sensitive, and menu prices are numeric.

Constraints

• 0 <= len(restaurant_ids) <= 100000
• len(restaurant_ids) == len(locations) == len(menus)
• restaurant_ids are unique strings
• locations[i] contains exactly two numeric coordinates
• Each menus[i] maps item names to non-negative numeric prices
• If multiple restaurants tie on both best price and nearest distance, return all tied restaurants sorted lexicographically by id

Examples

Example 1

Input: (['r1', 'r2', 'r3'], [[0, 0], [3, 4], [1, 1]], [{'pizza': 10.0, 'salad': 5.0}, {'pizza': 8.0}, {'pizza': 8.0}], [0, 0], 'pizza')
Output: [['r3', 1.4142135623730951]]

Explanation: Restaurants r2 and r3 both have the lowest pizza price 8.0, but r3 is closer to the user.

Example 2

Input: (['r1', 'r2'], [[0, 0], [1, 1]], [{'salad': 5.0}, {'burger': 7.0}], [0, 0], 'pizza')
Output: []

Explanation: No restaurant offers pizza.

Hints

1. You do not need to compute square roots to compare distances; compare squared distances and only take the square root for the output.
2. Track the current best price and, among that price, the current best squared distance while scanning the restaurants once.

Part 2: Revenue Metrics for Orders in a Time Window

You are given restaurant menus and orders. Restaurants are represented by aligned arrays restaurant_ids and menus. Orders are represented by aligned arrays: order_ids[i], order_restaurant_ids[i], timestamps[i], and order_items[i] describe the same order. For a half-open time window [start, end), compute total revenue, order count, and average order value. An order total is the sum of menu price times quantity for each item in that order. Assumption: every order references an existing restaurant, and every ordered item exists in that restaurant's menu.

Constraints

• 0 <= len(restaurant_ids) <= 100000
• 0 <= len(order_ids) <= 100000
• len(restaurant_ids) == len(menus)
• len(order_ids) == len(order_restaurant_ids) == len(timestamps) == len(order_items)
• start <= end
• Each timestamp is an integer Unix millisecond value
• Each quantity is a non-negative integer
• Every order restaurant id exists in restaurant_ids, and every ordered item exists in that restaurant's menu

Examples

Example 1

Input: (['r1', 'r2'], [{'pizza': 10.0, 'salad': 5.0}, {'pizza': 8.0, 'burger': 12.0}], ['o1', 'o2', 'o3'], ['r1', 'r2', 'r1'], [1000, 1500, 2000], [{'pizza': 2, 'salad': 1}, {'burger': 1, 'pizza': 1}, {'pizza': 1}], 1000, 2000)
Output: [45.0, 2, 22.5]

Explanation: Orders o1 and o2 are included. o1 total is 25.0 and o2 total is 20.0. o3 is excluded because its timestamp equals end.

Example 2

Input: (['r1'], [{'coffee': 3.0}], ['before', 'start', 'inside', 'end'], ['r1', 'r1', 'r1', 'r1'], [999, 1000, 1999, 2000], [{'coffee': 1}, {'coffee': 2}, {'coffee': 3}, {'coffee': 4}], 1000, 2000)
Output: [15.0, 2, 7.5]

Explanation: The order at timestamp 1000 is included and the order at timestamp 2000 is excluded.

Hints

1. Build a dictionary from restaurant id to its menu so each order can find prices quickly.
2. Be careful with the half-open interval: timestamp == start is included, timestamp == end is excluded.

Part 3: Top K Orders and Items in a Time Window

You are given restaurant menus and orders. For a half-open time window [start, end), return the Top K orders by total price and the Top K items by total quantity sold. An order total is computed from the restaurant's menu prices and that order's item quantities. Tie-breaking rules: orders are sorted by total price descending, then order id ascending; items are sorted by quantity sold descending, then item name ascending. This solution uses hash maps for menu lookup and item aggregation, then sorting to select the top K. Assumption: every order references an existing restaurant, and every ordered item exists in that restaurant's menu.

Constraints

• 0 <= len(restaurant_ids) <= 100000
• 0 <= len(order_ids) <= 100000
• len(restaurant_ids) == len(menus)
• len(order_ids) == len(order_restaurant_ids) == len(timestamps) == len(order_items)
• start <= end
• 0 <= k <= 100000
• Each quantity is a positive integer for sold line items
• Every order restaurant id exists in restaurant_ids, and every ordered item exists in that restaurant's menu

Examples

Example 1

Input: (['r1', 'r2'], [{'pizza': 10.0, 'salad': 5.0}, {'pizza': 8.0, 'burger': 12.0}], ['o1', 'o2', 'o3', 'o4'], ['r1', 'r2', 'r1', 'r2'], [1000, 1100, 1200, 1300], [{'pizza': 2, 'salad': 1}, {'pizza': 1, 'burger': 2}, {'salad': 3}, {'pizza': 4}], 1000, 1300, 2)
Output: [[['o2', 32.0], ['o1', 25.0]], [['salad', 4], ['pizza', 3]]]

Explanation: o4 is excluded because its timestamp equals end. Among included orders, o2 and o1 have the largest totals. Salad quantity is 4 and pizza quantity is 3.

Example 2

Input: (['r1'], [{'a': 10.0, 'b': 10.0}], ['oB', 'oA'], ['r1', 'r1'], [5, 6], [{'a': 1}, {'b': 1}], 0, 10, 5)
Output: [[['oA', 10.0], ['oB', 10.0]], [['a', 1], ['b', 1]]]

Explanation: k is larger than the number of orders/items, so all are returned. Order totals tie, so ids sort ascending. Item quantities tie, so item names sort ascending.

Hints

1. Compute each in-window order's total once, and at the same time aggregate quantities in an item -> total_quantity dictionary.
2. After aggregation, sorting with a compound key implements both the ranking and the tie-breaking rules.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Build functions for a food‑delivery analytics module. Data: - Restaurants: id, (x, y) location, menu mapping item -> price. - Orders: id, restaurantId, timestamp (Unix ms), line items: (item, quantity). Tasks: (a) Given the user's (x, y) and a target item, return the restaurant (s) offering the lowest price for that item and, among ties, the nearest by Euclidean distance (return id and distance). (b) For a time window [start, end), compute total revenue, order count, and average order value. (c) For a time window [start, end), return Top K orders by total price (id, total) and Top K items by quantity sold (item, quantity). Specify tie‑breaking rules, chosen data structures, and complexity.

Recommended Approach

For one-time top-K, use a size-K min-heap or quickselect plus sorting the selected K. For streaming windows, maintain counts in a hash map plus a heap with lazy deletion or bucketed frequency structures when updates must be near O(1). Define deterministic tie-breaking.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

One-time heap: O(n log k) time and O(k) space. Quickselect: expected O(n) plus O(k log k) to order output. Streaming complexity depends on window eviction and tie-breaking.

Edge Cases and Tests

k = 0, k > n, duplicate values, ties, negative values, stale heap entries, and deterministic output ordering.