Design a Customer Revenue Index with Referrals and Threshold Queries

Question

Design a system that manages customer revenue data while supporting referral tracking and querying for the lowest revenue customers above a specified threshold.

Codemia · Accepted Answer

The system must support three main functions: 
1. `insert(revenue)` - inserts a new customer with an auto-incremented ID. 
2. `insert(revenue, referrer)` - inserts a new customer with a specified referrer. 
3. `get_lowest_k_by_total_revenue(k, threshold)` - retrieves the lowest k customers whose total revenue exceeds a given threshold.

To implement this system, we can use a combination of a hash map and a sorted data structure. The hash map will store customer data, including their revenue and referrer information. For the `get_lowest_k_by_total_revenue` function, we can utilize a SortedSet or a priority queue to maintain the order of customers based on their total revenue efficiently.

Here is a Python implementation of the key functions:

```python
class CustomerRevenueSystem:
    def __init__(self):
        self.customers = {}
        self.revenue = []
        self.current_id = 0

def insert(self, revenue, referrer=None):
        customer_id = self.current_id
        self.customers[customer_id] = {'revenue': revenue, 'referrer': referrer}
        self.revenue.append((revenue, customer_id))
        self.current_id += 1

def get_lowest_k_by_total_revenue(self, k, threshold):
        # Filter customers by threshold
        filtered = [cust for cust in self.revenue if cust[0] > threshold]
        # Sort and get the lowest k
        filtered.sort()  # Sort by revenue
        return [cust[1] for cust in filtered[:k]]
```
In this implementation, `insert` handles both types of customer insertions, and `get_lowest_k_by_total_revenue` filters and sorts the customers based on their revenue.

Using a list for revenue storage allows for easy insertion but can be inefficient for large datasets due to O(n) complexity for sorting. A more scalable solution would involve using a balanced binary search tree or a SortedSet, which maintains order and allows for efficient insertions and deletions. This approach would significantly improve performance as the size of the dataset grows.

Design a Customer Revenue Index with Referrals and Threshold Queries

Databricks

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Databricks Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline