Find top-k lottery winners by spending
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building a lottery system where each user’s chance of winning is **linearly proportional** to how much they spent (e.g., user with spend `s` has weight `s`).
Given:
- An array of participants, each with a unique `user_id` and a non-negative integer `spend`.
- An integer `k`.
Task:
- Return the **`k` users with the highest winning probability**, i.e., the `k` users with the largest `spend` values.
Clarifications to handle:
- If `k` is greater than the number of users, return all users.
- Define how to break ties (e.g., by `user_id` ascending) and keep it consistent.
- Discuss time and space complexity of your approach.
Example:
- Input: `[(A, 10), (B, 5), (C, 10), (D, 1)], k=2`
- Output (one valid): `[A, C]` (tie broken deterministically)
Quick Answer: This question evaluates skills in selection and ordering of numeric-keyed records, covering concepts such as order statistics, deterministic tie-breaking, and time and space complexity analysis.
Return the user IDs for the k participants with highest spend, tie-breaking by user_id ascending.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([('A',10),('B',5),('C',10),('D',1)], 2)
Expected Output: ['A', 'C']
Explanation: Prompt example with deterministic tie-break.
Input: ([('u2',3),('u1',3)], 5)
Expected Output: ['u1', 'u2']
Explanation: k exceeds participant count.
Input: ([], 3)
Expected Output: []
Explanation: No participants.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.