Implement a Referral Revenue Tracker
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement an in-memory revenue tracking system for customers in a referral network.
Each customer has their own direct revenue. A customer may also have been referred by another customer. If customer B was referred by customer A, then A's aggregate revenue includes both A's own direct revenue and all revenue generated by B. Assume this relationship is recursive, so a customer's aggregate revenue includes the revenue of all customers in their referral subtree.
Design a data structure with these operations:
1. `insert_revenue(customer_id, amount, referrer_id=None)`
- Add `amount` to the direct revenue of `customer_id`.
- If the customer does not already exist, create them.
- If `referrer_id` is provided when the customer is first created, link the customer under that referrer.
- You may assume there are no referral cycles, and any provided referrer already exists.
2. `top_k_above(k, threshold)`
- Return the top `k` customers whose aggregate revenue is strictly greater than `threshold`.
- Sort results by aggregate revenue in descending order. Break ties by customer ID.
Discuss your design choices and implement the required methods efficiently.
Quick Answer: This question evaluates proficiency with data structures and algorithms for hierarchical aggregation and ranking, assessing skills such as maintaining recursive subtree aggregates, handling dynamic inserts, and executing efficient top-k queries; it is in the Coding & Algorithms domain and tests practical application of in-memory data structure design. It is commonly asked to evaluate the ability to design scalable, low-latency in-memory systems that preserve aggregate values across referral trees and support fast query operations while reasoning about time and space complexity trade-offs.