Extend Stored Logger with Search and Discuss Read/Write Trade-offs

Problem: Add Search to a Store-only Logger (Read/Write Trade-offs) In the previous store-only logger, messages are appended to an internal storage. Add a search(query) feature to query stored messages. Functional Requirements Implement: log(message: str) -> None: append a message to storage. search(query: str) -> List[str]: return all stored messages that contain query as a substring, preserving insertion order. Design Discussion (trade-offs) Pick and justify data structures to balance write vs read performance: Complexity with a simple list scan. If adding indexing (inverted index / trie / n-gram / hashing buckets, etc.), how it impacts write cost and memory. How the design scales as logs grow. Constraints Up to N = 1e5 messages. Each message length up to L = 1e3. query is a plain string (not regex). Example Stored: ["error: timeout", "info: start", "error: disk"] search("error") -> ["error: timeout", "error: disk"] search("start") -> ["info: start"] Sample tests Write a, ab, b; search a => a, ab Write hello, world; search x => [] Discuss performance for 100k writes and frequent searches Results must preserve insertion order Decide behavior for empty query (return all vs error) Example Input log a log ab log b search a Output a ab