Sequential Phrase Search Across Documents
Confluent● MediumFULLTIMEONSITE INTERVIEWProblem statement
Given an array of text documents and a query phrase, return the zero-based indices of every matching document, once each in increasing order. Match complete lowercase words exactly; a word prefix is not a match.
Query forms
- A plain query such as
alpha betais an ordered phrase: its words must appear in that order in the document, but they do not have to be adjacent. Each query occurrence consumes a later document occurrence, soalpha alphaneeds two occurrences. - A query such as
alpha AND betarequires every listed word to occur somewhere in the document, in any order. Repeated operands do not require extra occurrences. - A query such as
alpha OR betarequires at least one listed word to occur.
A one-word plain query is an exact-word lookup. Every Boolean query uses exactly one operator kind, with at least two lowercase-word operands and a single space around uppercase AND or OR. Mixed operators, parentheses, negation and malformed queries are outside this exercise. Plain queries and documents use one space between lowercase English words and have no leading or trailing spaces.
For this exercise, assume ordered nonadjacent phrase matching and the finite uniform-operator grammar above. An earlier report identifies the same-word-sequence search; the current report directly permits gaps and adds Boolean document retrieval.
Function
findDocumentsWithPhrase(documents: String[], phrase: String) → int[]Examples
Example 1
documents = ["distributed systems need careful testing","careful distributed systems testing","distributed reliable systems"]phrase = "distributed systems"return = [0,1,2]Plain phrases preserve query word order while allowing gaps; every returned index identifies a separate document.
Example 2
documents = ["alpha beta gamma","beta alpha gamma","alpha gamma beta"]phrase = "alpha beta"return = [0,2]Plain phrases preserve query word order while allowing gaps; every returned index identifies a separate document.
Example 3
documents = ["alpha beta gamma","beta alpha gamma","alpha gamma beta"]phrase = "gamma AND beta"return = [0,1,2]Boolean operands match complete words anywhere in a document; operator semantics do not require query order.
Example 4
documents = ["alpha","beta","delta alpha","alphabet"]phrase = "alpha OR delta"return = [0,2]Boolean operands match complete words anywhere in a document; operator semantics do not require query order.
Constraints
1 <= documents.length <= 1000.1 <= documents[i].length <= 1000.1 <= phrase.length <= 200.- Documents contain lowercase English words separated by exactly one space.
- The query is one of the valid plain, uniform-AND or uniform-OR forms described above.