"""
PROBLEM: Fraudulent Transaction Detection
Stripe processes billions of transactions daily. To protect merchants, we need to
identify potentially fraudulent transactions based on user behavior patterns.
A transaction is considered SUSPICIOUS if ANY of the following conditions are met:
1. The user makes more than 3 transactions within any 60-second window
2. The user's transactions in any 60-second window exceed $3000 total
3. The user makes a transaction from a different city within 30 minutes of a previous
transaction (impossible travel)
You are given a list of transactions, where each transaction is formatted as:
"timestamp,user_id,amount,city"
- timestamp: Unix timestamp (integer, seconds)
- user_id: String identifier for the user
- amount: Transaction amount in dollars (float)
- city: City where transaction occurred (string)
Return a list of transaction indices (0-indexed) that are SUSPICIOUS, sorted in
ascending order.
EXAMPLES:
Input: [
"1609459200,user1,100.00,NYC", # 0: OK
"1609459210,user1,200.00,NYC", # 1: OK
"1609459220,user1,300.00,NYC", # 2: OK
"1609459230,user1,400.00,NYC", # 3: SUSPICIOUS (4th transaction in 60s)
"1609459300,user2,3500.00,LA", # 4: SUSPICIOUS (exceeds $3000)
"1609462000,user1,50.00,Chicago", # 5: OK (2800 seconds / ~46 min later)
]
Output: [3, 4]
Input: [
"1609459200,user1,100.00,NYC", # 0: OK
"1609459500,user1,200.00,LA", # 1: SUSPICIOUS (different city within 30 min)
]
Output: [1]
CONSTRAINTS:
- 1 <= len(transactions) <= 100,000
- All timestamps are valid Unix timestamps
- 0 < amount <= 100,000
- user_id contains only alphanumeric characters
- city contains only alphabetic characters
"""
from collections import defaultdict
from typing import List
def find_suspicious_transactions(transactions: List[str]) -> List[int]:
"""
Identify suspicious transactions based on fraud detection rules.
Time Complexity: O(n * m) where n = number of transactions,
m = max transactions per user in a 60-second window
Space Complexity: O(n) for storing parsed transactions
"""
# Parse all transactions
parsed = []
for i, txn in enumerate(transactions):
parts = txn.split(',')
timestamp = int(parts[0])
user_id = parts[1]
amount = float(parts[2])
city = parts[3]
parsed.append({
'index': i,
'timestamp': timestamp,
'user_id': user_id,
'amount': amount,
'city': city
})
# Group transactions by user for efficient processing
user_transactions = defaultdict(list)
for txn in parsed:
user_transactions[txn['user_id']].append(txn)
# Sort each user's transactions by timestamp
for user_id in user_transactions:
user_transactions[user_id].sort(key=lambda x: x['timestamp'])
suspicious = set()
for user_id, txns in user_transactions.items():
for i, current_txn in enumerate(txns):
current_time = current_txn['timestamp']
# Check rules within 60-second window (Rules 1 & 2)
window_start = current_time - 60
window_txns = []
window_amount = 0
for j in range(i, -1, -1): # Look backwards from current
if txns[j]['timestamp'] >= window_start:
window_txns.append(txns[j])
window_amount += txns[j]['amount']
else:
break
# Rule 1: More than 3 transactions in 60-second window
if len(window_txns) > 3:
suspicious.add(current_txn['index'])
# Rule 2: Total amount exceeds $3000 in 60-second window
if window_amount > 3000:
suspicious.add(current_txn['index'])
# Rule 3: Different city within 30 minutes (impossible travel)
if i > 0:
thirty_min_ago = current_time - 1800 # 30 * 60 = 1800 seconds
for j in range(i - 1, -1, -1):
prev_txn = txns[j]
if prev_txn['timestamp'] >= thirty_min_ago:
if prev_txn['city'] != current_txn['city']:
suspicious.add(current_txn['index'])
break
else:
break
return sorted(list(suspicious))
# ============================================================================
# TEST CASES
# ============================================================================
def test_find_suspicious_transactions():
# Test Case 1: More than 3 transactions in 60 seconds
transactions1 = [
"1609459200,user1,100.00,NYC",
"1609459210,user1,200.00,NYC",
"1609459220,user1,300.00,NYC",
"1609459230,user1,400.00,NYC", # 4th transaction - suspicious
"1609459300,user2,100.00,LA",
]
result1 = find_suspicious_transactions(transactions1)
assert result1 == [3], f"Test 1 failed: expected [3], got {result1}"
print("✓ Test 1 passed: Detects >3 transactions in 60s window")
# Test Case 2: Amount exceeds $3000 in 60-second window
transactions2 = [
"1609459200,user1,1000.00,NYC",
"1609459210,user1,1500.00,NYC",
"1609459220,user1,600.00,NYC", # Total now $3100 - suspicious
]
result2 = find_suspicious_transactions(transactions2)
assert result2 == [2], f"Test 2 failed: expected [2], got {result2}"
print("✓ Test 2 passed: Detects amount >$3000 in 60s window")
# Test Case 3: Impossible travel (different city within 30 min)
transactions3 = [
"1609459200,user1,100.00,NYC",
"1609459500,user1,200.00,LA", # Different city, only 5 min later
]
result3 = find_suspicious_transactions(transactions3)
assert result3 == [1], f"Test 3 failed: expected [1], got {result3}"
print("✓ Test 3 passed: Detects impossible travel")
# Test Case 4: Same city within 30 min is OK
transactions4 = [
"1609459200,user1,100.00,NYC",
"1609459500,user1,200.00,NYC", # Same city - OK
]
result4 = find_suspicious_transactions(transactions4)
assert result4 == [], f"Test 4 failed: expected [], got {result4}"
print("✓ Test 4 passed: Same city transactions are not flagged")
# Test Case 5: Multiple users don't affect each other
transactions5 = [
"1609459200,user1,100.00,NYC",
"1609459210,user2,200.00,LA",
"1609459220,user1,300.00,NYC",
"1609459230,user2,400.00,LA",
]
result5 = find_suspicious_transactions(transactions5)
assert result5 == [], f"Test 5 failed: expected [], got {result5}"
print("✓ Test 5 passed: Different users are independent")
# Test Case 6: Multiple rules violated
transactions6 = [
"1609459200,user1,2000.00,NYC",
"1609459210,user1,500.00,NYC",
"1609459220,user1,300.00,NYC",
"1609459230,user1,400.00,LA", # >3 txns, >$3000, different city
]
result6 = find_suspicious_transactions(transactions6)
assert result6 == [3], f"Test 6 failed: expected [3], got {result6}"
print("✓ Test 6 passed: Multiple violations on same transaction")
# Test Case 7: Window resets after 60 seconds
transactions7 = [
"1609459200,user1,100.00,NYC",
"1609459210,user1,200.00,NYC",
"1609459220,user1,300.00,NYC",
"1609459400,user1,400.00,NYC", # 200 seconds later - new window
"1609459410,user1,500.00,NYC",
"1609459420,user1,600.00,NYC",
]
result7 = find_suspicious_transactions(transactions7)
assert result7 == [], f"Test 7 failed: expected [], got {result7}"
print("✓ Test 7 passed: 60-second window resets properly")
# Test Case 8: Large single transaction
transactions8 = [
"1609459200,user1,3500.00,NYC", # Single transaction >$3000
]
result8 = find_suspicious_transactions(transactions8)
assert result8 == [0], f"Test 8 failed: expected [0], got {result8}"
print("✓ Test 8 passed: Single large transaction flagged")
# Test Case 9: Edge case - exactly 3 transactions (should be OK)
transactions9 = [
"1609459200,user1,100.00,NYC",
"1609459210,user1,200.00,NYC",
"1609459220,user1,300.00,NYC",
]
result9 = find_suspicious_transactions(transactions9)
assert result9 == [], f"Test 9 failed: expected [], got {result9}"
print("✓ Test 9 passed: Exactly 3 transactions is not suspicious")
# Test Case 10: Edge case - exactly $3000 (should be OK)
transactions10 = [
"1609459200,user1,1000.00,NYC",
"1609459210,user1,1000.00,NYC",
"1609459220,user1,1000.00,NYC",
]
result10 = find_suspicious_transactions(transactions10)
assert result10 == [], f"Test 10 failed: expected [], got {result10}"
print("✓ Test 10 passed: Exactly $3000 is not suspicious")
print("\n" + "="*50)
print("All tests passed! ✓")
print("="*50)
if __name__ == "__main__":
test_find_suspicious_transactions()
# Example from problem description
print("\n--- Running Example from Problem Description ---\n")
example = [
"1609459200,user1,100.00,NYC",
"1609459210,user1,200.00,NYC",
"1609459220,user1,300.00,NYC",
"1609459230,user1,400.00,NYC",
"1609459300,user2,3500.00,LA",
"1609462000,user1,50.00,Chicago", # 46 min later, different city OK
]
result = find_suspicious_transactions(example)
print(f"Input transactions: {len(example)} transactions")
print(f"Suspicious indices: {result}")
print(f"Expected: [3, 4]")