Verily OA 面试真题解析：Function Name Normalization 字符串映射

题目描述

给定映射表，例如 {'x': '%y%', 'y': '%z%_abc', 'z': 'abc'}，求 function('x') 的最终输出。规则是把变量的值当作模板，模板里出现的变量继续展开，直到全部变成字面量。

解题思路

把每个值当模板逐字符扫描：遇到映射表里存在的键就递归展开，否则原样输出。用 memo 缓存展开结果，用 visiting 集合检测循环依赖（如 x -> y -> x）。展开完成后写入 memo，避免重复计算。

def evaluate(name, mapping):
    memo = {}
    visiting = set()

    def expand(x):
        if x in memo:
            return memo[x]
        if x in visiting:
            raise ValueError("cycle detected")
        if x not in mapping:
            return x
        visiting.add(x)
        out = ""
        for ch in mapping[x]:
            out += expand(ch)
        visiting.discard(x)
        memo[x] = out
        return out

    return expand(name)

复杂度与易错点

每个变量展开一次，总复杂度 O(展开结果长度)。占位符的语法（如 %y% 里的 % 是字面量还是分隔符）要以题面为准，但「递归展开 + 循环检测」的骨架不变。漏掉循环检测会无限递归。

FAQ

为什么需要 visiting 集合，只靠 memo 不够吗？

memo 只在展开完成后才写入，递归进行中的变量还不在 memo 里；visiting 记录当前递归路径，才能识别 x -> y -> x 这类环。

参考来源

• LeetCode 205 — Isomorphic Strings
• LeetCode 890 — Find and Replace Pattern

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。