360研发工程师笔试题复盘：字符串处理、动态规划与贪心调度全解析

做研发岗笔试刷题的人很少绕得过360这套2016年研发工程师内推笔试题。那年我正好也投了360的内推拿到笔试链接之后第一感觉是题量不大但每一道都长在你平时最容易忽略的细节上。现在回过头看这套题无论从考点分布、难度梯度还是代码量控制都堪称大厂笔试题的经典样本。今天把它复盘一遍不是为了单纯追忆那年的面试季而是想给正在准备笔试的人一份能直接落地的解题思路和避坑清单。先交代一下背景。2016年的360内推笔试岗位是研发工程师编程题部分一共几道大题时间大约一个半小时到两个小时。题目风格不是那种需要你写几百行代码的工程题也不是压死人的ACM竞赛题而是经典的“筛人题”——看起来人人会做但一跑边界数据就露馅。它考的不是你会不会写代码而是你有没有把代码写对、写稳、写快的能力。这几年我带过不少学弟学妹准备大厂笔试会反复拿这套题当摸底测试。原因很简单它覆盖了字符串处理、排序、动态规划、贪心模拟这些笔试最高频的方向而且题干短、信息密度高特别适合用来训练笔试节奏。1. 整体考情与题目风格拆解1.1 内推笔试的定位不是选高手是筛掉不稳定因素很多人对内推笔试有误解觉得“内推嘛走个流程而已”。实际上内推笔试往往比正式校招笔试更早启动名额有限筛选力度一点不小。360这套2016年内推笔试题的定位非常清楚在短时间内判断候选人是否具备扎实的编码基本功、清晰的逻辑思维和基本的工程习惯。它不需要你证明自己“算法很强”而是需要你证明自己“能把事情做对”。从考点分布来看这套题有几个明显倾向。第一字符串处理频率很高因为字符串边界情况多最容易考察细致程度。第二排序和查找必考但不会直接让你调库而是要求你理解排序的思想并处理变形问题。第三动态规划和贪心都会出现但难度控制在中等偏下重点考察状态定义和贪心策略的证明。第四输入输出格式往往埋着坑比如多组测试数据、行末空格、整数溢出这些反而成了区分度最高的地方。1.2 题量、难度与时间分配的实战经验具体到实战环节这套笔试的时间压力并不小。我记得当时编程题总共有好几道每一道都不是秒杀题平均需要十五到二十分钟才能写稳。再加上前面可能还有选择题或其他题型真正留给编程题的时间往往比想象中紧张。这里有一个经验一旦看到熟悉的题目不要急着写代码先在草稿纸上把边界条件和测试用例列出来再动键盘。这样做看似浪费了两分钟实际上能避免百分之八十的返工。难度梯度上这套题明显分了三档。第一档是热身题比如字符串压缩、数组去重做不出来基本告别面试。第二档是常规题比如TopK问题、最长递增子序列需要你有一定的算法积累。第三档是拉开差距的题比如带条件的任务调度表面是模拟实际考察贪心策略的严谨性。我的建议是热身题控制在十分钟以内常规题控制在二十分钟以内难题允许自己思考十分钟想不出来就先写暴力解法保底不要死磕。2. 核心细节解析与高频考点精讲2.1 字符串处理题边界条件就是命门字符串题在笔试里永远占一席之地360这套题也不例外。这类题目本身算法含量不高但特别能暴露一个人写代码的习惯。比如有一道很典型的字符串压缩题统计连续相同字符的数量将字符串压缩成“字母出现次数”的形式。如果压缩后的字符串不比原串短则返回原串。看起来很简单但里面至少有三个坑。第一个坑是“连续字符”的界定必须用双指针或循环变量扫到字符变化为止不能用字典统计全局出现次数。第二个坑是长度比较有人算出压缩结果之后忘了和原串长度比较直接返回压缩串这种粗心在真实笔试中非常致命。第三个坑是数字拼接出现次数可能超过一位数必须转换成字符串再拼接不能直接做字符加法。我在给学弟学妹做模拟面试时这道题的正确率不到六成大多数错误都出在边界用例上。2.2 排序与TopK问题堆、快排还是sort库TopK问题是研发岗笔试的常青树360这套题里也有类似影子比如“求一个整数数组中最大的K个数”。很多人的第一反应是调用排序接口取前K个这当然能过但如果笔试要求手写算法或者数据规模很大就需要考虑更优方案。当时我在笔试里用的就是最小堆维护一个大小为K的堆遍历数组时如果元素比堆顶大就弹出堆顶并将新元素入堆最后堆中就是最大的K个数。这里要展开讲讲为什么选最小堆而不是最大堆。如果维护最大堆堆顶始终是当前最大值遍历完整个数组后堆里剩下的是最大的那部分没错但堆里的元素并不方便按顺序取出。而最小堆的堆顶是堆中最小的元素也就是当前“前K大”的门槛每遇到比门槛大的数就替换掉保证堆里永远是全局最大的K个。这个思想不止适用于TopK很多流式数据的场景都能用上。复杂度上建堆复杂度O(K)遍历数组每次堆调整O(logK)整体O(N logK)比排序的O(N logN)更好尤其是N非常大而K很小时优势很明显。2.3 最长连续递增子序列动态规划还是双指针动态规划在笔试中属于中坚考点360的题库里也有这类题目比如“求数组中最长连续递增子序列的长度”。连续这个词非常关键它意味着状态转移非常简单dp[i]表示以第i个元素结尾的最长连续递增子序列长度当nums[i] nums[i-1]时dp[i] dp[i-1] 1否则dp[i] 1。最后取所有dp[i]的最大值。但考试时我并没有真的开一个dp数组而是用一个变量记录当前递增段长度另一个变量记录全局最优值空间复杂度降为O(1)。这种优化在笔试中很常见——很多所谓动态规划题其实可以进一步简化为贪心或双指针。关键是你要能判断“状态之间有没有后效性”。这个场景里每个位置的状态只依赖前一个位置滚动变量完全够用。我建议在刷题时遇到DP题先想想能不能压缩状态这既是笔试抢时间的技巧也是面试聊优化时的加分项。2.4 带冷却的任务调度模拟背后的贪心策略最后一道典型题是任务调度给定任务列表和冷却时间要求输出最短执行时间。这道题给很多人造成了心理阴影因为看起来只是模拟但直接一行行推进时间轴去模拟运行效率很低而且调度策略稍有偏差就会出错。正确的思路其实是贪心统计每个任务出现的次数找到出现次数最多的任务设其数量为maxCount那么最短时间下界至少是(maxCount - 1) * (n 1) 1。再统计出现次数等于maxCount的任务种类数有几种就把最后的1换成几。最后还要和任务总数比较取较大值。为什么要用这个公式我来解释一下。把频率最高的任务当作“骨架”每隔n个其他任务就必须插入一个同类型任务。如果所有任务执行完还有剩余空闲槽位那总时间就是“骨架长度”如果任务多到能填满所有空闲槽位那总时间就等于任务总数因为此时瓶颈不再是冷却时间而是任务本身。这两个值取max就是最优解。这个推导过程我在笔试时没有完全想透只是按直觉写了贪心模拟结果部分用例超时。后来复盘才意识到这种题的精髓就是数学建模用公式替代逐帧模拟。3. 实操过程与核心代码实现3.1 字符串压缩题Python参考实现与边界测试这里我用Python把逻辑写清楚虽然2016年笔试很多人用的是C但算法思路完全通用。先上代码def compress(s: str) - str: if not s: return s res [] count 1 for i in range(1, len(s)): if s[i] s[i - 1]: count 1 else: res.append(s[i - 1] str(count)) count 1 res.append(s[-1] str(count)) compressed .join(res) return compressed if len(compressed) len(s) else s测试用例要覆盖几种情况空串、单个字符、全部相同的字符如aaaa、交替字符如abab、压缩后不短于原串如abc。你把这些用例跑一遍基本就能确认代码没有问题。这个过程中最容易出错的是循环结束后最后一段字符的处理很多人忘了在循环外面再append一次导致漏掉末尾的字符组。这种细节在笔试环境里特别容易犯因为紧张状态下人倾向于“写完主逻辑就交卷”不会去补最后的收尾。3.2 TopK问题最小堆实现与复杂度对比最小堆在Python里没有现成的类所以用heapq模块实现。注意heapq默认是最小堆正好符合我们的需求。代码如下import heapq def top_k_largest(nums, k): if k 0: return [] heap nums[:k] heapq.heapify(heap) for num in nums[k:]: if num heap[0]: heapq.heappop(heap) heapq.heappush(heap, num) return sorted(heap, reverseTrue)这里做了一个边界处理k 0时直接返回空列表防止heapq报错。返回前排序是为了让输出更直观实际笔试中如果要求按原顺序输出就不能做这一步。还有一个小细节如果k比数组长度还大应该返回整个数组排序后的结果所以调用前最好加一个判断。这些边界情况恰恰是笔试中最容易丢分的地方我见过太多人在主逻辑正确的情况下因为没处理空数组、k超出范围等边界而无法通过全部测试用例。3.3 最长连续递增子序列状态压缩后的简洁写法这个题用滚动变量非常简洁。我用下面这版代码作为标准参考def find_length_of_lcis(nums): if not nums: return 0 max_len 1 cur_len 1 for i in range(1, len(nums)): if nums[i] nums[i - 1]: cur_len 1 max_len max(max_len, cur_len) else: cur_len 1 return max_len整个过程只需要一个for循环时间复杂度O(N)空间复杂度O(1)。有些同学会想用动态规划数组把每个位置的dp值都存下来结果发现后一个状态只依赖前一个保存全部状态纯属浪费。其实很多动态规划题都能做状态压缩尤其在笔试里空间复杂度往往是隐性扣分点。写出这份代码不需要什么高深技巧但要理解为什么cur_len在遇到下降时要重置为1而不是0——因为当前元素本身就是一个长度为1的新递增序列。3.4 任务调度的贪心公式从模拟到数学建模下面给出任务调度题的完整实现。我采用先统计频率、再套公式的思路代码量小运行快而且不需要模拟时间轴。from collections import Counter def least_interval(tasks, n): counts list(Counter(tasks).values()) max_count max(counts) max_count_num counts.count(max_count) ans (max_count - 1) * (n 1) max_count_num return max(ans, len(tasks))很多人不理解为什么最后要max(ans, len(tasks))。我举个例子假设任务是[A,A,A,B,B,B]冷却时间n0。此时maxCount3maxCountNum2公式得到(3-1)*(01)24但任务总数是6显然不可能在4个单位时间里执行完6个任务。当冷却时间为0时根本没有等待限制总时间就是任务总数。所以公式算出的是一个理论下界实际时间必须至少为任务总数。如果公式结果比任务总数大说明存在空闲等待时间如果比任务总数小说明任务足够密集可以做到无空闲执行。这道题给了一个很重要的启发很多复杂度高的模拟题都有机会通过数学规律化为简单公式。笔试时间有限如果你的解法需要循环模拟时间轴而且数据范围很大一定要停下来想想是否存在更优的数学解法。4. 常见问题与排查技巧实录4.1 输入解析的坑多组数据与行末空格笔试环境中输入解析比很多人想象得更重要。360这套题当时采用的标准输入输出有些题目会注明“包含多组测试数据”这意味着你的程序要能循环读取不能只处理一组就结束。Python里通常用sys.stdin.read()或sys.stdin.readline()配合while循环处理。C则要考虑while(cin n)的写法。我自己的习惯是拿到题目先看输入描述里有没有“多组”“直到文件结束”这类字眼如果有就先搭好循环框架再写核心逻辑。行末空格也是一个经典扣分点。有些评测系统接受行末多余空格有些则严格按照标准输出模式比对。最稳妥的做法是在输出循环中判断是不是最后一个元素只有不是最后一个元素时才打印空格。虽然这行代码不起眼但它决定了你能不能拿到全部分数。4.2 整数溢出与数据类型选择2016年的C笔试中整数溢出坑了不少人。比如计算任务调度公式时(maxCount - 1) * (n 1)可能超出int范围尤其当maxCount和n都很大时。正确做法是使用long long或者将中间结果转为64位。Python因为没有溢出问题所以写起来很舒服但如果你用C/Java就必须有意识地检查每个乘法、加法是否会溢出。我在实际面试辅导中反复强调一个习惯写任何和数值有关的代码先问自己“这个数最大可能是多少”再决定用int、long还是long long。4.3 超时排查别急着优化算法先看是不是死循环笔试中遇到超时很多人第一反应是“算法不够优”但实际上有一半以上的超时是死循环或边界条件错误导致的。比如字符串压缩题中如果循环变量更新条件写错可能永远无法到达循环末尾程序一直空转。再比如TopK题目中如果比较符号写反堆永远不会更新但程序会正常结束输出错误结果而不是超时。这里我建议的处理顺序是先检查是否有死循环再检查是否有多余的重复计算最后才考虑换算法。用几个小规模用例测试能跑通、但大规模用例超时的情况绝大多数是算法复杂度问题如果小规模用例都卡住那一定是逻辑死循环。4.4 速查表这套题最常见的五个错误为了让你在笔试前能快速自查我整理了一个针对这套360题的错误速查表错误类型出现场景解决思路未处理空输入字符串压缩、数组类题目开头直接判断长度空串返回空串循环末尾遗漏处理字符串压缩统计连续字符循环结束后手动补充最后一段比较符号写反TopK堆更新、递增序列判断用简单例子手动走一遍代码忘记输出格式要求所有涉及打印的题目逐字比对输出描述注意空格和换行中间结果溢出任务调度乘法计算C使用long longPython不用过度担心这个表的价值不在于它多全面而在于它对应的是真实笔试中高频出现、又容易被忽视的细节。如果上考场前你能把这几类错误全部避开这套题至少能拿到百分之八十的分数。5. 备考建议与后续扩展思路5.1 一周冲刺策略从题型到节奏的全方位准备如果你离笔试还有一周我的建议是不要盲目刷难题而是按照“高频考点限时训练”的方式推进。前三天集中刷字符串、数组、链表这些基础数据结构题重点训练边界条件意识中间两天专门练动态规划和贪心熟悉状态定义和贪心证明最后两天做整套模拟题严格按考试时间执行训练自己在压力下的时间分配能力。这套节奏对任何公司的研发岗笔试都适用因为它本质上是围绕“笔试考什么”而不是“某公司考什么”来设计。5.2 复盘比刷题更重要如何从一套题里榨出最大价值做完一套题不是终点复盘才是关键。我建议每道错题都按四个问题重新过一遍第一考的是什么知识点第二我做错的原因属于知识盲区、粗心大意还是时间不足第三这个知识点还有哪些变形第四有没有更优解是我没想到的。比如任务调度这道题如果你只是把正确代码背下来下次换个条件你可能还是不会。但如果你理解了“最高频任务决定理论下界”的核心思想再遇到带冷却时间的变体题你就能举一反三。这些年我在面试候选人的时候经常问笔试中出错的那道题是怎么解决的。不是为了考察记性而是想看看这个人有没有复盘的习惯。能清楚说出“我当时错在哪里、后来怎么查资料、现在怎么理解”的候选人往往要比刷题量更大但从不复盘的人表现更好。笔试只是起点复盘能力才是一个人长期成长的分水岭。5.3 从笔试到面试这套题还能怎么用360这套2016年的题虽然年代久远但里面的题目类型至今仍在各种大厂笔试中出现。更妙的是这些题非常适合拿来当面试前的模拟问答。比如面试官问你“如何求数据流中的中位数”你可以用TopK题里的堆思想作答问你“进程调度和任务调度有什么区别”你可以用冷却时间任务的贪心思路来谈。我在面试辅导中经常提醒候选人笔试题目不是考完就扔的很多题目在面经里改头换面又会出现。把笔试中每一个经典题的思路吃透远比浮光掠影地刷三百道题更有价值。如果你正在准备研发岗位的笔试我的建议是把这套题当作一份自带解析的体检报告。它检验的不是你的天赋而是你是否具备一个合格工程师的基本素质逻辑严谨、边界敏感、追求更优解。把这些素质打磨好你拿下的不止是360的笔试而是任何一家公司的研发岗位笔试。