Interview Support Pro北美科技面试辅助与冲刺陪跑

SWE / MTS / SMTS（多帖） · Onsite Coding / VO Coding

Salesforce 递归展平 JSON：路径编码、数组与字符串输出

Salesforce onsite 与 VO 面经重复提 JSON/HashMap 递归展平、输出字符串；本文明确自定路径格式，给可运行训练版并讨论空容器和可逆性边界。

题目重点：Salesforce onsite 与 VO 面经重复提 JSON/HashMap 递归展平、输出字符串；本文明确自定路径格式，给可运行训练版并讨论空容器和可逆性边界。

题意与假设

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

  • 训练版输入是合法 JSON 字符串，输出也是 JSON 字符串，其内容为 flat path→leaf value 的对象；路径沿用类似 JSON Pointer 的 `/` 分隔与 `~0`、`~1` 转义，但这只是本文输出约定。
  • 字典键按 JSON 字符串处理，数组索引用十进制下标；非空容器递归展开，空对象/空数组作为该路径上的值保留。根节点路径为 `''`。
  • 只要求展平展示，不保证输出可无歧义还原原容器类型：`{"0":1}` 与 `[1]` 在没有额外类型标记时可产生相同路径映射。若面试官要求 round-trip，需扩展格式。

解题路线

  1. 先澄清 flatten 的准确契约：对象嵌套键怎样连接、数组是否展开、空容器是否保留、叶子值是 JSON 值还是全部转字符串、输出排序是否重要。由于题目缺这些细节，文章选择一个明确且可验证的训练格式。
  2. 用 DFS visit(node,path)：对象节点遍历键并把转义后的键接到路径，数组遍历索引；遇标量则存路径→值。空容器没有叶子，若直接跳过会丢失其存在，因此作为终止值写入。
  3. 最后以 sort_keys=True 和紧凑分隔符序列化映射，得到确定性 String，便于测试。路径键含 `~` 或 `/` 时先转义，不然原键 `a/b` 与两级键 `a`、`b` 都可能看似 `/a/b`。
  4. 若输入 JSON 可能极深，Python 递归/解析器有深度上限，可改显式栈；若输入很大，最终字符串和 flat map 都要占内存。若原题要求只展平对象而不展开数组，这一训练代码需按题面改。

手动走一遍

训练例输入 `{"user":{"name":"Li","tags":["ml","infra"]}}`，输出字符串解析后是 `/user/name`→`Li`、`/user/tags/0`→`ml`、`/user/tags/1`→`infra`。输入 `{"a/b":{"~":null},"empty":{}}` 时路径分别为 `/a~1b/~0` 和 `/empty`，避免键分隔歧义并保留空对象。

Python 参考实现

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

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

import json


def _pointer_token(value: str) -> str:
    return value.replace("~", "~0").replace("/", "~1")


def flatten_json_to_string(source: str) -> str:
    """Training format: a JSON object of pointer-like paths to leaf values."""
    root = json.loads(source)
    flattened = {}

    def visit(node, path: str) -> None:
        if isinstance(node, dict):
            if not node:
                flattened[path] = {}
            for key, value in node.items():
                visit(value, path + "/" + _pointer_token(key))
        elif isinstance(node, list):
            if not node:
                flattened[path] = []
            for index, value in enumerate(node):
                visit(value, path + "/" + str(index))
        else:
            flattened[path] = node

    visit(root, "")
    return json.dumps(flattened, ensure_ascii=False, sort_keys=True, separators=(",", ":"))

复杂度

若 JSON 有 N 个节点、最大深度 D，总访问节点 O(N)；每次拼接路径会复制已有前缀，最坏时间与输出路径总长度同阶，可达 O(ND·L)（L 为平均路径段长度）的量级，最终 JSON 序列化还需处理全部输出字符。flat map 和结果字符串空间随输出大小增长，递归调用栈 O(D)。不能只声称 O(N) 且忽略路径构造与输出本身。

易错点与追问

容易失分的边界

  • 未经转义直接用点或斜杠连接键，原始键含分隔符时路径碰撞。
  • 空对象/空数组没有叶子而被静默丢弃，输出缺少原结构信息。
  • 把布尔值当整数做特殊处理，或把 null 序列化成字符串 `"null"` 而非 JSON null。
  • 声称该 flat map 一定可还原原 JSON，却没有记录对象与数组的容器类型。
  • 递归处理极深不可信输入而不设深度/大小限制，触发栈溢出或内存耗尽。

继续深挖

  • 若要完全可逆，如何记录每个容器路径的类型，并区分数组数字索引与对象键 `"0"`？
  • 若输出规定 `a.b[0]` 形式，如何转义原始键中的点、方括号和反斜杠？
  • 若输入过大不能全装内存，如何流式解析、边遍历边输出，同时维持合法 JSON 对象格式？
✓已复制微信号！