Optimize least-k revenue queries for read/write load
Company: Databricks
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
## Follow-up Scenario
Now assume revenue is not provided as a flat list of events, but may be **nested**, for example:
- Each customer has many orders, and each order has many line items.
- Or a stream of updates arrives as `(customer_id, delta_amount)` events.
You need to support the query:
> “Return the `k` customers with the smallest total revenue.”
### Questions
1. How would you compute/maintain customer revenue totals when the input is nested (orders → items) or incremental (`delta_amount` updates)?
2. What are the **time and space complexities** of your approach?
3. How would you change the design for:
- **Read-heavy** workload (many `leastK()` queries, fewer updates)
- **Write-heavy** workload (many updates, fewer queries)
Assume you do **not** need to write full code, but must clearly describe data structures, operations, and complexity.
Overview: This question evaluates a candidate's ability to design and maintain dynamic aggregate metrics from nested or incremental inputs, emphasizing data modeling, streaming updates, and the use of appropriate data structures and algorithms to compute least-k aggregates.