Document Store With Boolean Queries
Design DocumentStore:
insertDoc(id, text) // text is words separated by whitespace; inserting an id again replaces its document query(expression) // the ids of the documents that satisfy the expression, sorted
An expression is built from words, &&, ||, ! and parentheses, with ! binding tightest and && tighter than ||. A document satisfies a word when it contains that word exactly (case-sensitive).
insertDoc("d1", "apple banana") · insertDoc("d2", "banana cherry") · insertDoc("d3", "cherry apple pie")
query("apple && banana") -> ["d1"]
query("(apple || banana) && !cherry") -> ["d1"]
query("!banana") -> ["d3"]Hints
Hint 1
Keep an inverted index, word → set of ids, plus each id's current word set so a re-insert can remove the old postings.
Hint 2
Parse with recursive descent: or-expression → and-expressions → not-expressions → a word or a parenthesised expression. Evaluate as you parse, with sets as the values: union, intersection, and complement against all ids.