搜狗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_castint(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(); vectorint 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(vectorint nums, int idx, vectorvectorint 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(vectorint nums, int idx, vectorvectorint ans) { if (idx nums.size()) { ans.push_back(nums); return; } unordered_setint 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(vectorListNode* lists) { auto cmp [](ListNode* a, ListNode* b) { return a-val b-val; }; priority_queueListNode*, vectorListNode*, 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_mapchar, 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::queueint 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_lockstd::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_lockstd::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。C11之后最简单、最正确的写法是magic staticclass Singleton { public: static Singleton instance() { static Singleton inst; return inst; } private: Singleton() default; Singleton(const Singleton) delete; Singleton operator(const Singleton) delete; };C11标准保证了局部静态变量的初始化是线程安全的编译器会生成对应的同步代码。这个写法既简洁又高效是面试时的最优答案。如果面试官接着问“如果不能用magic static你怎么实现”可以回答加锁是必须的但为了性能可以先用一个原子变量判断实例是否已经创建避免每次调用都加锁。这个方案其实已经接近DCLP的复杂版本了能讲到这个深度面试官基本满意。注意千万不要在构造函数里做太重的初始化工作读文件、连数据库单例首次创建的耗时可能拖慢启动速度。客户端的启动时间是核心指标单例里放重逻辑是线上事故的高发区。4.3 智能指针与内存泄漏搜狗客户端的笔试和面试都很关注内存管理因为客户端产品要跑在各种配置的机器上内存泄漏是线上崩溃的主要原因之一。C里内存管理绕不开智能指针面试官会问shared_ptr会不会有内存泄漏什么时候会答案在循环引用。两个对象互相持有对方的shared_ptr会形成引用环引用计数永远不会归零对象就泄漏了。解决办法是把其中一边改成weak_ptr。class B; class A { public: std::shared_ptrB b_ptr; }; class B { public: std::weak_ptrA a_ptr; };这个场景在客户端里很常见父子窗口界面互相持有对方如果一个持有shared_ptr一个持有weak_ptr就不会泄漏。面试时说一句“我们项目里用weak_ptr打破循环引用”比单纯背概念有说服力得多。还有一道经典题shared_ptr是否是线程安全的答案是控制块的引用计数是线程安全的但指向的对象不是。也就是说多个线程可以同时拷贝同一个shared_ptr而不出错但在一个线程里读对象、另一个线程写对象时仍然需要外部锁。5. 笔试现场的答题策略与代码规范这部分是我自己踩过坑后的总结比任何一道具体的题都重要。笔试考的不仅是你会不会还有你在限时压力下的表现。同样是AC代码规范程度不同面试官后续问问题的态度也会不同。5.1 拿到题目先干什么先花两分钟看数据范围。数据范围决定复杂度复杂度决定算法选型。如果n是10的5次方O(n^2)的算法基本不可能过n是100O(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混用。在C11里没问题但如果OJ的编译标准比较旧可能不支持nullptr。用NULL或0更保险。不过现在大部分OJ都支持C14以上了这个坑在变少。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的分水岭。