触宝科技校招研发笔试题全解析：算法、数据结构与系统设计实战

拿到这份《触宝科技2017秋季校招研发笔试题（第一批）》的时候，我才刚准备完秋招的第三场笔试。说实话，当时看到“触宝”两个字，脑子里第一反应是输入法和那款海外很火的免费电话应用。后来真把这套题从头到尾做了一遍，才发现它的出题风格和市面上常见的刷题平台套路不太一样：既考基础算法，又不放过工程场景，甚至有几道题明显是奔着“你懂不懂移动端业务逻辑”去的。这篇文章我就以过来人的身份，把这份笔试题的考点、解题思路、容易踩的坑以及我自己的复习方法完整拆一遍，给还在准备校招或者想进移动互联网公司的朋友做个参考。

1. 笔试题整体布局与考察思路

1.1 触宝研发岗笔试的核心能力模型

先说说这份题的整体印象。触宝科技是做输入法和通讯工具出身的移动互联网公司，所以在筛选研发候选人时，它不会只盯着你能写出多少种排序算法，而是更关心三件事：第一，计算机基础扎不扎实；第二，面对真实业务场景能不能把技术用上去；第三，工程代码习惯好不好。这些考察点在2017秋季校招第一批笔试里体现得特别明显。

题目一般分成几个模块：计算机基础知识（计算机网络、操作系统、数据库）、数据结构和算法编程题、业务场景设计题，以及一小部分逻辑推理或数学题。前面两部分占分比重最大，但真正拉开差距的往往是场景设计题。因为算法题大家都刷过，只要功底够就不会差太多，而场景题考的是你平时有没有思考过一个产品功能背后需要什么样的技术支撑，这个光靠刷题是刷不出来的。

我在准备这轮笔试的时候，把触宝的业务特点也纳入了复习范围。输入法意味着大量文本处理、字符串匹配、用户词频统计；通讯工具意味着高并发、消息推送、客户端与服务端的数据同步。你会发现笔试题里不少考点都能在它们自己的产品里找到影子，所以备考时不要只埋头刷LeetCode，花点时间了解目标公司的产品和技术栈，往往能帮你猜到很多题目的考查方向。

1.2 题型结构与时间分配策略

根据我做完这套题以及后来和进面试的同学交流的情况，笔试的时间一般给得比较紧。基础知识部分如果熟练，大概能省下不少时间给编程题；如果基础题卡住了，后面编程题就没时间充分展开。我自己的策略是：拿到卷子先花两三分钟把整张卷子扫一遍，明确哪些题是送分题，哪些题需要深入思考，然后从送分题开始做，保证先把能拿到的分全部装进口袋。

基础知识部分多是选择题或填空题，覆盖网络协议、进程线程、内存管理、数据库索引这些内容，复习到位了基本可以快速拿下。算法编程题通常有两三道，难度呈阶梯状，第一题可能是字符串或数组的基础操作，第二题会上升到搜索或动态规划，第三题则可能结合具体场景来考。场景设计题一般放在最后，它是开放性的，没有标准答案，但你给出的方案越具体、越接近工程实践，得分就越高。

这里要特别提醒一点：不要在单个选择题上纠结太久。笔试和面试不一样，面试官能看到你的思维过程，但笔试只有最终结果，所以性价比很重要。我见过很多同学在一个有争议的多选题上耗了十分钟，结果编程题没写完，这个时间分配就非常不划算。

2. 核心题型拆解：算法与数据结构

2.1 高频算法题型的解题思路还原

算法编程题是整份卷子的重头戏，也是能拉开普通候选人和优秀候选人差距的地方。从我接触到的这批题来看，有几类算法题出现频率很高，这里我挑最典型的两种详细说说。

第一类，字符串处理类。触宝做输入法，对字符串操作的偏爱几乎是可以预见的。常见考法有：单词反转、字符去重、子串匹配、括号匹配校验等。这类题表面看简单，但特别考验边界处理能力。比如单词反转这道题，很多同学第一反应是split再reverse，但笔试官可能要求你实现的是原地反转，或者不允许使用额外空间，这时候就要考虑先反转整个字符串，再逐个单词反转的两步法，同时处理首尾空格和多个连续空格的情况。

