拼多多客户端开发一二三面：SDK 设计、坐标走到原点与二叉树高度

《面试题目》

1. （一面）聊实习。
2. （一面）场景题：如何设计一个客户端 SDK，如何和主端进行通信？
3. （一面）算法题：(x, y) 是坐标，走到 (0,0) 有五种移动方式：(x-1,y)、(x,y-1)、(x-y,y)、(x,y-x)、(x/2,y/2)，求方案数。
4. （一面）C++/OC 八股：协程、多态、智能指针。
5. （二面）实习；对 Agent 的看法（为什么不做成文档 MCP）；C++ 与操作系统八股；算法：不用递归求二叉树高度。
6. （三面）实习；C++ 与操作系统八股（操作系统如何把 C++ 代码变成可执行程序，进程有哪些内存分区）；能否接受拼多多的工作时间；算法：不用递归求二叉树高度。

《参考解析》

客户端 SDK 怎么设计：按五层讲。接口层：对业务方暴露稳定的 API，参数用值对象而不是散字段，版本语义要明确（新增字段向后兼容、删除字段走大版本）。协议层：主端与 SDK 之间用「命令 + 参数 + 回调 id」的消息协议，而不是直接互相持有引用——这样 SDK 可以独立演进、支持异步与超时。能力层：把宿主能力（UI 容器、网络、存储、日志、权限）抽象成接口由主端注入，SDK 不直接依赖宿主实现，方便测试与复用。生命周期：初始化、attach/detach、销毁要有明确语义，避免内存泄漏。安全与稳定性：调用要做参数校验、异常隔离（SDK 内部异常不能拖垮主端）、线程模型约定清楚。

坐标走到原点的方案数：先把五种移动分类——前两种是单步递减，后两种是「用较大的坐标减较小的」，第五种是同时折半。关键观察：折半只能在两者都是偶数时才有意义（否则坐标会变成小数），而减法类操作本质上是在做辗转相减，它的效果类似求 gcd 的过程——所以状态空间远小于直觉上的 O(n²)。实用做法是记忆化搜索：状态 (x, y) 用哈希表存，每个状态转出最多 5 个后继，遇到 x<0 or y<0 直接返回 0，(0,0) 返回 1。由于每次操作要么让某个坐标严格减小、要么让两者同时减半，状态总数是对数级别的，实测远优于 n²。面试里被问「有没有更优解」时可以指出去重与对称性（(x,y) 与 (y,x) 方案数相同），以及折半只在偶数时启用。

不用递归求二叉树高度：两种写法。BFS：按层遍历，每处理完一层层数加一，直观且不会栈溢出。后序迭代：用显式栈模拟递归，记录每个节点的访问状态（第一次入栈是「待访问子节点」，第二次出栈时用子节点的高度算出自己的高度），用一个 map 存节点高度。前者的空间是 O(宽度)，后者是 O(高度)。

操作系统如何把 C++ 代码变成可执行程序：预处理（展开宏与头文件）→ 编译（生成汇编）→ 汇编（生成目标文件，含符号表与重定位信息）→ 链接（符号解析 + 重定位，静态链接把库代码复制进来，动态链接留下对 .so 的引用，运行时由动态加载器 ld.so 解析）。可执行文件按 ELF 组织：代码段 .text、只读数据 .rodata、已初始化数据 .data、未初始化 .bss。进程加载后的内存分区：代码段、数据段（.data/.bss）、堆（向上生长）、内存映射区（共享库、mmap）、栈（向下生长），再加内核空间。

C++ 与 OS 八股的重点：多态（虚函数表、虚析构为什么必要、构造/析构期间虚函数不生效）、智能指针（unique_ptr 独占、shared_ptr 引用计数与控制块、weak_ptr 破环、make_shared 一次分配）、协程（C++20 的 coroutine 是编译器改写的状态机，co_await/co_yield/co_return，需要 promise_type）；OS 侧进程与线程的区别、上下文切换、内存管理、IO 模型（阻塞/非阻塞/多路复用）、零拷贝。