Revenue Service Results

Medium

Design · Databricks

Build a small revenue service. Process operations in order; each operation adds one entry to the output list:

["insert", revenue]: create a new customer with this revenue. Customer ids are assigned 0, 1, 2, ... in creation order. Output the new id.
["insert", revenue, referrer_id]: same, and additionally add revenue to the current revenue of the existing customer referrer_id. The credit goes only to the direct referrer, not further up the referral chain. Output the new id.
["query", k, min_revenue]: output a list of up to k customer ids whose current revenue is at least min_revenue, choosing the ones with the lowest revenue. Order the list by revenue ascending, breaking ties by smaller id first.

Return the list of outputs.

Example 1

Input:: operations = [["insert", 10], ["insert", 20, 0], ["insert", 5], ["query", 2, 10], ["insert", 1, 2], ["query", 5, 0]]
Output:: [0, 1, 2, [1, 0], 3, [3, 2, 1, 0]]
Explanation: Ids are 0, 1, 2. Customer 1 was referred by 0, so 0's revenue becomes 10 + 20 = 30. The first query wants revenue at least 10: customer 1 (20) then customer 0 (30). Customer 3 is referred by 2, raising 2 to 6, so the final query lists 3 (1), 2 (6), 1 (20), 0 (30).

Input:: operations = [["insert", 7], ["insert", 7], ["query", 5, 8], ["query", 1, 7]]
Output:: [0, 1, [], [0]]
Explanation: No customer has at least 8, so the first query returns []. Both have 7; ties go to the smaller id, and k = 1 keeps only customer 0.

Input:: operations = [["insert", 3], ["insert", 3, 0], ["insert", 3, 1], ["query", 3, 0]]
Output:: [0, 1, 2, [2, 0, 1]]
Explanation: Customer 1's referral raises customer 0 to 6, and customer 2's referral raises customer 1 to 6. Credit is only one level deep, so customer 2 does not also credit customer 0. Revenues are 6, 6, 3, so the order is 2, then 0 and 1 (tied, smaller id first).