How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Uber during technical interviews.

Implement a Referral Revenue Tracker

Quick Overview

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

You are given a sequence of operations for an in-memory referral revenue tracker. Each customer has direct revenue and may have exactly one referrer, forming a forest. A customer's aggregate revenue is the sum of its own direct revenue and the direct revenue of every customer in its referral subtree. Implement the tracker and return the answer for every top_k query. Each operation is one of: ("insert", customer_id, amount, referrer_id): add amount to the direct revenue of customer_id. If the customer does not exist, create it and set its referrer to referrer_id (which may be None). If the customer already exists, ignore the provided referrer_id and only add the revenue. ("top_k", k, threshold): find the customers whose aggregate revenue is strictly greater than threshold, sort them by aggregate revenue descending and then by customer_id ascending, and return the first k as [customer_id, aggregate_revenue] pairs. Return a list containing the result of each top_k query in order.

Constraints

0 <= len(operations) <= 10^4
There are at most 5000 distinct customers
1 <= customer_id <= 10^9
-10^9 <= amount, threshold <= 10^9
0 <= k <= number of current customers
If a new customer is inserted with a non-None referrer_id, that referrer already exists and the referral graph is acyclic

Examples

Input: [("insert", 1, 100, None), ("insert", 2, 50, 1), ("insert", 3, 70, 1), ("top_k", 2, 100), ("insert", 2, 30, None), ("top_k", 3, 60)]

Expected Output: [[[1, 220]], [[1, 250], [2, 80], [3, 70]]]

Explanation: After the first three inserts, customer 1 has aggregate revenue 220. After adding 30 more to customer 2, customer 2 becomes 80 and customer 1 becomes 250.

Input: [("insert", 1, 50, None), ("insert", 2, 50, None), ("insert", 3, 10, 1), ("insert", 4, 10, 2), ("top_k", 2, 59), ("top_k", 3, 50)]

Expected Output: [[[1, 60], [2, 60]], [[1, 60], [2, 60]]]

Explanation: Customers 1 and 2 both have aggregate revenue 60, so the tie is broken by smaller customer ID first.

Input: [("insert", 1, 100, None), ("insert", 2, -20, 1), ("insert", 3, 50, 2), ("top_k", 3, 200), ("top_k", 3, 20), ("insert", 2, -40, None), ("top_k", 3, 20)]

Expected Output: [[], [[1, 130], [3, 50], [2, 30]], [[1, 90], [3, 50]]]

Explanation: The first query returns no customers because aggregate revenue must be strictly greater than 200. Negative revenue updates reduce both the customer's aggregate and all ancestors' aggregates.

Input: [("insert", 1, 10, None), ("insert", 2, 5, 1), ("insert", 2, 15, 1), ("insert", 3, 7, None), ("insert", 2, 5, 3), ("top_k", 10, 0)]

Expected Output: [[[1, 35], [2, 25], [3, 7]]]

Explanation: Customer 2 already exists when inserted with referrer 3, so its original referrer remains 1. Only the revenue is added.

Input: []

Expected Output: []

Explanation: With no operations, there are no query results.

Hints

When revenue is added to one customer, the same delta must also be reflected in every ancestor's aggregate revenue.
For each top_k query, first filter customers whose aggregate revenue is above the threshold, then sort by the required key: descending aggregate revenue and ascending customer ID.

Last updated: May 6, 2026

Loading coding console...

Quick Overview

Implement a Referral Revenue Tracker

Company: Uber

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Constraints

0 <= len(operations) <= 10^4
There are at most 5000 distinct customers
1 <= customer_id <= 10^9
-10^9 <= amount, threshold <= 10^9
0 <= k <= number of current customers
If a new customer is inserted with a non-None referrer_id, that referrer already exists and the referral graph is acyclic

Examples

Input: [("insert", 1, 100, None), ("insert", 2, 50, 1), ("insert", 3, 70, 1), ("top_k", 2, 100), ("insert", 2, 30, None), ("top_k", 3, 60)]

Expected Output: [[[1, 220]], [[1, 250], [2, 80], [3, 70]]]

Explanation: After the first three inserts, customer 1 has aggregate revenue 220. After adding 30 more to customer 2, customer 2 becomes 80 and customer 1 becomes 250.

Input: [("insert", 1, 50, None), ("insert", 2, 50, None), ("insert", 3, 10, 1), ("insert", 4, 10, 2), ("top_k", 2, 59), ("top_k", 3, 50)]

Expected Output: [[[1, 60], [2, 60]], [[1, 60], [2, 60]]]

Explanation: Customers 1 and 2 both have aggregate revenue 60, so the tie is broken by smaller customer ID first.

Input: [("insert", 1, 100, None), ("insert", 2, -20, 1), ("insert", 3, 50, 2), ("top_k", 3, 200), ("top_k", 3, 20), ("insert", 2, -40, None), ("top_k", 3, 20)]

Expected Output: [[], [[1, 130], [3, 50], [2, 30]], [[1, 90], [3, 50]]]

Input: [("insert", 1, 10, None), ("insert", 2, 5, 1), ("insert", 2, 15, 1), ("insert", 3, 7, None), ("insert", 2, 5, 3), ("top_k", 10, 0)]

Expected Output: [[[1, 35], [2, 25], [3, 7]]]

Explanation: Customer 2 already exists when inserted with referrer 3, so its original referrer remains 1. Only the revenue is added.

Input: []

Expected Output: []

Explanation: With no operations, there are no query results.

Hints

When revenue is added to one customer, the same delta must also be reflected in every ancestor's aggregate revenue.
For each top_k query, first filter customers whose aggregate revenue is above the threshold, then sort by the required key: descending aggregate revenue and ascending customer ID.

Last updated: May 6, 2026

Loading coding console...