Rippling Logger OOD：文本操作、关键词查询与稳定去重

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版把三种文本变换定义为纯函数，`add(message)` 只存原字符串；`search(keywords,unique)` 要求所有关键词都作为大小写敏感子串出现，去重按完整 message 文本、保留首次出现顺序。
• `capitalize()` 按 Python 首字符大写其余小写解释；题目可能要全大写。keywords 为非空列表、每词非空，原题错误协议未给。

解题路线

1. 把文本变换和存储/查询分开，避免调用 truncate 后意外改变历史日志。remove_substring 用字面子串替换，truncate 限前 n 个字符，capitalize 明确语言库语义；组合顺序若要求可配置，定义 pipeline 顺序。
2. 写优化版本只 append 到列表；搜索逐条判断全部关键词，匹配后用 seen 集合做稳定去重。若不要去重，跳过 seen 维护即可，避免每条日志都参与全局 set。
3. 读多写少且关键词是分词时可建 token→有序日志 ID 倒排索引：多关键词取交集、按 ID 顺序回表；子串匹配需 n-gram 或原文验证，普通词索引不能直接保证语义相同。更新、删除、文本变换需同步索引或版本化重建。
4. 若只需一条日志内去掉重复单词，与跨日志相同消息去重是不同需求；必须与面试官确认 duplicate 的单位。

手动走一遍

写入 `error foo`、`error foo`、`error bar`；搜 `['error','foo']` 默认只返回第一条 `error foo`，关闭去重时返回两条。`truncate('Hello',3)='Hel'`；remove('banana','na')='ba'，因为采用非重叠字面替换。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Logger:
    """Training contract: immutable stored lines; case-sensitive AND keyword search."""

    def __init__(self) -> None:
        self.messages: list[str] = []

    @staticmethod
    def remove_substring(message: str, needle: str) -> str:
        if not needle:
            raise ValueError("empty needle")
        return message.replace(needle, "")

    @staticmethod
    def truncate(message: str, n: int) -> str:
        if n < 0:
            raise ValueError("negative length")
        return message[:n]

    @staticmethod
    def capitalize(message: str) -> str:
        return message.capitalize()

    def add(self, message: str) -> None:
        self.messages.append(message)

    def search(self, keywords: list[str], unique: bool = True) -> list[str]:
        if not keywords or any(not keyword for keyword in keywords):
            raise ValueError("nonempty keywords required")
        result = []
        seen = set()
        for message in self.messages:
            if all(keyword in message for keyword in keywords):
                if unique and message in seen:
                    continue
                result.append(message)
                seen.add(message)
        return result

复杂度

设 N 条日志、平均长度 L、K 个关键词，扫描搜索上界 O(N×K×L)，新增只追加 O(1) 摊还；稳定去重空间 O(结果中不同字符串数)。倒排索引写入随 token 数增长，交集复杂度取决于 posting 长度。

易错点与追问

容易失分的边界

• 擅自决定关键词是 OR、AND、前缀或正则却不标口径。
• 返回去重后的集合，丢失原始顺序。
• 用普通分词倒排索引直接回答任意子串查询。
• 优化读取后忘了新增日志索引更新成本。
• 把纯文本变换不小心应用到已存历史日志。

继续深挖

• 关键词 OR 查询如何与 AND 区分？
• 若重复指同一请求 ID，而不是同文本，key 怎么改？
• 读多写少时如何维护排序的 posting list？
• 如何避免同一条日志被多关键词命中后重复输出？