Track Customer Revenue and Referral Revenue
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Track Customer Revenue and Referral Revenue
## Problem
Implement a top-level function that processes an in-memory customer revenue tracker through a literal operation sequence:
def process_revenue_operations(operations: list[list]) -> list:
...
Every customer has a non-negative direct revenue value and may have one direct referrer. Customer identifiers are consecutive integers assigned from 0 after each successful insertion.
This operation-sequence wrapper is a practice representation assumption that makes the originally stateful tracker directly testable. Process operations from left to right:
- ["add", revenue]
Add a customer without a referrer and append the new customer ID to the result.
- ["add_referral", revenue, referrer_id]
Add a customer referred by an existing customer and append the new customer ID.
- ["top_direct", k]
Append up to k customer IDs ranked by direct revenue.
- ["top_nested", k]
Append up to k customer IDs ranked by nested revenue, where nested revenue is the customer's own revenue plus every direct and indirect referral descendant's direct revenue.
For both rankings, sort by revenue descending and then customer ID ascending. A valid query with k <= 0 appends an empty list. If fewer than k customers exist, append every customer in rank order.
Return exactly one result element per input operation.
## Deterministic Error Contract
The string "ERROR" is reserved as the result for an invalid operation. An invalid operation appends "ERROR", changes no tracker state, consumes no customer ID, and processing continues.
An operation is invalid when any of the following is true:
- it is not a list with one of the exact names and arities above;
- a numeric field is not a Python integer (Boolean values do not count as integers);
- revenue is outside [0, 10^9];
- referrer_id is not the ID of a customer created by an earlier successful operation;
- more than 100,000 customers would be created; or
- k is not an integer.
An integer k <= 0 is valid and produces an empty ranking. Ranking an empty tracker is valid and produces an empty list.
## Constraints
- At most 200,000 operations are supplied.
- Each successful customer insertion has at most one direct referrer, so the referral structure is a forest.
- Revenue never changes after insertion.
- Every nested-revenue total fits in a signed 64-bit integer.
## Example
operations = [
["add", 100],
["add_referral", 40, 0],
["add_referral", 70, 1],
["add", 150],
["top_direct", 3],
["top_nested", 3],
["add_referral", 20, 99],
["top_direct", 0],
]
output = [
0,
1,
2,
3,
[3, 0, 2],
[0, 3, 1],
"ERROR",
[],
]
The failed referral does not create customer 4.
## Discussion
Before coding, compare a full sort, a heap, and an ordered-set or balanced-tree approach. State the insert/query mix that makes your design appropriate, and explain how a successful referral updates the nested revenue of its ancestor chain.
Overview: Build a customer revenue tracker that supports referrals plus direct- and nested-revenue rankings. Process a deterministic operation stream, preserve state across invalid requests, and explain efficient ranking and ancestor-update strategies.
Process customer insertion and ranking commands, tracking direct revenue and each customer's revenue plus all referral descendants.
Constraints
- At most 100000 customers and 200000 operations
- Revenue is an integer from 0 through 10^9
- Invalid operations append ERROR and make no state change
Examples
Input: []
Expected Output: []
Explanation: No operations produce no results.
Input: [['top_direct', 3], ['top_nested', 1]]
Expected Output: [[], []]
Explanation: Ranking an empty tracker is valid.
Hints
- Store one parent pointer for each referred customer.
- On insertion, propagate the new direct revenue through the ancestor chain.
Community answers
Answer by jai13.space
Incorrect complexity specified in the solution for top k - it is Nlog(N) in every case since the sorted runs on the whole array of values and then slices last k. The optimal solution would do it in O(Nlog(K) + K*log(K)).
Here is a solution that does it using heap. This is written for the Alg round (where code quality matters as well). Could I have modified the original solution - of course. But this combines modularity with lazy compute for analytics on demand. We combine bfs when collecting values which makes it linear, followed by the heap collect logic. Its more easy to mould it for concurrency scenarios too as locks could be acquired only for specific users as needed instead of locking the whole data structure.
Exact scenario could depend on the discussion with the interviewer.
Tcpx for analytics: O(Nlog(K) + Klog(K))
Tcpx for inserts: O(1)
import heapq
from typing import Dict, List
class CustomerIdGenerator:
def init(self):
self.current_id = 0
def next_id(self) -> int:
val = self.current_id
self.current_id += 1
return val
class Customer:
def init(self, id, seed_revenue=0):
self.id = id
self.referrals:List["Customer"] = []
self.revenue = seed_revenue
def add_referral(self, customer:"Customer"):
self.referrals.append(customer)
class RevenueTracker:
def init(self):
self.id_gen = CustomerIdGenerator()
self.customers:Dict[int, Customer] = {}
self.total_customers = 0
def add_customer(self, revenue:int) -> Customer:
customer = Customer(self.id_gen.next_id(), revenue)
self.custo