Query and Log Stream

Requirements

• Process a stream of strings prefixed by Q: or L:.
• Register each query with a unique ID and output its acknowledgement.
• For a log, output all registered query IDs whose words are all present, regardless of word order.
• Matching is case-insensitive in the detailed example and operates on whole words.
• Follow-ups include faster lookup, caching, and query addition/deletion.

Examples

Q: database
Q: Stacktrace
Q: loading failed
L: Database service started
Q: snapshot loading
Q: fail
L: Started processing events
L: Loading main DB snapshot
L: Loading snapshot failed no stacktrace available

ACK: database; ID=1
ACK: Stacktrace; ID=2
ACK: loading failed; ID=3
M: Database service started; Q=1
ACK: snapshot loading; ID=4
ACK: fail; ID=5
M: Loading main DB snapshot; Q=4
M: Loading snapshot failed no stacktrace available; Q=2,3,4

Notes

The example produces no match line for a log with no matches. fail does not match the word failed. Repeated-word semantics, duplicate registrations, and deletion interface details are unspecified.

For a baseline, normalize case, tokenize on the agreed word boundaries, and compare each stored query with the log. Under set semantics, every distinct query word must occur in the log; repeated-word semantics still require clarification. Preserve the original text for acknowledgements and output.

For faster matching, store an inverted index from each word to the IDs of queries containing it, plus the distinct-word count for each query. Visit each distinct log word once and count hits for its query IDs; emit an ID when its hit count equals its query's distinct-word count. An empty query needs a separate agreed rule. Keep query-to-word records so deletion removes its postings; cached matches must be invalidated when registrations change.

With expected constant-time hash operations, a log costs O(L + P + M) before ordering, where L is its text length, P is the total postings visited, and M is the number of emitted matches. If ascending IDs are required, sorting adds O(M log M). The index stores O(W) word-to-query associations, where W is the total distinct-word count across queries, in addition to stored text.

Preparation

• In 20 minutes, implement the baseline and reproduce every acknowledgement and match line in the existing example, including omission of the no-match log.
• In 20 minutes, implement the inverted index and compare it with the baseline on mixed-case and repeated-word inputs under an explicitly chosen set policy.
• Trace query deletion and re-registration against a cached log result; explain which index and cache entries must change.