Katkat
Back

Find top-k lottery winners by spending

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to manage top-k selection from a stream or static collection using heap data structures while enforcing deterministic tie-breaking rules.

Problem Statement

You are given a list of lottery participants, where each participant is represented by a dictionary (or object) containing an id (int) and total_spent (float). Your goal is to identify the top k spenders.

If two participants have the same total_spent, the participant with the smaller id must be ranked higher. Implement the function get_top_k_spenders(participants, k).

Constraints

  • participants list size: up to 1,000,000.
  • k: 1 <= k <= len(participants).
  • total_spent: non-negative floats.
  • id: unique positive integers.

Examples

# Example 1
participants = [
    {"id": 1, "total_spent": 100.0},
    {"id": 2, "total_spent": 50.0},
    {"id": 3, "total_spent": 100.0}
]
k = 2
# Output: [{"id": 1, "total_spent": 100.0}, {"id": 3, "total_spent": 100.0}]
# Explanation: ID 1 and 3 are tied, but ID 1 < ID 3 for the rank order.

Requirements

  • Return the result as a list of dictionaries sorted by total_spent (descending) and then id (ascending).
  • Consider edge cases where k equals the length of the list or k is 1.
  • Aim for an optimal time complexity relative to N and k.

Hints

Hint 1

To handle the custom sorting criteria, define a comparison rule where higher spending is preferred, but for identical spending, the smaller ID is preferred.

Hint 2

A min-heap of size k can be used to track the top k elements, but you must carefully define the heap's 'less-than' operator to account for both spending and ID tie-breaking.

Hint 3

If using a min-heap, remember that the smallest element (the 'worst' of the top k) will be at the root, so your comparison logic needs to reflect the inverse of your final desired sorting order.

Follow-up questions

  • How would your approach change if the participants list was a stream of billions of records that cannot fit into memory?
  • What is the time complexity of your solution, and how would it change if k was very close to the total number of participants N?
  • If we wanted to return the k-th highest spender only, could we improve the average time complexity using a selection algorithm like QuickSelect?