前几天有个学弟来问我说想看看“触宝科技2017秋季校招研发笔试题(第四批)”到底是什么难度值不值得刷。我翻了一下当年的记录这套题放在今天看依然有很强的参考价值。它不算难但非常有代表性属于那种“看起来都会写起来容易翻车”的卷子跟现在不少公司动辄出hard题、竞赛题的路子不太一样。它考察的东西很聚焦语言基础、数据结构、经典算法题、再加一道跟业务强相关的开放题。对准备校招的同学来说把这套题吃透比盲目刷一百道LeetCode更能帮你摸清“一家做移动产品的公司到底想要什么样的研发”。这篇文章我就以复盘的形式把这套笔试题涉及的考点、编程题的完整解法、开放题的答题思路以及笔试现场容易踩的坑都过一遍。不管你是正在准备秋招的应届生还是想了解移动互联网公司笔试风格的在职开发者都能从中找到有用的东西。1. 这套笔试题的底细出题思路与考察逻辑1.1 题型结构与分数分布先说整体结构。触宝这套研发笔试题是典型的“选择题 编程题 附加题”组合线上笔试给一个比较紧张的时间窗口。选择题大概占30到40分覆盖编程语言、数据结构、操作系统、计算机网络这些计算机基础核心课。编程题占大头通常在50分以上2到3道题要求在OJ在线评测系统上写完整代码并提交运行。最后还有一道附加的开放设计题不算硬性得分但答得好会明显加分。为什么要这样设计笔试的筛选逻辑其实很清晰选择题筛掉基础不扎实的人编程题筛掉“只会背概念但写不出代码”的人附加题则用来识别那些对业务有感觉、有产品思维的候选人。三道关卡组合起来基本能判断一个应届生的下限和上限。这跟很多大厂的笔试套路是一致的只是触宝的选题风格更偏“应用基础”没有太多偏题怪题。1.2 “第四批”背后的信息“第四批”这三个字其实说明了一些事情。校招通常分多批次越到后面的批次题目越趋于稳定难度也会相对平衡因为前面已经筛过几轮了。触宝2017年秋季校招到了第四批出题人已经比较成熟题目大多是经过验证的、区分度好的经典题型不会出现那种“全场只有一两个人做出来”的情况。从题目偏好来看触宝做输入法和通讯工具出身业务对字符串处理、搜索排序、文本匹配这些能力比较看重所以笔试题里经常会围绕字符串、二叉树、动态规划做文章。这给后来者的启示是笔试前不要只刷热门题目一定要去了解目标公司的业务方向它用什么技术、做什么产品笔试多少会往这个方向倾斜。这不是什么潜规则而是技术面试的通用逻辑——公司希望招进来的人能对业务产生价值。2. 基础题考点拆解语言与数据结构是硬门槛2.1 编程语言选择题Java还是C触宝这套题的选择题部分编程语言主要考Java和C跟大部分移动端技术栈的公司一致。Java方向常考的几类HashMap的底层结构、扩容机制、为什么默认负载因子是0.75String为什么不可变值传递和引用传递的区别异常处理体系。C方向则会考虚函数、析构函数、内存泄漏、指针和引用的区别。拿HashMap举例这个考点几乎是必出的而且喜欢连环问。底层结构是数组加链表JDK 8之后链表长度超过8会转红黑树。默认容量是16负载因子0.75扩容时直接翻倍。为什么负载因子是0.75而不是0.5或1.0这是一个空间和时间的折中太小了导致频繁扩容浪费空间太大了哈希冲突变多查询效率下降。0.75是经过统计学测试后得出的一个平衡点。这些细节如果只背结论不追原理选择题一出变体就容易懵。我建议准备这类题时用“讲给同桌听”的方式来验证自己是否真懂。能不看资料把HashMap从put到get整个流程讲清楚包括哈希扰动函数的作用、树化的条件、扩容时链表如何拆分这题才算过关。停留在“数组加链表”这种一句话答案在笔试里是不太够用的。2.2 数据结构与算法选择题复杂度和稳定性选择题里数据结构与算法的比例也很高常见的出题角度包括各种排序算法的稳定性、时间复杂度和空间复杂度哈希冲突的解决方法二叉树遍历方式堆和优先队列的使用场景。排序算法对比是一个高频考点做题时可以直接记一张表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定这张表背下来不难难的是理解背后的原因。比如快速排序为什么最坏是O(n^2)因为每次选的基准值都恰好是最大或最小元素导致划分极度不平衡为什么快排不稳定因为partition过程中元素会跨区间交换相同元素的相对顺序无法保证。选择题如果只考“哪个排序不稳定”背表能解决如果考“为什么”就需要对排序过程有真正的理解。2.3 操作系统与网络基础分也不能丢操作系统和计算机网络是选择题的另一半江山。操作系统常考进程和线程的区别、死锁的四个必要条件、虚拟内存和分页、进程间通信方式。网络常考TCP和UDP的区别、三次握手和四次挥手、TIME_WAIT的作用、HTTP状态码的含义。这些知识点看似和研发岗位的实际工作关系不大但它筛选的是“计算机基础是否成体系”。举个例子TCP为什么需要TIME_WAIT因为要确保最后一个ACK能到达对端如果丢了对端会重发FIN如果没有TIME_WAIT本端已经关闭就收不到重发的FIN会导致对端一直处于LAST_ACK状态。这种问题在选择题里出现时四个选项长得都差不多只有真正理解TCP状态迁移的人才能选对。我的建议是这部分不要靠考前突击。因为内容太多太杂临时背只能记住“关键词匹配”遇到换一种说法的题目照样错。在准备校招的基础笔试阶段操作系统和网络至少提前一个月开始用“理解 做题”的方式推进每天花一到两小时比最后几天集中背效果好得多。3. 编程题核心解析两道让你涨经验的题编程题是这套笔试的重头戏。以下题目是根据当年考生回忆整理还原的版本大意与真题一致具体描述可能有出入但思路和解法是通用的。3.1 字符串压缩与解压最典型的“输入法式”字符串题第一道编程题是字符串压缩。题目大意是给定一个只包含小写字母的字符串将连续出现的相同字符压缩成“字符出现次数”的形式。例如aaabbbbcc压缩后变成a3b4c2。如果压缩后的字符串长度不小于原字符串则返回原字符串。另外还要实现一个解压函数把a3b4c2还原为aaabbbbcc。这道题思路非常简单就是一个单次遍历。用一个指针扫字符串遇到相同字符就计数遇到不同字符就把前一个字符和计数拼到结果里。但它的坑也不少最容易翻车的是边界条件字符串为空、字符串长度为1、压缩后长度反而更长比如abc会变成a1b1c1长度是6比原串长按题目要求必须返回原串。压缩的核心代码用Python写大概是这样def compress(s: str) - str: if not s: return s res [] cnt 1 for i in range(1, len(s)): if s[i] s[i - 1]: cnt 1 else: res.append(s[i - 1] str(cnt)) cnt 1 res.append(s[-1] str(cnt)) compressed .join(res) return compressed if len(compressed) len(s) else s解压函数则要处理“数字可能不止一位”的情况比如a12b3。不能只读一位数字要用循环把连续的数字字符完整读出来再转成整数。很多第一次写的同学在这里栽跟头以为出现次数只会是个位数测试用例一给a12b3就挂了。为什么这套题会放在第一道因为它考察的是最基本的字符串处理能力和代码严谨度。输入法业务里到处是这种“把用户输入做规范化处理”的逻辑出题人希望看到的是你写出来的代码能处理各种边界情况而不是只能跑通样例。3.2 二叉树的之字形层序遍历考察BFS灵活变通第二道编程题是二叉树的之字形层序遍历。题目大意给定一棵二叉树从根节点开始逐层输出节点值第一层从左到右第二层从右到左第三层再从左到右以此类推。输出形式是一个二维列表每一层单独占一个子列表。解法是用BFS广度优先搜索。标准层序遍历用队列就能搞定之字形只需要加一个层数判断如果是偶数层从0开始计数就把当前层的结果反转一下或者干脆用双端队列奇数层从尾部添加偶数层从头部添加省去反转的开销。Java实现大概是这样的public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) return result; QueueTreeNode queue new LinkedList(); queue.offer(root); int level 0; while (!queue.isEmpty()) { int size queue.size(); LinkedListInteger cur new LinkedList(); for (int i 0; i size; i) { TreeNode node queue.poll(); if (level % 2 0) { cur.addLast(node.val); } else { cur.addFirst(node.val); } if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } result.add(cur); level; } return result; }这题的易错点有两个。第一个是空树直接返回空列表而不是null。第二个是层数奇偶判断的方向有的题目从1开始计层奇数层从左到右、偶数层从右到左有的从0开始计层代码里就要相应调整。我见过不少同学在这个细节上写反导致只对一半的测试用例。这道题为什么值得好好做它考的BFS是高频考点树的层序遍历进阶版基本每年都出现在各大公司的笔试题里。除了之字形还有按之字形填充next指针、每层最大值、每层平均值等变体本质都是一样的。把这道题吃透BFS层序遍历这一族题就都稳了。3.3 最长递增子序列DP问题里的常客第三道编程题是经典的“最长递增子序列”LIS。题目大意给定一个无序整数数组求其中最长递增子序列的长度并输出其中一个最长递增子序列。注意子序列不要求连续只要保持相对顺序即可。这个问题有两种常用解法。第一种是动态规划状态定义很直观dp[i]表示以nums[i]结尾的最长递增子序列长度。状态转移是对于每个i遍历所有j i如果nums[j] nums[i]就用dp[j] 1尝试更新dp[i]。最终答案是max(dp)。时间复杂度O(n^2)在笔试中通常够用了因为数据范围一般不会太大。如果要求输出一个具体的最长递增子序列需要额外用prev数组记录每个位置的前驱节点最后从最优解的位置向前回溯。Python代码如下def lengthOfLIS(nums): if not nums: return 0, [] n len(nums) dp [1] * n prev [-1] * n max_len 1 end 0 for i in range(n): for j in range(i): if nums[j] nums[i] and dp[j] 1 dp[i]: dp[i] dp[j] 1 prev[i] j if dp[i] max_len: max_len dp[i] end i # 回溯路径 seq [] while end ! -1: seq.append(nums[end]) end prev[end] seq.reverse() return max_len, seq第二种解法是贪心 二分查找时间复杂度O(n log n)只求长度比较省事。它维护一个tails数组tails[k]表示长度为k1的递增子序列中末尾元素的最小值。如果当前数比tails最后一个元素还大就追加否则用二分找到第一个不小于当前数的位置并替换。但要注意用贪心二分的tails数组直接输出序列是不严谨的因为中间元素可能被替换过不一定是合法的递增子序列。如果题目要求输出某个具体的子序列稳妥的做法还是用O(n^2)的DP加前驱回溯或者在贪心过程中额外记录“每个数字作为某个长度的子序列尾部时的位置”再用反向遍历拼出序列。这里的取舍在笔试中很关键先看清楚题目是只求长度还是要求输出完整序列再决定套用哪种模板。3.4 笔试中的编码规范与调试建议编程题部分还有一个隐性考察点代码规范和调试能力。OJ判题系统只看最终输出结果但你的代码结构、变量命名、边界判断在阅卷人眼里是有印象分的。更重要的是好的编码习惯能帮你自己在考场上减少出错概率。我的建议是每道题都按照“读题 - 明确输入输出 - 思考边界 - 写核心逻辑 - 自测用例”的顺序来。举个例子字符串压缩题写完第一版后至少在本地跑这几个用例空串、单个字符、全部相同字符、没有相邻重复字符、连续出现10个以上字符。每一个都代表一类边界跑通了再提交能节省大量提交次数。很多OJ系统会记录提交失败次数白白浪费好几次提交机会是很亏的。4. 附加题当笔试遇上业务输入法候选词排序怎么答4.1 为什么触宝会有这道题触宝这套卷子最后有一道开放附加题方向基本是“说说你会如何设计一个输入法的候选词排序机制”。这道题放在这里一点也不意外因为触宝的核心产品就是输入法候选词排序直接影响用户打字效率是输入法体验的关键环节。出这样的题并不是要求应届生真能设计出商业级的排序系统而是想看看你面对一个开放问题时能不能拆解问题、给出有层次的方案、体现出技术判断力。从出题角度说这种题比编程题更难答。编程题有标准答案开放题没有。它考察的是你的知识广度和思考深度以及你能不能把学校学的东西跟实际产品场景结合起来。4.2 一个比较完整的答题框架我当年看到这类题第一反应是“这不就是按词频排吗”。实际上只答这个远远不够。一个合格的答案至少应该包含三个层次。第一层基础词频排序。这是最简单、最可落地的方案。统计所有候选词在语料库中的出现频率作为静态排序依据。词频越高排得越靠前。这个基线方案就足以覆盖80%的场景不能丢。第二层加入上下文信息。用户当前打的这个拼音结合上文的词或句子可以预测下一个词的概率。这本质上是N-gram语言模型比如二元模型P(w_i | w_{i-1})。如果用户输入了“今天”那么“天气”就比“天气的”更靠前因为前者和“今天”的共现概率更高。这一层方案能显著改善候选词排名的合理性。第三层用户个性化。这是输入法区别于通用搜索排序的关键。不同用户有不同用语习惯有人爱说“哈哈哈”有人经常打“好的”。通过对用户历史输入做统计建立用户级别的词频表让高频使用词浮动到更靠前的位置。同时要处理冷启动问题——新用户没有历史数据就退回到全局词频和上下文模型。再往上还可以讲排序学习Learning to Rank。把词频、上下文共现概率、用户个性化得分、时间衰减因子等作为特征用样本训练排序模型例如GBDT、RankSVM。这一层能体现你对机器学习排序方向的了解但要注意开放题里谈到这个层级的难点不是“用哪个模型”而是样本怎么获取、特征怎么对齐、线上推理怎么做实时。答到这一层已经超出多数应届生的预期了。这题的答题技巧是“先给出分层框架再往下细讲”。不要一上来就讲深度学习模型。面试官想看到的是你能从简单方案开始依据使用场景逐步优化而不是只背了一个高大上的名词。5. 实战教训笔试中最容易踩的坑与时间管理5.1 时间分配先拿基础分再啃难题这套笔试的时间大概是90分钟到120分钟选择题加编程题全部要在这个时间内完成。我见过很多人的失败方式在一道编程题上死磕40分钟结果后面的题连看都没来得及看。这是最亏的因为卷子里一定存在“会做但没时间做”的题。我的建议是拿到卷子先用3到5分钟把所有题目扫一遍标记出“容易题”“中等题”“难题”。选择题尽量在25到30分钟内完成遇到犹豫超过1分钟的先跳千万别卡住。编程题按“先易后难”的顺序做每道题最多分配25到30分钟。如果15分钟还没思路果断写一个暴力解法提交至少能拿部分分再回头想优化方案。最后留10分钟整体检查一遍重点看有没有读错题目、有没有漏掉多组输入的情况。5.2 真实踩坑记录这里整理几个这套题常见的翻车现场都是实际发生过的事情希望大家避免字符串压缩题忘了判空。输入是空串时直接访问s[0]就会抛异常OJ报错0分。一个if语句的事很多人就是会忘。树的之字形遍历奇偶层判断写反。题目要求第一层从左到右、第二层从右到左有的同学把第一层当成第0层但在判断时用了level % 2 1才需要反转结果第二层也处理反了。这里建议代码里明确注释“level从0开始偶数层从左到右”。LIS题DP数组初始化写错。dp数组应该全部初始化为1因为每个元素自身可以构成长度为1的递增子序列。有的同学初始化为0最后答案会比正确值少1。这个错误非常隐蔽但测试用例一跑就现形。输入输出格式问题。有的笔试题要求读取多组测试数据直到文件结束。很多同学只处理了一组就提交导致只过部分用例。这种情况要养成习惯看到题目描述里有“输入包含多组测试数据”就马上想到用循环读取。开放题上来就写深度学习模型。不是说不能写而是没有从简单方案开始递进显得思路跳跃也容易暴露出对基础排序流程不熟悉。先讲词频基线再一层层往上加反而是最稳的答法。5.3 笔试之前应该怎么准备基于这套题的风格如果你正在准备类似的校招笔试我建议按下面的思路来准备。刷题重点放在数组、字符串、二叉树、动态规划这四类高频问题上LeetCode上打上这四类标签的前100道题基本够了。不要贪多要保证每道题都能独立写出并跑通而不是看了一遍题解就划走。基础选择题也不能裸考。操作系统、计算机网络、数据库、编程语言各找一份高频考点清单过一遍。这个环节没有太多捷径靠的就是日常积累。但你可以用“费曼学习法”来压缩时间每天挑一个知识点用自己的话讲给别人听讲不出来就是没懂再回头查资料直到能讲明白为止。最后强烈建议在正式笔试前做几次全真模拟。找一个在线OJ平台开摄像头定好时间关闭所有辅助工具把一套真题从头到尾做一遍。你会发现模拟和平时刷题完全是两回事时间压力、心理压力都会影响发挥。提前适应这种状态考场上会从容很多。如果让我总结这次复盘最大的收获我觉得就是一句话这类校招笔试题真正考的不是你会不会某道题而是你的知识体系有没有漏洞、代码习惯能不能支撑你在压力下写出可靠的东西。把基础打扎实比默写十套模板都管用。