Customer Revenue

DatabricksPhone screenMedium

You maintain an in-memory record of customers and the revenue each has brought in. Customers are numbered 0, 1, 2, ... in the order they are added, and revenue is a non-negative integer.

Part 1: Add and query

Implement two methods on CustomerRevenue.

add(revenue) adds a customer with revenue revenue and returns the new customer's number.
lowest_k(minimum, k) returns the numbers of at most k customers whose revenue is at least minimum, ordered by revenue from lowest to highest, with customers of equal revenue ordered by number. If fewer than k customers qualify, return all of them.

Example 1
init
[]
operations
[["add",[100]],["add",[40]],["lowest_k",[0,2]],["lowest_k",[41,5]],["add",[40]],["lowest_k",[40,3]],["lowest_k",[40,1]],["lowest_k",[1000,3]]]
Output
[0,1,[1,0],[0],2,[1,2,0],[1],[]]
Why: After two adds the revenues are 100 and 40, so the lowest 2 with minimum 0 are [1, 0]. With minimum 41 only customer 0 qualifies. Customer 2 also has revenue 40, so the lowest 3 with minimum 40 are [1, 2, 0] (customers 1 and 2 tie on revenue, ordered by number), and k = 1 truncates that to [1]. No customer reaches 1000.

Constraints

0 <= revenue <= 10^9
0 <= minimum <= 10^9
0 <= k <= 10^4
1 <= len(operations) <= 10^4