Katkat
Back

Determine Redeemable Promotion Offers

AffirmSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage stateful constraints by processing a stream of promotional event logs to determine if a user remains eligible for a discount based on a per-user, per-promotion usage limit.

Determine Redeemable Promotion Offers

You are building a backend service for a payment platform that tracks user promotion usage. You are given a list of promotional events and a list of requested redemptions.

A promotion is defined by a promo_id and a usage_limit. An event represents a user successfully redeeming a promo_id at a specific timestamp. A redemption request checks if a user is still eligible to use a promo_id given their history.

Task

Implement a function get_eligible_promos(promo_limits, event_logs, check_requests).

  • promo_limits: A dictionary mapping promo_id (string) to an integer usage_limit.
  • event_logs: A list of objects/dicts, each containing user_id, promo_id, and timestamp (integer).
  • check_requests: A list of objects/dicts, each containing user_id and promo_id.

Return a list of booleans corresponding to each request in check_requests, where True means the user can still redeem the promotion (i.e., their current count for that promo is strictly less than the defined limit).

Constraints

  • event_logs and check_requests can contain up to 10^5 entries.
  • timestamp is a non-negative integer.
  • If a promo_id is not in promo_limits, assume a limit of 0 (never eligible).

Example

promo_limits = {"SAVE10": 2, "WELCOME": 1}
event_logs = [
    {"user_id": "u1", "promo_id": "SAVE10", "timestamp": 100},
    {"user_id": "u1", "promo_id": "SAVE10", "timestamp": 150},
    {"user_id": "u2", "promo_id": "WELCOME", "timestamp": 200}
]
check_requests = [
    {"user_id": "u1", "promo_id": "SAVE10"}, # False: 2/2 used
    {"user_id": "u1", "promo_id": "WELCOME"}, # True: 0/1 used
    {"user_id": "u2", "promo_id": "WELCOME"}  # False: 1/1 used
]

Edge Cases

  • A user has never used a specific promotion.
  • A user requests a promotion that doesn't exist in promo_limits.
  • Large volumes of logs for a single user.

Hints

Hint 1

First, aggregate the event logs to build a frequency map of (user_id, promo_id) counts.

Hint 2

Using a nested dictionary or a tuple key (user_id, promo_id) for your map will allow O(1) average time complexity for both counting and lookups.

Hint 3

After pre-processing the logs into a counts map, iterate through the check_requests and compare the current count against the limits dictionary.

Follow-up questions

  • How would your approach change if promotions had an expiration timestamp, meaning only events before a certain time count toward the limit?
  • If this service needed to handle millions of requests per second, how would you distribute the storage of these counts across multiple servers?
  • How would you handle race conditions if two redemption requests for the same user and promo arrive at the exact same time?