Katkat
Back

Implement a Referral Revenue Tracker

UberMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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.

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