Validate password service

  • 5

    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 requirements:

    1. The method needs to be extremely fast;
    2. The list of known bad passwords is huge: more than 1 billion
    3. The list of known bad passwords keeps being updated constantly.

  • 1

    We can maintain a trie for storing, updating and searching bad passwords.

  • 1

    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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.