Transaction Network: Detect Fraud Cycles and Compute Net Flow Between Accounts in a Payment Graph

Question

## Problem

You have a directed payment network where edge `(u, v, amount)` means account `u` sent `amount` to account `v`. Implement:
- `net_flow(account) -> int` -- return total received minus total sent for an account.
- `detect_cycle() -> list[int] | None` -- return any cycle of transactions, or None if the graph is acyclic.
- `largest_component() -> list[int]` -- return the accounts in the largest weakly connected component.

```python
class TransactionNetwork:
    def __init__(self, transactions: list[tuple[int,int,int]]): ...
    def net_flow(self, account: int) -> int: ...
    def detect_cycle(self) -> list[int] | None: ...
    def largest_component(self) -> list[int]: ...
```

**Example:**
```
txns = [(1,2,100),(2,3,50),(3,1,30),(4,5,200)]
net_flow(1) -> 30 - 100 = -70
detect_cycle() -> [1,2,3]  # or equivalent cycle
largest_component() -> [1,2,3]
```

## Follow-ups
1. DFS cycle detection uses a color-marking scheme. Walk through it on the example above.
2. How would you flag suspicious cycles: transactions that loop back within 24 hours with amounts above a threshold?
3. Extend `net_flow` to return per-currency breakdowns when transactions have a currency field.
4. The network grows by 10,000 edges per second. How do you maintain cycle detection incrementally?

Transaction Network: Detect Fraud Cycles and Compute Net Flow Between Accounts in a Payment Graph

Question Details

Full Details

Topics

More from Square/Block