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 Technical Screen rounds at Uber.

What role is this question designed for?

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

Track Customer Referral Revenue | Uber Coding Question

Quick Overview

This question evaluates understanding of dynamic data structure design and algorithms for maintaining aggregated metrics over a referral tree, specifically computing subtree revenue contributions and selecting customers by total contributed revenue under a threshold.

Track Customer Referral Revenue

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a data structure to track customers and referral-based revenue. Implement the following operations: - `int insertNewCustomer(double revenue)` - Add a new customer with the given direct revenue and no referrer. - Return the newly assigned customer ID. - `int insertNewCustomer(double revenue, int referrerID)` - Add a new customer with the given direct revenue. - This customer was referred by `referrerID`. - Return the newly assigned customer ID. - `Set<Integer> getLowestK(int k, double minTotalRevenue)` - Return the IDs of the `k` customers with the smallest **total contributed revenue** among all customers whose total contributed revenue is at least `minTotalRevenue`. Define a customer's **total contributed revenue** as: - their own direct revenue, plus - the direct revenue of all customers in their referral subtree (all direct and indirect referrals). Assumptions: - Customer IDs are assigned incrementally starting from `0`. - `referrerID` is always valid. - If fewer than `k` customers satisfy the threshold, return all of them. - Since the return type is a set, output order does not matter. Example: - `insertNewCustomer(10)` returns `0` - `insertNewCustomer(30, 0)` returns `1` - `insertNewCustomer(50, 1)` returns `2` Then the total contributed revenues are: - customer `0` -> `10 + 30 + 50 = 90` - customer `1` -> `30 + 50 = 80` - customer `2` -> `50` So: - `getLowestK(1, 45)` returns `{2}` - `getLowestK(2, 45)` returns `{1, 2}`

Quick Answer: This question evaluates understanding of dynamic data structure design and algorithms for maintaining aggregated metrics over a referral tree, specifically computing subtree revenue contributions and selecting customers by total contributed revenue under a threshold.

You are given a sequence of operations on a customer referral system. Each new customer has a direct revenue and may optionally be referred by an existing customer. The customers form a forest of referral trees. For each customer, define total contributed revenue as the sum of their own direct revenue and the direct revenue of every customer in their referral subtree, including all direct and indirect referrals. Process the operations and return the result of every operation in order. Operations: - ("insert", revenue): add a new customer with no referrer. - ("insert", revenue, referrerID): add a new customer referred by referrerID. - ("get", k, minTotalRevenue): among customers whose total contributed revenue is at least minTotalRevenue, choose the k customers with the smallest total contributed revenue. If multiple customers have the same total contributed revenue, the smaller customer ID is considered smaller. In the original object-oriented version this query returns a set, so output order does not matter. For this batch-function problem, represent each "get" result as a list of the selected customer IDs sorted in ascending order. Customer IDs are assigned incrementally starting from 0. If fewer than k customers satisfy the threshold, return all qualifying customers. If none qualify, return an empty list.

Constraints

1 <= len(operations) <= 3000
0 <= revenue, minTotalRevenue <= 10^9
0 <= referrerID < current number of customers whenever a referred insert appears
1 <= k <= 3000

Examples

Input: [('insert', 10), ('insert', 4, 0), ('insert', 3, 0), ('get', 1, 3), ('get', 2, 3)]

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

Explanation: After the inserts, total contributed revenues are: customer 0 -> 17, customer 1 -> 4, customer 2 -> 3. For ('get', 1, 3), the smallest qualifying total is customer 2, so return [2]. For ('get', 2, 3), the two smallest qualifying customers are 2 and 1, and the final returned list is sorted by ID as [1, 2].

Input: [('insert', 7), ('get', 3, 10)]

Expected Output: [0, []]

Explanation: Customer 0 has total contributed revenue 7, which is below 10, so the query returns an empty list.

Input: [('get', 2, 0)]

Expected Output: [[]]

Explanation: There are no customers yet, so no one qualifies.

Input: [('insert', 2), ('insert', 5), ('insert', 3, 0), ('insert', 5), ('get', 2, 5), ('get', 10, 5)]

Expected Output: [0, 1, 2, 3, [0, 1], [0, 1, 3]]

Explanation: Totals become: customer 0 -> 5, customer 1 -> 5, customer 2 -> 3, customer 3 -> 5. For threshold 5, customers 0, 1, and 3 qualify. Since their totals are tied, smaller IDs come first, so the first two are 0 and 1.

Input: [('insert', 4), ('insert', 2, 0), ('insert', 1, 1), ('get', 2, 2)]

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

Explanation: Totals are: customer 0 -> 7, customer 1 -> 3, customer 2 -> 1. With threshold 2, customers 1 and 0 qualify. They are chosen in total order as 1 then 0, but the returned ID list is sorted ascending, so the answer is [0, 1].

Hints

A newly inserted customer is always a leaf. Their direct revenue increases the total contributed revenue of every ancestor on the path to the root.
For each get query, filter customers whose total is at least the threshold, sort them by (total contributed revenue, customer ID), take the first k, then sort those chosen IDs for output.

Quick Overview