第二类，二分查找及其变体。比如在一个有序数组中查找目标值的第一个和最后一个出现位置。很多同学能写出基本二分，但一旦要求边界正确，就容易陷入死循环或者返回错误的下标。这类题考察的不是你会不会二分，而是你能不能跳出“找到目标就返回”的思维定势，在二分过程中持续压缩搜索空间，直到区间收敛。核心点在于：当中间值等于目标值时，不能立刻返回，要看是找左边界还是右边界来调整high或low的值。

2.2 经典手写代码题参考实现与边界分析

我根据回忆还原了一道比较有代表性的题目，并附上一份可供参考的Java实现，题目是“将字符串中的每个单词逆序输出，单词之间由空格分隔，要求不使用额外空间”。

public class ReverseWords { public String reverseWords(String s) { if (s == null || s.length() == 0) { return s; } char[] chars = s.toCharArray(); int n = chars.length; // 第一步：反转整个字符数组 reverse(chars, 0, n - 1); // 第二步：逐个单词反转，顺便处理多余空格 int start = 0, end = 0; for (int i = 0; i < n; i++) { if (chars[i] != ' ') { start = i; while (i < n && chars[i] != ' ') { i++; } end = i - 1; reverse(chars, start, end); } } return new String(chars).trim(); } private void reverse(char[] chars, int left, int right) { while (left < right) { char tmp = chars[left]; chars[left] = chars[right]; chars[right] = tmp; left++; right--; } } }

这里有一个非常容易踩的坑：如果原字符串开头或结尾有空格，或者单词之间有多个连续空格，两次反转很容易把多余空格也带进结果里。所以我在代码里用了一个相对取巧的方式——只对非空格区间的单词做反转，最后统一trim。虽然严格来说“不使用额外空间”的要求下用toCharArray是在原地操作字符数组，但String本身不可变，笔试时如果环境允许这样处理，写清楚思路和复杂度分析就可以。

再补充一道常见的链表类题目，比如“判断一个链表是否有环”。这道题看起来简单，但很多人在证明快慢指针为什么一定能相遇时会卡壳。其实核心逻辑是：如果链表里有环，快指针每次移动两步，慢指针每次移动一步，快指针相对于慢指针的速度差是1，所以两者之间的距离会逐步缩短，最终一定会相遇。笔试时除了写代码，最好把这个推导过程也写在注释里或旁边，让阅卷官看到你不只是背了模板。

2.3 开放型逻辑题的答题框架

除了标准的算法题，这份笔试题里还出现了一些类似脑筋急转弯的开放型逻辑题。这种题不会直接问你“写一个排序算法”，而是给一个现实中的约束条件，让你设计方案。比如“在一个很大的日志文件中，统计出现次数最多的前100个IP地址”这类。

这类题其实是在变相考察你对哈希、堆、外部排序这些知识点的理解深度。正确的思考路径是：先明确内存是否放得下全部数据，放不下就需要分治；然后考虑用哈希表对IP做计数；最后用容量为100的小顶堆维护出现次数最多的前100个IP。每一步的存储复杂度都要说清楚，这样答案就会显得非常完整。

我当时在复习这类题时总结了一个答题框架，叫“三步走”：第一步说清楚数据规模和数据特征，第二步根据规模选择适合的数据结构和算法，第三步分析时间复杂度和空间复杂度，并指出瓶颈在哪里。只要按这个框架答，基本不会跑偏。

3. 工程能力考察：系统设计与场景题

3.1 场景题背后隐藏的工程考核点

编程题之外，系统设计类和业务场景类题目是触宝这份笔试题中非常有特色的一部分。它不会让你设计一个庞大的电商系统，而是会给你一个相对聚焦的功能，比如“如何为输入法设计一个输入联想模块”，或者“如何为一个IM应用实现消息的可靠投递”。这一类题目背后隐藏的考核点，我总结下来有三个：需求拆解能力、技术选型能力、以及表达条理性。

以输入联想模块为例，很多同学第一反应就是“用Trie树”。这个答案对，但只答对了一半。面试官和阅卷官更想看到的是：你用什么数据结构存储词库，词库怎么维护和更新，联想结果的排序依据是什么——是用户历史输入的频率，还是全局热度，或者结合了上下文信息。如果你能在答案里体现这些层次，说明你真的思考过一个输入法产品是怎么工作的，而不是单纯背了一个数据结构的定义。

再比如消息可靠投递这道题，很多人上来就聊TCP，但题目要的可能是一个应用层的机制：客户端发送消息后，服务端返回ACK，客户端超时未收到ACK则重传；服务端需要做消息去重，防止客户端因为重传导致同一消息被处理两次。这套机制其实和TCP的可靠传输原理很像，但你要把它套用到即时通讯的业务场景中去描述，才能拿到高分。

3.2 搜索自动补全场景的答题结构参考

我练习过一道很有代表性的场景题，题目大致是“在搜索引擎或输入法中，当用户输入一个前缀时，系统需要快速返回若干补全候选词，请设计一个方案”。这道题的答题结构非常能体现一个人的工程思维，我这里给出一个可以套用的版本。

先是需求分析：用户输入“自”，系统需要返回“自然语言处理”“自动驾驶”“自媒体”等候选词，要求延迟足够低，比如几十毫秒内返回，而且候选词需要根据热度或用户个性化行为排序。然后是方案设计：底层用Trie树存储词库，每个节点存一个字符，节点上附一个热门候选词的列表，这样用户输入前缀时，直接定位到对应节点并取出候选列表，时间复杂度只和输入长度有关，和词库总量无关。

但这里有个细节很多人会漏掉：如果每个节点都存一份候选词列表，内存会非常大。所以实际工程中往往采用“Top K缓存 + 增量更新”的策略，只在部分热点节点上保存候选列表，其他节点动态计算。把这个权衡讲清楚，比单纯说“我用Trie树”要高级得多。这道题答完，基本就能看出来一个人有没有真正考虑过“底层数据结构和上层业务需求之间的匹配关系”。

3.3 从产品反推技术需求的方法

场景题还有一种考法，就是给你一个产品功能描述，让你反推技术需求。比如“输入法需要根据用户输入的拼音序列，输出对应的候选汉字”，你打算怎么做？这种题没有标准答案，但需要你从输入法的核心技术链路去思考：首先把拼音序列做切分，然后去词库里检索匹配的候选词，再用语言模型或词频信息对候选词排序，最后呈现给用户。

我在准备这类题时发现一个特别有用的方法：把产品功能按照“数据从哪来、数据怎么处理、结果怎么展示”三个环节拆开。数据来源对应存储和查询方案，数据处理对应算法和策略，结果展示对应前端交互和性能要求。按这个思路走，任何场景题都能拆成一个结构化的方案，不会出现无话可说的情况。

这一部分很多同学觉得难，是因为平时只在刷题，很少看技术博客或开源项目。这里我建议准备校招的朋友，尤其是目标公司是工具类或内容类互联网公司的，平时可以多看一些关于搜索引擎、推荐系统、输入法内核的公开分享，不需要多深入，但至少要知道这些系统大概拆分成哪些模块，每个模块解决什么问题。

4. 编程实现与调试环节的经验实录

4.1 手写代码时的四类低级失误

笔试编程题最可惜的不是做不出来，而是会做的题因为一些低级失误丢了分。我在复盘自己的笔试和帮别人看笔试代码时，总结出四类高频失误，这里逐一列出来，你看一眼就知道自己有没有犯过同样的问题。

第一类，变量名和题目含义对不上。比如题目里说了用low和high表示搜索区间，你写代码时用成left和right，逻辑没问题，但阅卷时如果代码和你注释里的说明不一致，很容易被误判。第二类，没有初始化变量。很多语言里局部变量默认值不一定为0，你直接拿来做累加或条件判断，结果就是随机报错。第三类，循环边界退出的条件想当然。二分查找、快排的partition、链表的快慢指针，每一个都对边界敏感，少一个等号就可能是死循环或越界。第四类，该做的判空没做。输入参数为null或长度为0时，代码直接崩溃，这道题即便思路全对，运行结果也很可能直接判错。

我在笔试的时候有一个习惯：写完代码之后，不急着交，按顺序做三件检查——参数有没有判空、循环边界有没有更新、返回值类型是不是符合题目要求。这三件事花费不到一分钟，但能救回很多不该丢的分。

4.2 测试用例设计的三层思路

笔试和面试里“你打算怎么测这段代码”也是一个高频考点。千万不要说“我随便测一下”，那样显得非常不专业。一个相对完整的测试思路应该分三层。

第一层是功能测试，也就是正常的输入输出，覆盖代表典型场景的用例。第二层是边界测试，比如数组长度为1、目标值在数组头部或尾部、字符串为全空格、链表只有一个节点等。第三层是异常测试，输入为空、参数不合法、数据量极大导致超时或溢出等。

我举个具体例子。如果题目要求“实现一个函数，删除有序链表中重复的元素”，那么测试用例至少要有这些：链表为null的用例、链表只有一个节点的用例、所有元素都相同的用例、没有重复元素的用例、重复元素在链表中间和末尾的用例。如果你在答题纸或代码注释里能写出这些测试用例，阅卷官会认为你确实具备工程思维，而不只是会写一个函数。

4.3 时间复杂度和空间复杂度标注技巧

笔试编程题的答题区域如果允许写注释，一定要在代码前面或注释里写明你选择算法的思路、时间复杂度、空间复杂度。这不仅是给阅卷官看，也是给自己理清思路。特别是在你用了不太常规的解法时，一句简洁的“本题使用哈希表将查找时间从O(n)降到O(1)，整体时间复杂度O(n)，空间复杂度O(n)”会立刻让阅卷官明白你的思路是有设计的，而不是碰巧写对了。

另外，如果题目要求“尽可能降低空间复杂度”，你可以在注释里额外说明“这里牺牲了部分时间，换取O(1)空间”，这种权衡能力往往是拿高分的加分项。

5. 笔试复盘与后续行动清单

5.1 错题整理法：按考点而不是按题目归档

笔试结束之后，很多人就把它抛到脑后，直接等结果。但根据我的经验，笔试后的复盘，价值不亚于笔试前的刷题。把错题或没做出来的题整理成一个错题本的时候，不要按题目顺序原样复制，我建议按考点归档。比如字符串处理归一类、二分查找归一类、动态规划归一类、网络协议归一类。这样可以清楚看到自己的薄弱点集中在哪个方向，后续复习才有针对性。

我自己的做法是，每次笔试结束，在表格里统计每类题的对错情况，然后只针对错误率高的考点去查找相应的专题训练。这样做比漫无目的地刷题效率高很多，尤其在秋招时间紧、任务重的时候，精准补短板比泛泛刷题更有用。

5.2 如何把一个笔试失利转化为面试素材

笔试没通过肯定有挫败感，但你仍可以从这份卷子里得到不少东西。就算最终没有拿到面试机会，我也建议你把笔试大题重新做一遍，并整理成一篇笔记，写上完整思路和实现代码。因为很多公司的笔试题和面试题高度相关，这道题这次没写出来，下次换个公司很可能还会考。

更实际一点讲，如果你笔试通过进入面试，面试官经常会看着你的笔试卷子追问：“这道题你当时是怎么思考的？”“为什么这个函数的时间复杂度是O(n log n)？”如果你没有认真复盘过，这些问题很容易把你问住。把笔试中的方案、复杂度分析、边界测试都想明白，面试时会变成一种天然的加分项。

5.3 校招备战中容易被忽视的三条建议

最后再补三条我在整个秋招过程中总结出来的建议，不一定只针对触宝的笔试题，但适用于所有准备技术校招的同学。

第一条，刷题一定要限时。很多人平时刷题很放松，一道题想半小时也没关系，但笔试现场一道题最多给你十五到二十分钟。建议从九月份开始，每天固定一小时模拟笔试环境，连续做三道题，时间一到就停笔，训练自己的时间感知和临场取舍能力。第二条，数据结构要能脱离IDE写出来。校招笔试很多时候是在在线编辑器里写代码，没有自动补全，也没有调试器，这在平时可能没感觉，但上了考场就会知道手写代码的熟练度有多重要。第三条，如果想投移动互联网公司，平时一定要关注客户端开发的相关技术，不要只停留在Web后端那套知识体系里。触宝这种公司在笔试题里很可能就会考到Android生命周期、iOS内存管理、客户端与服务端的数据同步等知识点，没有准备的话，到了考场上遇到就会比较被动。

我在帮身边同学做笔试复盘时，最常说的一句话是：笔试不是终点，它只是你和技术团队之间第一次正式的技术沟通。通过一套题，你展示了自己会什么、怎么思考、怎么表达，公司则通过这些题目判断你是否适合他们的团队。抱着这个心态去对待每一份笔试题，你就不会只是为了“过笔试”而刷题，而是真正通过一次次的笔试和复盘，把自己打磨成一名更成熟的工程师。