Given a maximum capacity, return an implementation of a fraudster cache.
Adyen's fraud team has identified that fraudsters often try multiple card numbers in short periods of time. Therefore, it's useful to keep a small list of shoppers in memory — the ones that most recently attempted fraud or were marked as fraudulent. Given that fraud detection happens before payment authorizations, the cache is expected to perform very well.
Given a maximum capacity, return an implementation of a fraudster cache.
Sample test case:
On a fraudster cache with a capacity of 2, we do the following 6 operations:
1) Mark the shopper with attributes (shopper1, 205.13.50.50, fraud@gmail.com) as fraudulent.
The cache now contains shopper1.
2) Mark the shopper with attributes (shopper2, 201.16.13.55, fraud@yahoo.com) as fraudulent.
The cache now contains shopper1 and shopper2.
3) Shopper shopper1 attempts to pay, we get them from the cache and return their details.
The fraud attempt for shopper1 is reflected in the cache.
4) Mark the shopper with attributes (shopper3, 202.56.0.17, fraud@example.com) as fraudulent.
shopper3 should be added to the cache, but we're at capacity, so we need to remove 1 of the 2 shoppers from the cache. We remove shopper2 — even though shopper1 was marked as fraud first, they recently attempted fraud.
The cache now contains shopper1 and shopper3.
5) Get shopper shopper1
Return the shopper attributes (shopper1, 205.13.50.50, fraud@gmail.com)
6) Get shopper shopper2
This shopper was removed from the cache to make room for shopper3, we no longer have their details in memory so we return null.This problem is an LRU-style cache with a fixed capacity: every <code>markFraud</code> or <code>getFraudster</code> operation makes a shopper the most recently used, and when the cache is full, the least recently used shopper must be evicted. The cleanest solution is to combine a hash-based lookup structure with an access-ordered <code>LinkedHashMap</code> or a custom doubly linked list so that updates, reads, and evictions all run in O(1) time. In the sample, shopper1 is kept because it was accessed more recently than shopper2 before shopper3 was inserted.
