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 Plaid.

What role is this question designed for?

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

Design a coupon redemption system | Plaid Coding Question

Quick Overview

This question evaluates proficiency in data structures and algorithms for building an in-memory service, including efficient lookup/update strategies, expiration handling, limit enforcement, idempotency, concurrency considerations, and time/space complexity reasoning.

Design a coupon redemption system

Company: Plaid

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory coupon service supporting: addCoupon(code, discount, expiresAt, totalLimit, perUserLimit); redeem(userId, code, now) -> success/discountApplied; and getRemaining(code, now). Choose data structures to achieve O( 1) average lookups and updates (e.g., hash maps plus a structure for expirations). Analyze time/space complexity. Handle edge cases: invalid or duplicate codes, expired coupons, zero/negative discounts, exceeding global/per-user limits, clock skew/daylight-saving near expiresAt, and idempotent retries. Follow-up: extend to support category restrictions, minimum spend thresholds, and bulk input parsing.

Quick Answer: This question evaluates proficiency in data structures and algorithms for building an in-memory service, including efficient lookup/update strategies, expiration handling, limit enforcement, idempotency, concurrency considerations, and time/space complexity reasoning.

Part 1: In-Memory Coupon Redemption Engine

Implement an in-memory coupon service that processes a list of operations and returns the result of each operation in order. You must support average O(1) lookups and updates using hash-map-style data structures. Each operation is one of: - ('ADD', code, discount, expiresAt, totalLimit, perUserLimit) - ('REDEEM', userId, code, now, requestId) - ('GET', code, now) Rules: - A coupon is valid only when now < expiresAt. - ADD returns True if the coupon is created, otherwise False. - ADD fails if the code is empty, already exists, discount <= 0, expiresAt < 0, totalLimit <= 0, or perUserLimit <= 0. - REDEEM returns (success, discountApplied). - REDEEM succeeds only if the coupon exists, is not expired, has remaining global uses, and the user has not exceeded the per-user limit. - GET returns the remaining global redemptions for that code at time now; return 0 if the coupon does not exist or is expired. - requestId is an idempotency key. If the same requestId appears again, return the exact same previous redeem result without changing state again. - All times are integer UTC timestamps; use direct numeric comparison only.

Constraints

0 <= len(operations) <= 200000
code, userId, and requestId are strings without spaces
0 <= expiresAt, now <= 10^9
For a valid ADD, discount, totalLimit, and perUserLimit are positive integers
If a requestId repeats, it represents a retry of the same logical redeem request

Examples

Input: ([('ADD', 'SAVE10', 10, 100, 2, 1), ('GET', 'SAVE10', 50), ('REDEEM', 'u1', 'SAVE10', 60, 'req1'), ('REDEEM', 'u1', 'SAVE10', 70, 'req1'), ('GET', 'SAVE10', 80), ('REDEEM', 'u1', 'SAVE10', 90, 'req2'), ('REDEEM', 'u2', 'SAVE10', 90, 'req3'), ('GET', 'SAVE10', 90)],)

Expected Output: [True, 2, (True, 10), (True, 10), 1, (False, 0), (True, 10), 0]

Explanation: The second redeem with requestId 'req1' is an idempotent retry, so it returns the cached result and does not consume another use.

Input: ([('ADD', 'BAD', 0, 50, 3, 1), ('ADD', 'A', 5, 10, 1, 1), ('ADD', 'A', 7, 20, 2, 2), ('REDEEM', 'u1', 'MISSING', 5, 'r1'), ('GET', 'MISSING', 5)],)

Expected Output: [False, True, False, (False, 0), 0]

Explanation: Invalid discount makes the first ADD fail; duplicate code makes the third ADD fail.

Hints

Use one hash map from coupon code to coupon state, and a second hash map from requestId to the previously returned redeem result.
Store per-user redemption counts inside each coupon so checking the per-user limit stays O(1) average.

Part 2: Coupon Engine with Category Rules, Minimum Spend, and Bulk Parsing

Extend the coupon system to support category restrictions, minimum spend thresholds, and bulk input parsing. You are given a list of command strings. Parse each command and execute it, returning one result per command. Command formats: - ADD code discount expiresAt totalLimit perUserLimit minSpend categories - REDEEM userId code now spend category requestId - GET code now Rules: - categories is either '*' meaning all categories, or a comma-separated list such as grocery,electronics. - A coupon is valid only when now < expiresAt. - A redeem succeeds only if the coupon exists, is unexpired, has remaining global uses, the user is under the per-user limit, spend >= minSpend, and the category is allowed. - ADD returns True if created, otherwise False. - ADD fails semantically if the code is empty or duplicate, discount <= 0, expiresAt < 0, totalLimit <= 0, perUserLimit <= 0, minSpend < 0, or the category list is empty after parsing. - REDEEM returns (success, discountApplied). - GET returns remaining global uses, or 0 for missing/expired coupons. - requestId is idempotent exactly as in Part 1. - If a command is malformed or contains a numeric field that cannot be parsed as an integer, return 'ERROR' for that command and continue processing the rest. - Ignore extra calendar logic; times are integer UTC timestamps.

Constraints

0 <= len(commands) <= 200000
Total length of all command strings <= 10^6
Codes, user IDs, request IDs, and category names contain no spaces
A repeated requestId indicates an idempotent retry of the same logical redeem request
Malformed commands should not stop processing; they produce 'ERROR'

Examples

Input: (['ADD SAVE10 10 100 3 2 50 grocery,electronics', 'REDEEM u1 SAVE10 60 30 grocery r1', 'REDEEM u1 SAVE10 60 80 fashion r2', 'REDEEM u1 SAVE10 60 80 grocery r3', 'GET SAVE10 70'],)

Expected Output: [True, (False, 0), (False, 0), (True, 10), 2]

Explanation: The first redeem fails minSpend, the second fails category restriction, and the third succeeds.

Input: (['ADD ANY5 5 20 1 1 0 *', 'REDEEM u1 ANY5 10 0 books x1', 'REDEEM u1 ANY5 10 0 books x1', 'REDEEM u2 ANY5 15 100 books x2', 'GET ANY5 15'],)

Expected Output: [True, (True, 5), (True, 5), (False, 0), 0]

Explanation: Wildcard categories allow any category. The second redeem is an idempotent retry and does not consume another use.

Hints

Split and validate each command before touching state. Keep parse errors separate from business-rule failures.
Store allowed categories as a set for O(1) average membership checks; use None or a special marker for '*' meaning all categories.

Quick Overview