看到“360公司2016研发工程师内推笔试编程题”这个标题可能有人会觉得这是份过期的考古资料。但如果你经历过那个阶段的校招或者正在准备今年的秋招我建议你认真把这类老题翻出来过一遍。原因很简单这类笔试编程题的考点和套路至今还在各大厂的笔试题里反复出现只是换了个壳。360当年的研发工程师内推笔试整体难度在互联网公司里属于中上。它的编程题不像现在很多公司那样动不动就上困难级别的动态规划加状态压缩而是更偏向考察基础算法的扎实程度和边界条件的处理能力。说白了就是看你能不能把数据结构的基础题写出干净、稳定、不超时的解法。这篇我就以当年这套题的常见题型为主线结合我后来自己刷题、出题、面人的经验把每一类题的考察点、解题思路、代码实现和踩坑点全部拆开讲透。不管你是准备笔试的在校生还是工作几年想跳槽的老兵这篇都值得你花二十分钟认真读完。1. 整套卷子先拆个底朝天考什么、怎么考1.1 当年的笔试场景和竞争环境2016年前后正好是移动互联网公司校招最火热的阶段360作为头部互联网公司研发岗的简历投递量非常大。内推笔试和统考笔试不一样的地方在于内推本身就是筛过一轮简历的所以笔试题的区分度会更高目的很明确把真正能写代码的人挑出来。当时很多公司采用的是在线笔试系统摄像头监控题目从题库里抽取题型包括选择题、简答题和编程题。编程题通常是两道到三道难度递增时间大概是一个小时到两个小时。你不仅要写对还得在有限时间内跑通所有测试用例这对熟练度要求很高。也正因为如此这套题不算偏门怪题基本不会出现那种需要灵光一现的脑筋急转弯更多的是“你平时有没有认真刷过基础题”的检验。换句话说套路性很强准备好的人能稳定拿分裸考的人基本会挂在第一道题上。1.2 题目难度分布和三种典型风格从我接触到的信息和周围同学的反馈来看360这套题的编程部分大致可以归成三类一类是数组和哈希表的应用一类是字符串处理还有一类是动态规划或者递推。这三类基本覆盖了大多数公司笔试的编程题范围。第一类题通常会给你一个数组要求找重复元素、找缺失数字、统计频次之类的。这类题考的是你对哈希表这种基础结构的敏感度以及能不能把时间复杂度从O(n^2)降到O(n)。第二类题字符串处理会涉及到反转、去重、子串匹配、按规则转换等。这类题看起来简单但实际上特别容易在边界条件上翻车比如空字符串、只有一个字符、大小写混排、包含空格或标点等。第三类题动态规划或者递推常见的有最长上升子序列、背包问题、斐波那契数列变种。这类题考察的是你对状态转移的理解程度。很多人在考场上一看到动态规划就发怵但实际上这类题往往是最高频的送分题前提是你真的懂套路而不是死记代码。2. 高频题型的解题思路从读题到写码2.1 数组加哈希表找出第一个重复元素这类题是笔试里的常客题目描述一般是这样给你一个整数数组从前往后找出第一个重复出现的数字如果没有则输出-1。很多人第一反应是两层循环暴力解这当然能做但效率太低。如果数组长度是10万那要比较的次数就到了亿级肯定会超时。正确做法是用哈希表遍历数组把每个数字存入set或者map如果当前数字已经在集合里了那它就是第一个重复的元素直接返回。这个思路背后其实是一种空间换时间的权衡。你可以把哈希表理解成一个登记簿每来一个数字先查一下登记簿里有没有没有就登记有就说明这家伙重复了。这样一趟走完就能出结果时间复杂度变成了O(n)代价是额外付出了O(n)的空间。我在实际笔试中遇到过类似题当时用的是C的unordered_set。选择它而不是set的原因是它的哈希表实现平均O(1)查找而set底层是红黑树虽然也能用但平均复杂度是O(log n)。在笔试场景里性能差这一点点可能就决定了你能不能过某些大数据量的测试点。2.2 字符串处理看似简单却最容易翻车字符串题是笔试里的一大坑。看起来逻辑很直白写起来却往往因为各种边界条件挂掉。举个例子有一道经典题把一句话里的单词顺序反转但是每个单词内部的字母顺序不变。输入“I am a student”输出“student a am I”。这题最朴素的解法是先按空格把字符串拆成单词数组然后倒序遍历数组拼接结果。听起来很简单对吧但问题往往出在细节上如果输入开头或结尾有空格怎么办如果有连续多个空格怎么办如果字符串是空的怎么办这些都是测试用例可能会覆盖的情况。我当时踩过的坑就是split函数在不同语言里的默认行为不一样。比如在C里标准的istringstream配合getline可以自动跳过连续空格但在有些语言里split之后会产生空字符串项得额外过滤。这类题真正的考察点其实是字符串处理的基本功和容错意识。面试官和出题人不会指望你在十秒钟内写出一个优雅的解决方案他们更想看到的是你能不能把各种边角情况考虑到位而不是只搞定一个“标准输入”。2.3 动态规划LIS题背后的常规套路动态规划在笔试题里几乎是必考的最常见的有一道最长上升子序列LIS。题目让你在一个无序数组里找出最长的严格递增子序列的长度不需要连续。这类题的解法有两个层次。第一层是O(n^2)的做法定义dp[i]表示以第i个元素结尾的最长上升子序列长度对于每个i去遍历它前面所有的j如果nums[j] nums[i]就尝试用dp[j]1更新dp[i]。这个思路直观写完也不难适合作为保底方案。第二层是O(n log n)的优化做法维护一个tails数组tails[k]表示长度为k1的上升子序列里结尾元素的最小值。遍历原数组时用二分查找找到当前元素在tails中的位置然后更新它。这个做法的核心思想是通过贪心让每个长度的子序列结尾尽可能小从而为后续增加长度留出空间。说实话O(n log n)的版本在笔试里不一定需要写出来因为大多数题目的数据范围在O(n^2)可以承受的范围内。但如果你能在考场上写出这个优化版本绝对能跟其他候选人拉开差距。我当时练LIS题的时候花了一个晚上把这两种写法都写熟了后来在不止一家公司的笔试题里都用上了。3. 实操复现用Python还原三道典型题3.1 题目一第一个重复元素题目描述给定一个长度为n的整数数组n在1到100000之间请从前往后找出第一个重复出现的数字若存在则输出该数字否则输出-1。输入输出格式输入第一行是数字n第二行是n个空格分隔的整数。输出一个整数表示第一个重复出现的数字或-1。示例6 1 3 4 2 3 1输出3注意这里为什么不是输出1因为下标从0开始第一个重复出现的元素指的是第二次出现的元素中下标最小的那个。数组里3第一次出现在下标1第二次出现在下标41第一次出现在下标0第二次出现在下标5。3的第二次出现比1的第二次出现更靠前所以答案是3。3.2 代码实现与逐行讲解def find_first_duplicate(arr): seen set() for num in arr: if num in seen: return num seen.add(num) return -1 def main(): n int(input().strip()) arr list(map(int, input().strip().split())) print(find_first_duplicate(arr)) if __name__ __main__: main()这段代码的逻辑非常直接遍历数组把每个数字往set里塞。在塞之前先检查一下set里有没有这个数字有就说明它是第一个重复的元素直接返回遍历完都没有重复就返回-1。这里有一个很重要的细节为什么用set而不是list来记录已出现元素因为set的in操作是O(1)的而list的in操作是O(n)。如果用list外层遍历O(n)里层判断O(n)整体又退回到O(n^2)了等于白优化。3.3 复杂度分析与优化空间时间复杂度和空间复杂度都是O(n)。从理论上讲这已经是这道题的最优解了因为不管怎样你至少得把数组遍历一遍才能知道哪些重复了。但笔试里有个细节值得注意如果数组中所有数字的范围很小比如都在0到100之间可以考虑用一个布尔数组替代set来记录出现情况这样能在常数上省掉哈希的计算开销。不过实际测评中这种优化对结果没什么影响因为n的规模通常不会大到让哈希set变慢的程度。我后来在出题的时候也最喜欢用这类题做热场因为它能很有效地检验候选人是否具备“先用大脑估算复杂度再去写代码”的习惯。如果一个人一上来就写两层循环哪怕最后结果对我也能判断他对数据结构的敏感度还不够。3.4 题目二单词反转题目描述给定一个字符串str包含若干个以空格分隔的单词请将单词顺序反转单词内部字符保持原样。多个连续空格视为一个分隔符首尾空格忽略。输入输出格式输入一行字符串。输出反转后的字符串。示例I am a student输出student a am I3.5 Python实现与关键细节def reverse_words(s): words s.strip().split() return .join(reversed(words)) def main(): s input() print(reverse_words(s)) if __name__ __main__: main()这里Python占了很大的便宜split()在没有参数的时候会自动按连续空白字符分割并且自动过滤掉首尾和中间多余的空格省掉了很多C里需要手动处理的逻辑。这也是为什么我建议现在准备笔试的人至少掌握一门脚本语言因为有些题用脚本语言写能省一半时间。但需要注意的是split()的参数和默认行为在不同语言中不一样。比如Java的split方法如果传入单个空格就不会自动处理连续空格需要传正则表达式\s。如果你平时用Java刷题必须熟悉这个区别。这道题的变种也很多比如不允许使用额外的数组存储单词那就得先反转整个字符串再逐个反转每个单词。这种思路在C面试里会更受欢迎因为它体现了对字符串内存操作的理解。但笔试场景下能用简单方法正确解决问题才是第一位的。3.6 题目三最长上升子序列题目描述给定一个长度为n的整数数组求其最长严格递增子序列的长度。输入输出格式输入第一行是数字n第二行是n个空格分隔的整数。输出一个整数表示最长上升子序列的长度。示例8 10 9 2 5 3 7 101 18输出4一个最长的上升子序列是[2,3,7,101]长度为4。3.7 从O(n^2)到O(n log n)的完整实现先写O(n^2)的版本便于理解def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个版本是标准的动态规划解法。dp[i]的含义是以nums[i]结尾的上升子序列的最大长度。初始化为1是因为每个元素本身可以单独构成一个长度为1的上升子序列。然后对于每个i扫描它前面的所有j如果前面某个元素小于当前元素说明可以接在后面于是用dp[j]1来尝试更新dp[i]。再看O(n log n)的版本import bisect def length_of_lis(nums): tails [] for num in nums: pos bisect.bisect_left(tails, num) if pos len(tails): tails.append(num) else: tails[pos] num return len(tails)这段代码用了一个tricktails数组不一定是真实的子序列但它的长度就是LIS的长度。bisect_left找到第一个大于等于num的位置如果num比所有尾数都大就说明它可以扩展一个更长的上升子序列否则它就替换掉那个位置的尾数因为它比原来的数更小更有利于后续扩展。这个替换逻辑是第一眼看上去比较费解的地方。我当初学的时候也绕了很久后来自己想了一个类比才转过来这个过程就像你在维护一个“员工列表”如果来了一个新员工能力比某个职位的在职者更强就把他替换上去这样整支队伍的平均水平会越变越高但队伍人数才是最终要看的指标。在笔试中如果n不超过5000O(n^2)版本足够应对。但如果n到了10万O(n^2)一定会超时必须用二分优化版。所以两个版本最好都熟练掌握。4. 笔试现场最容易踩的坑4.1 输入输出格式的坑在线笔试的输入输出格式是固定的不按格式来就直接判零分哪怕你的算法再对也没用。常见的坑有读整数时没有处理换行符、读字符串时把整行读成了单词、输出的时候多了空格或换行等。我记得有个同学考360的时候第一题明明写对了但输出的时候多打了一个空格导致全组测试用例都匹配不上。这种失误是最冤枉的。所以交卷前一定要仔细检查输出逻辑尤其是涉及循环打印的场景最后一个元素后面不能有空格。如果用的是Python建议就用sys.stdin.read()一次性读入再按空白字符拆分这样能避免很多input()在行尾和空行上的小毛病。我自己面过的候选人里能用好这一招的笔试通过率明显更高。4.2 边界条件的坑边界条件是编程题最大的失分点。比如第一道题里数组长度为1时不会重复必须返回-1空数组也不能崩溃。第三道题里数组为空时LIS长度是0数组只有一个元素时长度是1。这些情况在题目的示例里通常不体现但后端的测试用例一定会覆盖。写代码的时候我建议养成一个习惯写完主逻辑后立刻用三个特殊用例自我验证一下——空输入、最小规模输入、所有元素相同。这三个用例过了大部分边界问题就不会漏。所有元素相同是一个很经典的坑。比如输入[2,2,2,2]最长严格上升子序列长度应该是1。如果实现时不小心用了等号写成nums[j] nums[i]那就会错误地得到4。题目里写了“严格递增”就意味着不包含相等的情况。4.3 时间不够时的提交策略考场上时间紧张是常态尤其是前面选择题磨了太久留给编程题的时间只剩二十分钟。这时候我建议按照“最优解优先暴力解保底”的原则来安排。如果一道题你能想出最优解直接写不需要犹豫。如果暂时没思路暴力解一定要先写出来哪怕复杂度很差也能拿到一部分测试用例的分数。很多在线笔试系统是分测试点计分的能过几个算几个比交白卷强得多。还有一个小技巧如果题目给出的数据范围里n非常小比如小于100那暴力解可能本身就是出题人预期内的解法不需要强行优化。先看清楚数据范围再动手有时候反而能节省很多时间。5. 这套老题对今天的面试还有多少参考价值5.1 题型没有过时考法在升级这几年各大厂的笔试题目确实在变难但底层的核心考点并没有本质变化。数组、哈希表、字符串处理、基础动态规划依然是出现频率最高的几类问题。360这套2016年的题目里出现的考点放到今天的笔试题里同样成立。变化的是什么呢考法更灵活了比如把字符串处理包装成一个实际的业务场景或者把动态规划隐藏在“求最少操作次数”这类问题里。但只要你基础够扎实剥开外壳看到内核的时候会发现还是那些老朋友。所以我一直建议准备笔试的人不要一上来就刷难题怪题。把基础题吃透做到看一眼就能写出代码的程度比囫囵吞枣刷三百道难题有用得多。这套2016年的题就是一个很好的基础训练素材。5.2 语言选择C还是Python回到复习策略上我当时是用C刷题的现在回头看觉得Python其实对笔试更友好。原因有三个一是代码量少同样的逻辑用Python写可能只有C的一半长度这在时间紧张的笔试里有明显优势二是内置库强大字符串处理和排序等功能开箱即用三是可读性好写完自己复查起来也快。但如果你投的岗位明确要求C或者Java比如底层开发或者客户端开发那用C笔试反倒更贴合岗位要求。这时候还是投其所好比较好。一个折中的建议是笔试用你最有把握的语言但一定要会读至少两门语言的代码。因为有些公司在笔试后面试阶段会给你一段别的语言的代码让你分析如果完全看不懂就比较被动了。不过说到底语言只是工具能不能写出正确的解题思路才是关键。别在语言选择上内耗太久选一个你用得最顺的然后把精力花在算法本身。