Real-Time Transaction Anomaly Detector

Problem Context

You are building a fraud detection system for a financial platform. As transactions arrive one by one in a stream, your system must flag any transaction as anomalous if its amount is significantly higher than recent activity for that account.

Specifically, a transaction is considered anomalous if its amount is strictly greater than k times the median of the last w transactions for that account (not including the current transaction). If an account has fewer than w prior transactions, use all available prior transactions to compute the median. If an account has no prior transactions, the transaction is not anomalous.

Input/Output Format

Function Signature:

def detect_anomalies(transactions: List[Tuple[str, float]], w: int, k: float) -> List[bool]

Input:

• transactions: A list of tuples (account_id, amount) representing the stream of transactions in chronological order.
• w: The sliding window size (number of prior transactions to consider).
• k: The multiplier threshold.

Output:

• A list of booleans of the same length as transactions, where True means the corresponding transaction is anomalous.

Examples

Example 1

Input: transactions = [("A", 10), ("A", 12), ("A", 11), ("A", 100)], w = 3, k = 3 Output: [false, false, false, true] Explanation:

• Tx 0 (A, 10): No prior txns → not anomalous.
• Tx 1 (A, 12): Prior txns = [10], median = 10. 12 > 3×10=30? No.
• Tx 2 (A, 11): Prior txns = [10, 12], median = 11. 11 > 3×11=33? No.
• Tx 3 (A, 100): Prior txns = [10, 12, 11] (last 3), median = 11. 100 > 3×11=33? Yes → anomalous.

Example 2

Input: transactions = [("A", 5), ("B", 200), ("A", 6), ("B", 201), ("A", 500)], w = 2, k = 2 Output: [false, false, false, false, true] Explanation:

• Each account is tracked independently. A's prior txns before tx 4 are [5, 6], median = 5.5. 500 > 2×5.5=11? Yes → anomalous. B's transactions are normal relative to each other.