1092. String Hash Set

Medium3.5 points estimatedDesignHash FunctionHash TableString3 hints
RPby Rohit Parihar

A login service keeps a blacklist of usernames and wants to answer membership questions quickly without leaning on a built-in hash table. Design StringHashSet, a set of strings that you implement yourself, using your own polynomial hash of the characters to choose a bucket.

  • add(s) inserts s; if it is already stored, nothing changes.
  • contains(s) returns true exactly when s is currently stored.
  • remove(s) deletes s if it is stored, otherwise does nothing.

Strings are case sensitive. Two different strings can land in the same bucket (or even share a hash value), so comparing hashes alone is never enough to decide equality. The structure must stay fast as it grows, however many strings are stored.

Example 1

Input:
operations = ["StringHashSet","add","add","contains","remove","contains","contains"]arguments = [[],["river"],["stone"],["river"],["river"],["river"],["stone"]]
Output:
[null,null,null,true,null,false,true]
Explanation:

Both strings are added; after river is removed only stone is still reported as present.

Example 2

Input:
operations = ["StringHashSet","add","contains","add","contains","remove","contains","contains"]arguments = [[],["Aa"],["BB"],["BB"],["Aa"],["Aa"],["Aa"],["BB"]]
Output:
[null,null,false,null,true,null,false,true]
Explanation:

Aa and BB collide under many simple hashes, yet they are different strings, so each one is found only after it is added.

Example 3

Input:
operations = ["StringHashSet","add","add","remove","contains","remove","remove"]arguments = [[],["x7"],["x7"],["x7"],["x7"],["x7"],["y"]]
Output:
[null,null,null,null,false,null,null]
Explanation:

Adding x7 twice stores it once, so one removal empties it; removing an absent string does nothing.

Constraints

1 ≤ number of operations ≤ 2 * 105

1 ≤ s.length ≤ 20

s consists of ASCII letters and digits only

Build the table yourself rather than relying on a built-in hash set or map

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(L) per operation on average
Space
O(total characters stored)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.