How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Affirm.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Affirm during technical interviews.

Determine Redeemable Promotion Offers | Affirm Coding Question

Q: Determine Redeemable Promotion Offers

This question evaluates proficiency in event-stream processing, stateful counting, timestamp filtering, and enforcing business constraints for limited-use promotions, testing skills in date/time handling, aggregation, and mapping of user-event data.

Determine Redeemable Promotion Offers

Company: Affirm

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given predefined objects for promotion offers and user redemption events. A `PromotionOffer` has: - `offer_id` - `start_time` - `end_time` - `max_redeems_per_user`, the maximum number of times one user may redeem this offer A `RedeemEvent` has: - `user_id` - `timestamp` - `action`, either `"redeem"` or `"unredeem"` - `offer_id` Given a list of promotion offers and a list of redeem events, determine which offers each user can still redeem as of the end of `2015-12-31`. Rules: - Only events with `timestamp <= 2015-12-31 23:59:59` should affect the result. - A `redeem` event increases that user's active redemption count for the corresponding offer by `1`. - An `unredeem` event decreases that user's active redemption count for the corresponding offer by `1`, but the count should not go below `0`. - A user can redeem an offer if: - the offer is active on `2015-12-31`, meaning `start_time <= 2015-12-31 23:59:59 <= end_time`; and - the user's active redemption count for that offer is less than `max_redeems_per_user`. Return a mapping from each user who appears in the event list to the list of offer IDs that the user can still redeem.

Quick Answer: This question evaluates proficiency in event-stream processing, stateful counting, timestamp filtering, and enforcing business constraints for limited-use promotions, testing skills in date/time handling, aggregation, and mapping of user-event data.

You are given two lists of dictionaries representing promotion offers and user redemption events. Each offer dictionary has these fields: - `offer_id`: a string ID - `start_time`: string in `YYYY-MM-DD HH:MM:SS` format - `end_time`: string in `YYYY-MM-DD HH:MM:SS` format - `max_redeems_per_user`: maximum number of active redeems one user may have for this offer Each event dictionary has these fields: - `user_id`: a string ID - `timestamp`: string in `YYYY-MM-DD HH:MM:SS` format - `action`: either `"redeem"` or `"unredeem"` - `offer_id`: the offer affected by the event As of the cutoff time `2015-12-31 23:59:59`, determine which offers each user can still redeem. Rules: - Only events with `timestamp <= 2015-12-31 23:59:59` affect the final counts. - A `redeem` event increases that user's active redemption count for that offer by 1. - An `unredeem` event decreases that user's active redemption count for that offer by 1, but the count must never go below 0. - A user can still redeem an offer if: - the offer is active at the cutoff time, meaning `start_time <= cutoff <= end_time`, and - the user's active redemption count for that offer is less than `max_redeems_per_user`. Return a dictionary mapping every user who appears anywhere in the event list to a sorted list of offer IDs that the user can still redeem at the cutoff time. Sort each user's offer list lexicographically.

Constraints

0 <= len(offers) <= 10^5
0 <= len(events) <= 10^5
All timestamps use the exact format `YYYY-MM-DD HH:MM:SS`
Each `offer_id` and `user_id` is a string
`max_redeems_per_user` is a non-negative integer

Examples

Input: ([{'offer_id': 'A', 'start_time': '2015-01-01 00:00:00', 'end_time': '2015-12-31 23:59:59', 'max_redeems_per_user': 2}, {'offer_id': 'B', 'start_time': '2015-06-01 00:00:00', 'end_time': '2016-06-01 00:00:00', 'max_redeems_per_user': 1}, {'offer_id': 'C', 'start_time': '2015-01-01 00:00:00', 'end_time': '2015-12-01 00:00:00', 'max_redeems_per_user': 5}], [{'user_id': 'u1', 'timestamp': '2015-01-10 10:00:00', 'action': 'redeem', 'offer_id': 'A'}, {'user_id': 'u1', 'timestamp': '2015-12-30 09:00:00', 'action': 'redeem', 'offer_id': 'B'}, {'user_id': 'u1', 'timestamp': '2015-12-31 12:00:00', 'action': 'unredeem', 'offer_id': 'B'}, {'user_id': 'u2', 'timestamp': '2015-11-01 10:00:00', 'action': 'redeem', 'offer_id': 'A'}, {'user_id': 'u2', 'timestamp': '2015-11-02 10:00:00', 'action': 'redeem', 'offer_id': 'A'}, {'user_id': 'u2', 'timestamp': '2015-11-05 10:00:00', 'action': 'unredeem', 'offer_id': 'A'}, {'user_id': 'u2', 'timestamp': '2015-06-01 10:00:00', 'action': 'redeem', 'offer_id': 'C'}, {'user_id': 'u3', 'timestamp': '2016-01-01 00:00:00', 'action': 'redeem', 'offer_id': 'A'}])

