Design a service that validates the password. You're given a collection of known bad passwords. Your service API has only one method: bool isBadPassword(String password). When the password is one of the known bad passwords, it returns true; otherwise it returns false. For simplicity, the matching is plain string comparison (case sensitive).
- The method needs to be extremely fast;
- The list of known bad passwords is huge: more than 1 billion
- The list of known bad passwords keeps being updated constantly.
Not too difficult, a radix tree should work great here.
Set up a radix tree of the bad password dictionary and once the user leaves focus of the input field traverse the pre-built radix tree. One great optimization I can think of off the bat is implementing a Bloom filter on top of the database. That'll leave out all the good passwords from triggering the traversal.