CareerCup

We can keep a system of credit cards in Ternary Search Trie like structure.
Value at the end of the credit card would be true or false specifying that the card is fraud or not.
To get the changes new changes , we need a trigger from the system when a card is marked as fraud, so that we will add/update the credit card in Trie system.

1. Have a credit card cache, partitioned into good and fraud.
2. When a card belong to any of the above, then do due diligence.
3. When a card belongs to neither, call the website and get the latest fraud card list.
4. Update the card cache, move from good to fraud.
5. Now, if the card is still in neither, then add the card to the good card cache.

Issue : with [2]. But it can never be fixed, really.

This problem mainly deals with the storage of fraud credit cards. System should return whether the credit card details provided are proper or fraud in optimum time.

So, efficient storing the list of fraud cards includes
a.) Use optimum space.
b.) Check if credit card is already present in list or not in minimal time
c.) Insert new list of credit cards to the existing storage
d.) Deleting existing card from storage if required

Once we get the information whether the credit card is fine or fraud, we can proceed further as per requirement.

To solve the storage problem in our system, we can use hash table . but in this case, we need to design a good hash function.
Alternatively, we can use trie as well to store the credit card info

I think the problem here is with the cache. If we cache the list of fraud cards then a fraud card can exists in the original fraud cards list but not in our cache. So the problem is, when do we update our cache? I suppose that usually most of the cards of the users are not fraud cards, so updating each time a card is not in our fraud cards list could be computationally expensive.

Probably there are more specifications that you can ask to the amazon's interviewer. For example you can maybe query the external service to know if there were any changes in the list.

Can we use bloom filter concept here too?

Ravi, yes, I was just going to mention bloom filter, I think it's the perfect application for it.
Instead of making an expensive data store look up to see if a card is fraud every time somebody makes a transaction, which there would be many, we should keep a bloom filter in the memory.

How does Bloom Filter helps here ? Bloom Filter has the issue of false positives. Suppose we keep all the fraudulent credit cards details in the bloom filter, when we get a new card it is possible when we may return a proper card as fraudulent when it is not.