How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Coinbase.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coinbase during technical interviews.

Compute prices, distances, and Top-K for orders

Quick Overview

Compute prices, distances, and Top-K for orders evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute prices, distances, and Top-K for orders

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: Compute prices, distances, and Top-K for orders evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

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')

Expected Output: [['r3', 1.4142135623730951]]

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

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

Expected Output: []

Explanation: No restaurant offers pizza.

Input: (['b', 'a', 'c'], [[-1, 0], [1, 0], [0, 2]], [{'taco': 5.0}, {'taco': 5.0}, {'taco': 5.0}], [0, 0], 'taco')

Expected Output: [['a', 1.0], ['b', 1.0]]

Explanation: All three have the same price, but a and b are nearest with distance 1.0. They are returned sorted by id.

Input: ([], [], [], [10, 10], 'sushi')

Expected Output: []

Explanation: Edge case: there are no restaurants.

Hints

You do not need to compute square roots to compare distances; compare squared distances and only take the square root for the output.
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

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)

Expected 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.

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)

Expected Output: [15.0, 2, 7.5]

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

Input: (['r1'], [{'tea': 2.5}], [], [], [], [], 0, 100)

Expected Output: [0.0, 0, 0.0]

Explanation: Edge case: there are no orders.

Input: (['r1'], [{'x': 4.0}], ['o1'], ['r1'], [100], [{'x': 1}], 100, 100)

Expected Output: [0.0, 0, 0.0]

Explanation: Edge case: an empty half-open window [100, 100) includes no timestamps.

Hints

Build a dictionary from restaurant id to its menu so each order can find prices quickly.
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

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)

Expected 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.

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

Expected 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.

Input: (['r1'], [{'a': 2.0}], ['o1'], ['r1'], [1], [{'a': 3}], 0, 10, 0)

Expected Output: [[], []]

Explanation: Edge case: k = 0 means no top results should be returned.

Input: (['r1'], [{'a': 2.0}], ['o1'], ['r1'], [10], [{'a': 3}], 0, 10, 2)

Expected Output: [[], []]

Explanation: The only order is at timestamp end, so it is excluded from the half-open window.

Hints

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

Quick Overview

Compute prices, distances, and Top-K for orders

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Part 1: Lowest-Price Nearest Restaurant for an Item

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

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')

Expected Output: [['r3', 1.4142135623730951]]

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

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

Expected Output: []

Explanation: No restaurant offers pizza.

Input: (['b', 'a', 'c'], [[-1, 0], [1, 0], [0, 2]], [{'taco': 5.0}, {'taco': 5.0}, {'taco': 5.0}], [0, 0], 'taco')

Expected Output: [['a', 1.0], ['b', 1.0]]

Explanation: All three have the same price, but a and b are nearest with distance 1.0. They are returned sorted by id.

Input: ([], [], [], [10, 10], 'sushi')

Expected Output: []

Explanation: Edge case: there are no restaurants.

Hints

You do not need to compute square roots to compare distances; compare squared distances and only take the square root for the output.
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

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

Expected 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.

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)

Expected Output: [15.0, 2, 7.5]

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

Input: (['r1'], [{'tea': 2.5}], [], [], [], [], 0, 100)

Expected Output: [0.0, 0, 0.0]

Explanation: Edge case: there are no orders.

Input: (['r1'], [{'x': 4.0}], ['o1'], ['r1'], [100], [{'x': 1}], 100, 100)

Expected Output: [0.0, 0, 0.0]

Explanation: Edge case: an empty half-open window [100, 100) includes no timestamps.

Hints

Build a dictionary from restaurant id to its menu so each order can find prices quickly.
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

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

Expected 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.

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

Expected 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.

Input: (['r1'], [{'a': 2.0}], ['o1'], ['r1'], [1], [{'a': 3}], 0, 10, 0)

Expected Output: [[], []]

Explanation: Edge case: k = 0 means no top results should be returned.

Input: (['r1'], [{'a': 2.0}], ['o1'], ['r1'], [10], [{'a': 3}], 0, 10, 2)

Expected Output: [[], []]

Explanation: The only order is at timestamp end, so it is excluded from the half-open window.

Hints

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