call(back)
Algorithms & Data StructuresmediumSign in to star problems

Filter With a Dynamic Blacklist

Design BlacklistFilter, a stream filter whose blacklist changes while items flow:

publish(item)    // item is words separated by spaces
block(word)      // from now on, items containing word are held back
unblock(word)    // held items that no longer contain any blocked word are emitted now, in publish order
emitted()        // every item emitted so far, in order

An item is held if any of its words is blocked at publish time. Emitting is final: blocking a word later never retracts an item.

block("spam") · publish("buy spam now") · publish("hello")
emitted()  ->  ["hello"]
unblock("spam") · emitted()  ->  ["hello", "buy spam now"]

Hints

Hint 1

Three pieces of state: the blocked set, the held list in publish order, and the emitted list.

Hint 2

publish checks the item against the set and routes it; unblock walks the held list once, emitting what is now clean and keeping the rest in order.

Asked at