Process auth requests with fraud rules
Company: Stripe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Implement a function that, given a list of Authorization Requests (timestamp_seconds, unique_id, amount, card_number, merchant), outputs a human-readable report ordered chronologically, with each line formatted as "timestamp unique_id amount APPROVE".
Extend the function to also consume a stream of Fraud Rules (time, field, value). From the rule’s time onward, any future Authorization Request whose specified field equals the rule’s value must be marked fraudulent. Produce the same report, but with "REJECT" for fraudulent requests and "APPROVE" otherwise. Include unit tests demonstrating correctness.
Quick Answer: This question evaluates a candidate's ability to implement stateful stream processing and event handling, including applying time-scoped fraud rules to authorization requests, maintaining chronological ordering, and producing verified outputs via unit tests.
You are given two lists: (1) Authorization Requests, each as a dictionary with keys time (int seconds), unique_id (string), amount (int), card_number (string), merchant (string); and (2) Fraud Rules, each as a dictionary with keys time (int seconds), field (string), value (string). From each rule's time onward (i.e., for any request with request.time >= rule.time), any future request whose specified field equals the rule's value must be marked fraudulent. Produce a chronological report of all requests as lines formatted: "time unique_id amount DECISION", where DECISION is REJECT if any rule applies, otherwise APPROVE. The report must be ordered by increasing time; for ties, preserve the original input order of requests. Valid rule fields are: unique_id, amount, card_number, merchant. For matching, compare rule.value to str(request[field]).
Constraints
- 0 <= len(requests) <= 200000
- 0 <= len(rules) <= 200000
- 0 <= time <= 10^9
- 0 <= amount <= 10^9 (integer)
- field ∈ {"unique_id", "amount", "card_number", "merchant"}
- A rule with time t applies to any request with timestamp >= t
- Report must be sorted by time ascending; if times are equal, preserve request input order
- Rule matching uses string equality: rule.value == str(request[field])
Solution
def process_authorizations(requests, rules):
# Build earliest activation time for each (field, value)
allowed_fields = {"unique_id", "amount", "card_number", "merchant"}
earliest = {}
for r in rules:
f = r.get("field")
if f not in allowed_fields:
continue
t = r["time"]
v = str(r["value"]) # compare using string equality
key = (f, v)
if key in earliest:
if t < earliest[key]:
earliest[key] = t
else:
earliest[key] = t
# Sort requests by time; stable for equal times (preserve input order)
indexed = list(enumerate(requests))
indexed.sort(key=lambda it: (it[1]["time"], it[0]))
result_lines = []
for _, req in indexed:
t = req["time"]
decision = "APPROVE"
for f in ("unique_id", "amount", "card_number", "merchant"):
v = str(req[f])
start = earliest.get((f, v))
if start is not None and start <= t:
decision = "REJECT"
break
result_lines.append(f"{t} {req['unique_id']} {req['amount']} {decision}")
return result_lines
Explanation
Compute the earliest activation time for every (field, value) pair across all rules. A request is fraudulent if any of its fields matches a pair whose activation time is less than or equal to the request's timestamp. Sorting requests by time (stable) ensures chronological output and input order preservation for ties. Comparing rule values to str(request[field]) unifies type handling for numeric and string fields.
Time complexity: O(n log n + r), where n = number of requests and r = number of rules. Space complexity: O(r) additional space for the rule index (excluding output).
Hints
- Precompute the earliest activation time for each (field, value) pair using a dictionary.
- Sort requests by time; for equal times, rely on stable sort to preserve input order.
- For each request, check if any matching (field, str(value)) has activation_time <= request.time.