Design a coupon redemption system
Company: Plaid
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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
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.
Input: ([('ADD', 'X', 5, 10, 1, 1), ('REDEEM', 'u1', 'X', 10, 'r1'), ('GET', 'X', 9), ('GET', 'X', 10)],)
Expected Output: [True, (False, 0), 1, 0]
Explanation: Expiry is exclusive: the coupon is valid only when now < expiresAt, so now == 10 is already expired.
Input: ([],)
Expected Output: []
Explanation: Edge case: no operations.
Solution
def solution(operations):
coupons = {}
request_cache = {}
results = []
for op in operations:
op_type = op[0]
if op_type == 'ADD':
_, code, discount, expires_at, total_limit, per_user_limit = op
if (not isinstance(code, str) or code == '' or code in coupons or discount <= 0 or expires_at < 0 or total_limit <= 0 or per_user_limit <= 0):
results.append(False)
continue
coupons[code] = {
'discount': discount,
'expires_at': expires_at,
'total_limit': total_limit,
'per_user_limit': per_user_limit,
'used': 0,
'user_used': {}
}
results.append(True)
elif op_type == 'REDEEM':
_, user_id, code, now, request_id = op
if request_id in request_cache:
results.append(request_cache[request_id])
continue
result = (False, 0)
coupon = coupons.get(code)
if coupon is not None and now < coupon['expires_at']:
used_by_user = coupon['user_used'].get(user_id, 0)
if coupon['used'] < coupon['total_limit'] and used_by_user < coupon['per_user_limit']:
coupon['used'] += 1
coupon['user_used'][user_id] = used_by_user + 1
result = (True, coupon['discount'])
request_cache[request_id] = result
results.append(result)
elif op_type == 'GET':
_, code, now = op
coupon = coupons.get(code)
if coupon is None or now >= coupon['expires_at']:
results.append(0)
else:
results.append(coupon['total_limit'] - coupon['used'])
else:
raise ValueError('Unknown operation type')
return resultsTime complexity: O(1) average per operation; O(n) total for n operations. Space complexity: O(C + U + R), where C is the number of coupons, U is the total number of stored per-user counters across all coupons, and R is the number of unique redeem requestIds.
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
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.
Input: (['ADD BAD 0 10 1 1 0 *', 'ADD X 5 10 1 1 0 electronics', 'ADD X 6 20 2 2 10 electronics', 'REDEEM u1 X nope 20 electronics r1', 'GET X', 'BLAH something'],)
Expected Output: [False, True, False, 'ERROR', 'ERROR', 'ERROR']
Explanation: Semantic invalidity on ADD returns False; malformed commands or unparsable integers return 'ERROR'.
Input: (['ADD LATE 9 10 2 1 0 home', 'GET LATE 10', 'REDEEM u1 LATE 10 50 home r1'],)
Expected Output: [True, 0, (False, 0)]
Explanation: Expiry is exclusive, so now == expiresAt means expired.
Input: ([],)
Expected Output: []
Explanation: Edge case: empty bulk input.
Solution
def solution(commands):
coupons = {}
request_cache = {}
results = []
for raw in commands:
if not isinstance(raw, str):
results.append('ERROR')
continue
parts = raw.strip().split()
if not parts:
results.append('ERROR')
continue
cmd = parts[0]
if cmd == 'ADD':
if len(parts) != 8:
results.append('ERROR')
continue
_, code, discount_s, expires_s, total_s, per_user_s, min_spend_s, categories_s = parts
try:
discount = int(discount_s)
expires_at = int(expires_s)
total_limit = int(total_s)
per_user_limit = int(per_user_s)
min_spend = int(min_spend_s)
except ValueError:
results.append('ERROR')
continue
if (code == '' or code in coupons or discount <= 0 or expires_at < 0 or total_limit <= 0 or per_user_limit <= 0 or min_spend < 0):
results.append(False)
continue
if categories_s == '*':
categories = None
else:
categories = {cat for cat in categories_s.split(',') if cat}
if not categories:
results.append(False)
continue
coupons[code] = {
'discount': discount,
'expires_at': expires_at,
'total_limit': total_limit,
'per_user_limit': per_user_limit,
'min_spend': min_spend,
'categories': categories,
'used': 0,
'user_used': {}
}
results.append(True)
elif cmd == 'REDEEM':
if len(parts) != 7:
results.append('ERROR')
continue
_, user_id, code, now_s, spend_s, category, request_id = parts
try:
now = int(now_s)
spend = int(spend_s)
except ValueError:
results.append('ERROR')
continue
if request_id in request_cache:
results.append(request_cache[request_id])
continue
result = (False, 0)
coupon = coupons.get(code)
if coupon is not None and now < coupon['expires_at']:
category_ok = coupon['categories'] is None or category in coupon['categories']
spend_ok = spend >= coupon['min_spend']
used_by_user = coupon['user_used'].get(user_id, 0)
if (category_ok and spend_ok and coupon['used'] < coupon['total_limit'] and used_by_user < coupon['per_user_limit']):
coupon['used'] += 1
coupon['user_used'][user_id] = used_by_user + 1
result = (True, coupon['discount'])
request_cache[request_id] = result
results.append(result)
elif cmd == 'GET':
if len(parts) != 3:
results.append('ERROR')
continue
_, code, now_s = parts
try:
now = int(now_s)
except ValueError:
results.append('ERROR')
continue
coupon = coupons.get(code)
if coupon is None or now >= coupon['expires_at']:
results.append(0)
else:
results.append(coupon['total_limit'] - coupon['used'])
else:
results.append('ERROR')
return resultsTime complexity: O(total input size) overall; equivalently O(1) average per GET/REDEEM and O(k) for an ADD with k listed categories, plus command parsing cost. Space complexity: O(C + U + R + G), where C is coupons, U is stored per-user counters, R is unique redeem requestIds, and G is the total number of stored category names.
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.