Expected Output: {'u1': ['A', 'B'], 'u2': ['A', 'B'], 'u3': ['A', 'B']}

Explanation: Only A and B are active at the cutoff. u1 has A count 1 and B count 0. u2 has A count 1. u3 appears in the event list, but their only event is after the cutoff, so their counts are 0 for all active offers.

Input: ([{'offer_id': 'X', 'start_time': '2015-01-01 00:00:00', 'end_time': '2015-12-31 23:59:59', 'max_redeems_per_user': 1}, {'offer_id': 'Y', 'start_time': '2015-12-31 23:59:59', 'end_time': '2016-01-31 00:00:00', 'max_redeems_per_user': 2}, {'offer_id': 'Z', 'start_time': '2016-01-01 00:00:00', 'end_time': '2016-12-31 23:59:59', 'max_redeems_per_user': 1}], [{'user_id': 'alice', 'timestamp': '2015-03-01 00:00:00', 'action': 'unredeem', 'offer_id': 'X'}, {'user_id': 'alice', 'timestamp': '2015-12-31 23:59:59', 'action': 'redeem', 'offer_id': 'Y'}, {'user_id': 'bob', 'timestamp': '2015-12-31 23:59:58', 'action': 'redeem', 'offer_id': 'X'}, {'user_id': 'bob', 'timestamp': '2015-12-31 23:59:59', 'action': 'unredeem', 'offer_id': 'X'}, {'user_id': 'charlie', 'timestamp': '2015-07-01 10:00:00', 'action': 'redeem', 'offer_id': 'X'}, {'user_id': 'charlie', 'timestamp': '2015-12-30 10:00:00', 'action': 'redeem', 'offer_id': 'Y'}])

Expected Output: {'alice': ['X', 'Y'], 'bob': ['X', 'Y'], 'charlie': ['Y']}

Explanation: X and Y are active at the cutoff. Alice's unredeem on X does not make the count negative. Bob redeems and then unreedeems X back to 0. Charlie has X count 1, which equals its max, so X is no longer redeemable for Charlie.

Input: ([{'offer_id': 'D', 'start_time': '2015-01-01 00:00:00', 'end_time': '2016-01-01 00:00:00', 'max_redeems_per_user': 1}, {'offer_id': 'E', 'start_time': '2015-01-01 00:00:00', 'end_time': '2015-12-31 23:59:59', 'max_redeems_per_user': 3}], [{'user_id': 'u1', 'timestamp': '2015-12-31 23:59:59', 'action': 'redeem', 'offer_id': 'D'}, {'user_id': 'u1', 'timestamp': '2016-01-01 00:00:00', 'action': 'unredeem', 'offer_id': 'D'}, {'user_id': 'u1', 'timestamp': '2015-01-01 00:00:00', 'action': 'redeem', 'offer_id': 'E'}, {'user_id': 'u1', 'timestamp': '2015-06-01 00:00:00', 'action': 'redeem', 'offer_id': 'E'}, {'user_id': 'u1', 'timestamp': '2015-12-01 00:00:00', 'action': 'redeem', 'offer_id': 'E'}, {'user_id': 'u2', 'timestamp': '2016-01-02 00:00:00', 'action': 'redeem', 'offer_id': 'D'}])

Expected Output: {'u1': [], 'u2': ['D', 'E']}

Explanation: The future unredeem for u1 does not count, so u1 still has D count 1 and E count 3, both at their per-user limits. u2 appears in the event list but has no effective events before the cutoff, so both active offers are still available.

Input: ([{'offer_id': 'ONLY', 'start_time': '2015-01-01 00:00:00', 'end_time': '2015-12-31 23:59:59', 'max_redeems_per_user': 1}], [])

Expected Output: {}

Explanation: No users appear in the event list, so the result is an empty mapping.

Input: ([], [{'user_id': 'solo', 'timestamp': '2015-01-01 00:00:00', 'action': 'redeem', 'offer_id': 'M'}, {'user_id': 'solo', 'timestamp': '2015-01-02 00:00:00', 'action': 'unredeem', 'offer_id': 'M'}, {'user_id': 'pair', 'timestamp': '2016-01-01 00:00:00', 'action': 'redeem', 'offer_id': 'N'}])

Expected Output: {'pair': [], 'solo': []}

Explanation: There are no offers at all, but both users appear in the event list, so each must map to an empty list.

Hints

First identify which offers are active at the cutoff time. Inactive offers can never appear in the answer.
Track active redemption counts with a hash map keyed by `(user_id, offer_id)` or with nested dictionaries. Be careful that `unredeem` cannot make a count negative.

Quick Overview

This question evaluates proficiency in event-stream processing, stateful counting, timestamp filtering, and enforcing business constraints for limited-use promotions, testing skills in date/time handling, aggregation, and mapping of user-event data.