搜狗2019秋招客户端工程师的第一场笔试，我到现在还留着当时的复盘笔记。那场笔试一共4道编程题，在线OJ判题，语言自选，绝大多数人用的C++，因为搜狗客户端（输入法、浏览器）的主力语言就是C++。我当年笔试成绩还行，后来也陆续帮学弟学妹复盘过这套题，发现很多同学不是不会写代码，而是栽在边界条件和代码规范上。这篇文章我挑几道有代表性的题，把考点拆开讲透，顺便聊聊笔试现场的答题策略。不管你是准备客户端方向还是后端方向，这套题的参考价值都不低。
1. 先聊聊这套题的含金量与考察逻辑
搜狗的业务线里，客户端产品占了很大比重，输入法、浏览器、地图App都算。客户端工程师的笔试和其他岗位最大的区别在于：它不只是考你会不会写算法，而是考你写出来的代码能不能在真实工程环境里活下来。所以这套题表面上是在考字符串、链表、二叉树，实际上是在模拟客户端开发的几个核心场景。
1.1 搜狗客户端笔试在考什么
从题型分布来看，客户端笔试的重点非常明确：字符串处理、数据结构基础、C++内存与并发。为什么是这三块？因为客户端开发日常就是跟这三样东西打交道。输入法的核心业务是字符串解析、拼音匹配、候选词排序；浏览器的核心是页面渲染、缓存管理、网络请求分发；地图App的核心是海量点位的存储和检索、手势交互的响应。这些场景落到技术上，全部指向字符串和基础数据结构。
那套笔试里真正的编程题大多不涉及高深的算法，没有红黑树，没有网络流，考的都是“基础中的基础”。但越是基础的题，越能看出一个人的工程素养。同样的字符串转整数，有人写20行就AC，有人写八十行还各种边界崩溃，这就是差距。在线OJ判题会跑大量边界用例，空串、超长串、带符号的、带空格的、夹杂非法字符的，一个没考虑就前功尽弃。
1.2 这份题集适合哪些人刷
如果你是正在准备秋招的应届生，尤其是目标岗位是客户端工程师，这套题属于必刷范围。它不偏不怪，难度介于LeetCode中等题和简单题之间，但陷阱密度很高。我更推荐把它当作“C++工程能力自测题”来用：先自己限时75分钟写完，再看哪些地方考虑不周全。
如果你已经工作，也可以拿这些题来回顾基础知识。客户端这行技术迭代很快，三五年过去，很多人的C++功底已经退化到只会改业务代码了。偶尔做几道这种题，能帮你找回手感。我到现在还偶尔翻翻这几道题，主要是提醒自己，基础永远是这行的护城河。
2. 字符串与模拟题：客户端笔试的主战场
2.1 字符串转整数：边界条件比你想的多
这道题在搜狗笔试里出现过，也是各大厂笔试的常客。题目描述很简单：实现一个myAtoi函数，把字符串转换成整数。但就是这么一道题，能把一批人筛下去。
核心难点全在边界条件上：
- 字符串开头可能有空格，需要跳过
- 可能有正负号，正号可以省略
- 可能包含非数字字符，遇到就停止解析
- 整数可能溢出，需要返回INT_MAX或INT_MIN
- 可能是空串，或者全是空格
- 也可能是个合法数字后面跟着无意义的字符，比如"123abc456"，正确结果是123
我当时的一个做法是先跳过前导空格，再处理符号位，然后用long long累积结果，每加一位就检查溢出。用long long不是最优的，但在笔试场景里它是性价比最高的写法，代码清晰不容易错。
int myAtoi(const string& str) { int i = 0, n = str.size(); while (i < n && str[i] == ' ') i++; if (i >= n) return 0; int sign = 1; if (str[i] == '+' || str[i] == '-') { if (str[i] == '-') sign = -1; i++; } long long ans = 0; while (i < n && isdigit(str[i])) { ans = ans * 10 + (str[i] - '0'); if (ans * sign > INT_MAX) return INT_MAX; if (ans * sign < INT_MIN) return INT_MIN; i++; } return static_cast<int>(ans * sign); }关键点是isdigit判断要放在while条件里，这样遇到非数字字符会自然停止，不需要额外break。还有一点，ans * sign可能出现负数溢出，所以检查条件要写ans * sign < INT_MIN，而不是直接比较ans，很多同学在这里栽跟头。
注意：在笔试里，凡是处理字符串的题，先在草稿纸上列全边界条件再动手写代码。我见过太多人写完了才发现没处理空串，重新改代码浪费大量时间。
2.2 大整数乘法：不考高精度还叫笔试吗
大整数乘法是搜狗这套题里最“硬核”的一道。题目要求输入两个字符串表示的非负整数，返回乘积的字符串形式。客户端开发里做支付、做加密、做大数运算的时候都会碰到这类需求，所以考点非常实际。
思路不复杂：模拟竖式乘法。用一个长度为n + m的数组存每一位的中间结果，两层循环逐位相乘，把结果累加到对应位置，最后处理进位。
这里有个经验之谈：很多人在实现的时候会把进位逻辑写在每一步里，结果代码非常臃肿。其实可以先无脑累加，最后统一处理进位，代码会清爽很多。
string multiply(string num1, string num2) { int n = num1.size(), m = num2.size(); vector<int> res(n + m, 0); for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { int mul = (num1[i] - '0') * (num2[j] - '0'); int p1 = i + j, p2 = i + j + 1; int sum = mul + res[p2]; res[p2] = sum % 10; res[p1] += sum / 10; } } string ans; for (int v : res) { if (!(ans.empty() && v == 0)) ans.push_back(v + '0'); } return ans.empty() ? "0" : ans; }这段代码的思路是：num1[i]和num2[j]相乘的结果，个位放在i + j + 1位置，十位累加到i + j位置。最后从前往后遍历数组，跳过前导零输出。
需要注意的一个坑是：当结果为0时，整个res数组全是0，上面的遍历逻辑会把所有0都跳过，导致返回空串。所以最后必须加一个ans.empty() ? "0" : ans的判断，否则0乘以任何数都会错误。
2.3 字符串全排列：回溯与去重的细节
字符串全排列是另一道高频题。题目要求输出一个字符串的所有排列，字符可能有重复。全排列本身不难，递归交换法是最直观的解法。难的是去重，尤其是有重复字符的时候。
先看最朴素的交换法：
void dfs(vector<int>& nums, int idx, vector<vector<int>>& ans) { if (idx == nums.size()) { ans.push_back(nums); return; } for (int i = idx; i < nums.size(); i++) { swap(nums[idx], nums[i]); dfs(nums, idx + 1, ans); swap(nums[idx], nums[i]); } }如果输入是[1, 1, 2]，这个写法会输出重复结果，因为两个1的位置交换不会产生新排列。去重最稳妥的做法是在每一层递归里用一个unordered_set记录已经在当前位置出现过的元素，遇到重复就跳过：
void dfs(vector<int>& nums, int idx, vector<vector<int>>& ans) { if (idx == nums.size()) { ans.push_back(nums); return; } unordered_set<int> used; for (int i = idx; i < nums.size(); i++) { if (used.count(nums[i])) continue; used.insert(nums[i]); swap(nums[idx], nums[i]); dfs(nums, idx + 1, ans); swap(nums[idx], nums[i]); } }这个写法的好处是不需要预先排序，逻辑也直白。用set去重的时间复杂度是O(n)的查找，但n等于字符串长度，完全可接受。如果你追求极致性能，可以先排序，再判断if (i > idx && nums[i] == nums[i - 1]) continue，但那个写法在交换法的语境下容易出错，我建议笔试用set，面试聊优化的时候再提排序法。
实操心得：全排列这类回溯题，考场上最容易犯的错是忘记回溯。
swap完递归后一定要再swap回来。我见过有同学递归完没恢复数组，导致输出一堆乱序排列，排查了一刻钟才发现是少了一行回溯。
3. 数据结构与算法：链表、滑动窗口、二叉树
3.1 合并K个有序链表
合并K个有序链表在搜狗这套题里出现过，也是客户端笔试的标配。题目本身不复杂，但很考察对基础数据结构的掌握程度。最自然的思路是每次从K个头结点中选出最小的那个，但每次都扫描一遍K个节点，时间复杂度是O(KN)，数据大了肯定超时。
正确做法是用小顶堆（优先队列）维护K个头结点，每次堆顶就是最小值，弹出后把该节点的next压入堆里。时间复杂度降到O(N log K)。
struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeKLists(vector<ListNode*>& lists) { auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp); for (ListNode* head : lists) { if (head) pq.push(head); } ListNode dummy(0); ListNode* cur = &dummy; while (!pq.empty()) { ListNode* node = pq.top(); pq.pop(); cur->next = node; cur = node; if (node->next) pq.push(node->next); } return dummy.next; }有几个细节要提一下。优先队列默认是大顶堆，所以比较函数要写成a->val > b->val，让值小的优先级高。另外，dummy节点的用法是链表题的常规操作，可以省去对头结点做单独判空的麻烦。最后一个容易忽略的坑是：优先队列里存的是原始指针，如果链表节点在堆上分配，合并完成后需要自行管理内存释放，但在笔试OJ里一般不要求。
这道题还有一个分治的写法，两两合并，时间复杂度同样是O(N log K)。面试的时候可以提一下，说明你理解多种解法，笔试就直接用堆，代码短，不容易错。
3.2 最长无重复子串：滑动窗口的经典场景
最长无重复子串字符串处理在客户端开发里很常用，比如输入法里的输入串去重、文本编辑器里的重复检测。题目给一个字符串，找出其中不含有重复字符的最长子串的长度。
解法是滑动窗口加哈希表。右指针不断向右扩展，每次遇到一个已经出现过的字符，就把左指针跳到上次出现位置的下一个。这一步跳转是很多人的失分点，容易写成left++而不是left = max(left, last[c] + 1)。
int lengthOfLongestSubstring(string s) { int left = 0, ans = 0; unordered_map<char, int> last; for (int right = 0; right < s.size(); right++) { char c = s[right]; if (last.count(c)) { left = max(left, last[c] + 1); } last[c] = right; ans = max(ans, right - left + 1); } return ans; }为什么left要用max？因为左指针只能往前走，不能回退。假设字符串是abba，当右指针走到第二个a时，前一个a在位置0，按公式算出来left = 1，但如果此时left已经在2了（因为之前的b重复已经把left推到了2），再把它拉回1就错了。这个细节，好多刷题量不够的同学会在这里卡住。
滑动窗口的时间复杂度是O(n)，只遍历一遍字符串。这是笔试中的标准答案，也是面试官期待的复杂度。
3.3 判断平衡二叉树
平衡二叉树这题看起来基础，实际写对的人不多。题目定义：每个节点的左右子树高度差不超过1。最直白的写法是递归计算每个节点的左右子树高度，再分别递归判断左右子树是否平衡。但这个写法是O(n log n)，因为计算高度的过程会重复遍历每个节点。
更优的解法是在计算高度的同时顺便判断平衡性，用一个特殊返回值-1表示“不平衡”。这样一次后序遍历就能完成判断，时间复杂度O(n)。
int height(TreeNode* root) { if (!root) return 0; int l = height(root->left); if (l == -1) return -1; int r = height(root->right); if (r == -1) return -1; if (abs(l - r) > 1) return -1; return max(l, r) + 1; } bool isBalanced(TreeNode* root) { return height(root) != -1; }这个写法妙在提前剪枝：一旦发现左子树不平衡，直接返回-1，不再递归右子树。代码量不大，但概念上把“递归返回什么”想得很清楚。很多同学在写这题时会用两个函数（一个求高度，一个判断平衡），也没有错，但复杂度差了一截，面试追问的时候会显得思路不够深。
二叉树相关的题，关键是想清楚递归函数的定义：这个函数返回什么？在什么条件下返回？调用方怎么处理返回值？想清楚这三点，代码基本不会乱。
4. 客户端特色的延伸考点：C++内存与并发
笔试结束后，如果顺利进入面试，面试官会顺着笔试题继续追问。客户端方向的追问重点非常固定：多线程、内存管理、C++基础。这一节我讲三道面试手写题，它们和笔试是配套的，提前准备好，面试能省很多力气。
4.1 手写生产者消费者模型
生产者消费者是客户端并发面试的必考题。客户端里线程池的任务队列、网络回调的数据缓冲、UI线程和后台线程的消息传递，本质都是生产者消费者模型。
手写的要求通常是：一个固定大小的缓冲区，多个生产者往里面放数据，多个消费者从里面取数据，要求线程安全。标准答案是条件变量加互斥锁：
#include <condition_variable> #include <mutex> #include <queue> std::queue<int> buffer; const int CAPACITY = 16; std::mutex mtx; std::condition_variable not_full, not_empty; void producer() { for (int i = 0; i < 100; ++i) { std::unique_lock<std::mutex> lock(mtx); not_full.wait(lock, [] { return buffer.size() < CAPACITY; }); buffer.push(i); not_empty.notify_one(); } } void consumer() { for (int i = 0; i < 100; ++i) { std::unique_lock<std::mutex> lock(mtx); not_empty.wait(lock, [] { return !buffer.empty(); }); int value = buffer.front(); buffer.pop(); not_full.notify_one(); } }这里有几个考点面试官一定会追问。第一，为什么wait要传谓词？因为条件变量存在伪唤醒（spurious wakeup），当线程被唤醒时不代表条件真的满足，必须用while或谓词再检查一遍。wait带谓词的形式其实就是while (!pred()) wait(lock)的语法糖。
第二，为什么用的是unique_lock而不是lock_guard？因为condition_variable::wait需要临时释放锁并重新获取锁，lock_guard不支持这个操作，unique_lock才行。
第三，缓冲区满了生产者等待，空了消费者等待，这是两个条件变量，用同一个也可以，但两个条件变量的好处是避免无意义的唤醒，性能更好。这些细节答出来比代码本身加分多了。
4.2 线程安全的单例模式
单例模式在客户端开发里到处都是：配置文件管理器、日志模块、全局缓存。手写一个线程安全的单例，看起来简单，坑却很多。
最经典的陷阱是双重检查锁定（DCLP）。早年C++没有内存模型保证，双重检查在指令重排的影响下会出bug。C++11之后，最简单、最正确的写法是magic static：
class Singleton { public: static Singleton& instance() { static Singleton inst; return inst; } private: Singleton() = default; Singleton(const Singleton&) = delete; Singleton& operator=(const Singleton&) = delete; };C++11标准保证了局部静态变量的初始化是线程安全的，编译器会生成对应的同步代码。这个写法既简洁又高效，是面试时的最优答案。
如果面试官接着问“如果不能用magic static，你怎么实现”，可以回答：加锁是必须的，但为了性能，可以先用一个原子变量判断实例是否已经创建，避免每次调用都加锁。这个方案其实已经接近DCLP的复杂版本了，能讲到这个深度，面试官基本满意。
注意：千万不要在构造函数里做太重的初始化工作（读文件、连数据库），单例首次创建的耗时可能拖慢启动速度。客户端的启动时间是核心指标，单例里放重逻辑是线上事故的高发区。
4.3 智能指针与内存泄漏
搜狗客户端的笔试和面试都很关注内存管理，因为客户端产品要跑在各种配置的机器上，内存泄漏是线上崩溃的主要原因之一。C++里内存管理绕不开智能指针，面试官会问：shared_ptr会不会有内存泄漏？什么时候会？
答案在循环引用。两个对象互相持有对方的shared_ptr，会形成引用环，引用计数永远不会归零，对象就泄漏了。解决办法是把其中一边改成weak_ptr。
class B; class A { public: std::shared_ptr<B> b_ptr; }; class B { public: std::weak_ptr<A> a_ptr; };这个场景在客户端里很常见：父子窗口界面互相持有对方，如果一个持有shared_ptr一个持有weak_ptr，就不会泄漏。面试时说一句“我们项目里用weak_ptr打破循环引用”，比单纯背概念有说服力得多。
还有一道经典题：shared_ptr是否是线程安全的？答案是：控制块的引用计数是线程安全的，但指向的对象不是。也就是说，多个线程可以同时拷贝同一个shared_ptr而不出错，但在一个线程里读对象、另一个线程写对象时，仍然需要外部锁。
5. 笔试现场的答题策略与代码规范
这部分是我自己踩过坑后的总结，比任何一道具体的题都重要。笔试考的不仅是你会不会，还有你在限时压力下的表现。同样是AC，代码规范程度不同，面试官后续问问题的态度也会不同。
5.1 拿到题目先干什么
先花两分钟看数据范围。数据范围决定复杂度，复杂度决定算法选型。如果n是10的5次方，O(n^2)的算法基本不可能过；n是100，O(n^2)完全可以接受。很多人一上来就写最直观的解法，写到一半发现会超时，再改成优化版本，时间白白浪费。
然后是确认输入输出的格式。在线OJ对输出格式非常严格，多一个空格、少一个换行都判错。我见过有同学代码逻辑全对，就因为输出多了一个空格，AC不了，最后十分钟在排查这个，心态直接崩了。
拿到题目先草稿纸上列好输入输出的测试用例也很关键，尤其是边界用例。你可以先用题目给的示例验证思路，再自己想两个边界用例，比如空数组、只有一个元素、最大整数。这些用例在写完之后用来验证代码，能拦截掉大多数隐藏bug。
5.2 代码风格和边界条件的加分项
很多同学觉得笔试只要AC就行，代码丑点无所谓。其实笔试结果通过后，面试官是能看到你的代码的，很多人面试被问“你解释一下你当时是怎么想的”，就是在翻你笔试题。
代码风格上，我的建议是：变量名要有意义，不要用a、b、c这种；函数拆得短一点，一个函数最好只干一件事；边界条件写在前面，不要散落在代码中间；关键步骤写一行注释，解释“这一步在干什么”。这些不会影响AC，但会让面试官觉得这个人有工程素养。
还有一点很重要的经验：写完代码不要急着提交，手动用几个用例走一遍。我自己的习惯是模拟执行一个正常用例，一个边界用例，一个错误输入用例。这个过程能发现很多低级问题，比如数组越界、忘记返回、溢出。在OJ上反复提交被罚时，不如在本地多花一分钟自测。
5.3 时间分配与做题顺序
编程题的时间分配有讲究。我的策略是：先把所有题都看一遍，在心里排个难度顺序；先做最简单的题，确保拿到保底分；再做中等题；最难的题留到最后。千万不要在第一道难题上死磕，否则后面几道本来能拿分的题都没时间做。
搜狗这场笔试是4道题，我当年的做题节奏是：先花3到5分钟扫一遍所有题目，选出最简单的一道，10到15分钟写完并自测。然后做中等难度，最后剩下30分钟左右的完整时间给最难的题。如果某一题卡了超过20分钟，果断放弃，先去做其他题，最后有时间再回来补。
这里的核心思路是：笔试的目标是拿分，不是证明自己多强。一道难题完全做出来可能就20分，但一个简单题AC了也是20分，性价比完全不同。
6. 常见问题与排查技巧实录
这部分我整理一下当年笔试和小伙伴们讨论时常见的问题。每一条都是真实的坑，照着排查能省不少时间。
6.1 编译不过的坑
- 忘记
#include。C++的字符串用std::string忘了#include <string>，用优先队列忘了#include <queue>，这在OJ上会报编译错误。很多同学在本地IDE里开发，IDE自动带了头文件，编译没问题，一上OJ就各种报错。解决办法是提交前检查一下自己用到的标准库组件，确保头文件齐全。 - 返回值类型不一致。函数声明返回
int，函数体里返回了long long或者string，编译报错。笔试时间紧张时容易犯这种错。 nullptr和NULL混用。在C++11里没问题，但如果OJ的编译标准比较旧，可能不支持nullptr。用NULL或0更保险。不过现在大部分OJ都支持C++14以上了，这个坑在变少。
6.2 超时的原因
超时是笔试里最让人崩溃的问题。代码逻辑没问题，但就是跑不完。常见原因有三个：
第一，输入输出用了cin/cout而没有关同步。C++里cin/cout默认和stdio同步，这个同步开销非常大。处理大量数据时，在main开头加一行ios::sync_with_stdio(false)，能把IO时间缩短很多倍。这个习惯要养成，笔试必用。
第二，函数传参用了传值而不是传引用。大字符串、大vector，每次递归或调用都拷贝一份，时间复杂度瞬间就爆炸了。除非明确需要副本，否则统统用const&。
第三，循环里重复计算了不变量。比如求长度的循环里每次调用size()没问题，编译器会优化；但循环里每次都重做一个unordered_map，或者每次都排序，这种就是无谓的浪费。写完代码自己扫一遍循环体，看有没有可以提到循环外的操作。
6.3 笔试后的面试追问
笔试过了并不是结束，面试官会拿着你的代码来问。他可能不关心你AC没有，而是关心你的代码能不能扛住变化。常见追问有：
- “你这个算法的时间复杂度是多少？能不能优化？”如果你的解法是O(n^2)而最优解是O(n log n)，你要能清晰说出自己解法的瓶颈在哪。
- “如果输入规模变成10的6次方，你的代码会出什么问题？”这个问题专门考察对数据范围和内存的敏感度。
- “如果改成多线程环境，你的代码有哪些地方不是线程安全的？”这个追问在客户端岗位出现的概率极高，因为客户端就是多线程环境。
我的建议是：笔试完不要急着对答案或者关电脑，花10分钟回忆一遍每道题的思路，想想如果被追问能怎么回答。这套题的价值不止在AC那一刻，能让你提前准备面试才是它最大的意义。尤其要注意把自己的代码在本地再测一遍，因为面试官让你解释的时候，你总不希望看到自己当时提交的代码含有低级bug。
我当年就是因为笔试时写的大整数乘法，在最后时刻想起了一个边界用例没覆盖，多花了一分钟改掉，结果面试时面试官正好问到了“如果相乘的两个数极大怎么办”，我直接把自己的溢出处理思路讲了一遍，面试氛围立刻就不一样了。这种细节，往往就是能不能拿offer的分水岭。
