## Interview Prompt Design an in-memory service with three operations: insert a customer with direct revenue and return an auto-incrementing ID; insert a customer with direct revenue and an existing referrer; and return the `k` customers with the lowest total revenue that is at least a threshold. Treat total revenue as a customer's direct revenue plus revenue credited from direct referrals. Explain update and query complexity and how you keep an ordered index consistent. ### Constraints & Assumptions - Customer IDs begin at zero and never change. - A referrer must already exist; referral credit is one level, not recursively propagated. - Revenue is nonnegative and use integer minor units to avoid floating-point ordering errors. - Threshold results sort by total revenue ascending and then customer ID ascending. ### Clarifying Questions to Ask - Does a referred customer's revenue also remain part of that customer's own total? - Can revenue change after insertion, or are inserts the only updates? - Should the result include the new customer and referrer when both satisfy the threshold? ### What a Strong Answer Covers - Authoritative maps for customer records and referrer relationships. - An ordered structure keyed by `(totalRevenue, customerId)` with remove-update-reinsert semantics. - Correct atomic update of both the inserted customer and its referrer's ordered key. - A lower-bound threshold scan that returns only k records and preserves tie order. - Honest discussion of language-specific balanced trees versus heaps or sorted arrays. ### Follow-up Questions - How would recursive referral credit change update complexity? - How would you support revenue corrections after insertion? - What consistency mechanism is needed when multiple inserts run concurrently?