阿里2015校招笔试题解析：从数据结构到算法，大厂研发岗的基本盘

每年校招季都会有人来问我笔试刷题到底按什么节奏准备要不要把近几年大厂真题全刷一遍。我的回答通常很一致——先去找到你目标公司前几年的真题然后认真问自己一个问题这套题想筛出什么样的人以阿里巴巴2015年校招研发在线笔试题为例这是我很推荐研究的一套卷子别看它年头久考察的技术栈和思维模型放到今天依然是研发岗的基本盘。2015年刚好是移动互联网爆发、云计算和大数据平台快速走向成熟的一年阿里那批题的出题逻辑直接反映了当时研发工程师在日常工作中真正需要的基本功数据结构与算法、操作系统与网络、数据库常识以及一定的代码落地能力。这篇博文我会拆解这套笔试题的考察维度、典型题目类型和复习方法也会还原一些解题思路和代码实现。无论你是准备大厂校招还是工作几年后想回来补基础这篇都值得认真看。1. 先弄清2015年这场笔试的出题逻辑1.1 那年的技术风向为什么考的是这些题理解一套笔试题不能只看题目本身要先看它诞生的背景。2015年的阿里正处在核心业务移动化转型的关键期手机淘宝、天猫无线端都在加大投入云计算和大数据业务也在迅速铺开。这种情况下公司需要的研发工程师必须同时对底层基础、工程效率、业务理解有感知。所以笔试没有像很多人想象的那样去考某个特定语言的冷门语法而是把重心放在了计算机核心基础能力上。数据结构、算法复杂度、操作系统进程线程、网络TCP/IP和HTTP、数据库索引和SQL这些内容在实际工作中天天都要碰到。阿里那几年的招聘规模很大笔试本质上是第一轮标准化筛选要在几万份简历里筛出基础扎实、能写代码、有潜力的人。题目不是为了难倒你而是要让面试官在最短时间内得到一个相对可靠的判断。1.2 卷面结构基础客观题叠加在线编程题2015年前后阿里校招研发岗的在线笔试大致分成两个模块客观题和在线编程题。客观题以单选题为主辅以少量多选题覆盖范围包括C/C或Java语言基础、数据结构与算法、操作系统、计算机网络、数据库。在线编程题一般有两道到三道需要在线提交代码并跑测试用例考察实际编码能力。这和我现在看到的很多在线笔试平台流程类似登录系统、看题、写代码、提交、判分。那年头已经有在线OJ判题了但当时考生普遍对ACM式输入输出不够熟悉不少人挂在读入格式上。后文我会专门说在线笔试的代码提交技巧这是一个非常现实的问题。需要注意的是2015年的研发岗没有像现在这样细分到Java后端、C客户端、算法工程师等方向笔试是一套统一的基础题C/C、Java都能作答但数据结构、算法、操作系统这些核心领域是躲不开的。这也提醒我们基础能力是研发岗位真正通用的货币语言只是表达工具。2. 客观题高频考点数据结构是绕不开的基本盘2.1 复杂度分析笔试里的“送分题”与“陷阱题”复杂度分析是笔试客观题里出现频率极高的考点也是最容易被低估的一类题。表面上看只要记住常见数据结构的增删改查复杂度就能应付但题目往往会包装成递归调用、循环嵌套、链表操作的形式让你现场推算。有个经典版本我印象很深考的是对一组数据在不同数据结构里做查找和插入的平均时间复杂度。给大家整理一下常见数据结构的时间复杂度对照数据结构查找平均插入平均查找最坏备注无序数组O(n)O(1)尾部插入O(n)删除需要移动元素有序数组O(log n)二分O(n)O(log n)插入要保持有序单向链表O(n)O(1)头插O(n)无法随机访问二叉搜索树O(log n)O(log n)O(n)退化成链时最坏哈希表O(1)O(1)O(n)冲突严重时退化堆O(1)取最值O(log n)O(1)常用于优先队列这里最容易翻车的是递归类的复杂度推导。比如斐波那契数列的朴素递归时间复杂度是O(2^n)很多人会误记为O(n)或O(n²)。原因是每次调用会分裂出两个子调用形成一棵指数级的调用树。如果改成带备忘录的自顶向下DP或者直接自底向上的循环复杂度就降到O(n)。2.2 二叉树与哈希出现频率最高的两类结构数据结构模块里二叉树和哈希表是阿里的偏爱。二叉树相关题目可以覆盖遍历、重建、层次关系、平衡性判断等子考点。那几年常考的一道选择题是给定一棵二叉树的前序遍历序列和中序遍历序列要求确定后序遍历序列。这题的关键在于前序第一个节点是根节点再用这个根节点在中序序列里切分左右子树递归处理下去。会了这个方法不管怎么换序列都能解。哈希表考的不是“哈希表是什么”而是冲突处理方案。链地址法拉链法、开放定址法的区别负载因子对性能的影响以及最坏情况下查找复杂度会退化到O(n)的原因。举个例子给定一系列关键字哈希函数H(key) key % 11用链地址法处理冲突要求计算等概率情况下查找成功的平均查找长度。这类题需要你手动画一遍哈希表模拟每个关键字插入到哪个桶然后统计比较次数。有意思的是这类题即使过去十年依然是笔试常客。核心就是因为哈希表在缓存、索引、去重等场景里太常用了公司希望候选人真的理解它的运作机制而不是死记八个外部特性。2.3 操作系统与网络的经典题操作系统模块常考以下几点进程和线程的区别、哪些资源是线程共享的地址空间、文件描述符、哪些是独立的栈、寄存器死锁产生的四个必要条件——互斥、持有并等待、不可剥夺、循环等待以及对应的预防和避免策略进程调度算法在不同场景下的优劣比较。网络模块里TCP三次握手和四次挥手几乎是必考。这里有个容易被问懵的细节为什么连接建立要三次握手而不是两次核心原因是两次握手无法防止旧的重复连接请求突然到达服务端导致服务端白白建立连接、浪费资源。TIME_WAIT状态的作用也一样常考保证最后一个ACK能到达对端同时让旧连接的报文在网络中自然消失。HTTP状态码也是高频考点301和302的区别、304协商缓存、404不存在、502网关错误这些在研发日常排查接口问题时用得特别多。笔试里会给你一个场景问应该返回什么状态码或者给你状态码让你判断发生了什么。这里没有捷径就是多积累。3. 在线编程题拆解从容易到进阶的五类题目在线编程题才是整套笔试真正拉开差距的部分。客观题大家背一背都能拿个不错的分数但编程题写不写得出来、写得对不对直接决定了你能否进入面试。下面按类型拆解几类高频题目给出核心思路和代码实现。3.1 数组类找出出现次数超过一半的数这道题在2015年前后流传很广题干通常这样描述给定一个长度为n的数组其中有一个数字出现的次数超过n/2请找出这个数字。最简单的方法是排序后取中间元素时间复杂度O(n log n)也可以用哈希表计数时间O(n)、空间O(n)。但更漂亮的解法是摩尔投票法时间复杂度O(n)、空间O(1)。思路是维护一个候选元素和一个计数器遍历数组时如果计数器为0就把当前元素设为候选人并计数1如果当前元素等于候选人则计数加1否则计数减1。最后剩下的候选人就可能是答案。int majorityElement(vectorint nums) { int candidate nums[0]; int count 1; for (int i 1; i nums.size(); i) { if (count 0) { candidate nums[i]; count 1; } else if (nums[i] candidate) { count; } else { --count; } } return candidate; }为什么这个算法成立因为一个出现次数超过一半的元素在和其它元素两两抵消后计数仍然为正。换句话说它是唯一一个不会被完全抵消掉的元素。这道题考察的是对题目特殊条件的敏感度以及能否跳出“排序”和“哈希”的惯性思路。3.2 字符串类大数相加大数相加是一道经典的字符串模拟题。给定两个用字符串表示的非负整数返回它们相加的结果字符串不能用系统自带的大数类型。思路就是模拟竖式加法从两个字符串的末尾开始逐位相加记录进位最后把结果反转。string addStrings(string num1, string num2) { int i num1.size() - 1, j num2.size() - 1; int carry 0; string res ; while (i 0 || j 0 || carry) { int x i 0 ? num1[i] - 0 : 0; int y j 0 ? num2[j] - 0 : 0; int sum x y carry; res.push_back(0 sum % 10); carry sum / 10; --i; --j; } reverse(res.begin(), res.end()); return res; }这类题容易忽略三个地方第一两个字符串长度不同短的先遍历完第二最高位相加后可能产生新的进位比如“999”加“1”得到“1000”循环条件必须包含carry第三结果字符串如果不反转输出的是逆序。代码里用res.push_back逐位追加最后reverse这是一种比较稳妥的写法。3.3 二分思想旋转有序数组的最小值假设一个按升序排列的数组在某个未知位置做了旋转比如[3,4,5,1,2]要求找出最小元素。直接遍历是O(n)但利用数组局部有序的特性可以做到O(log n)。核心思路是二分每次拿中间元素和右端元素比较如果nums[mid] nums[right]说明最小值在右半区间包括mid1到right所以left mid 1。否则最小值在左半区间包括left到mid所以right mid。int findMin(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else { right mid; } } return nums[left]; }这个写法的关键是用mid和right比而不是和left比。很多人第一次做会把比较对象写成left结果在旋转点刚好位于数组中部的时候就会出错。还有一道变体是数组中包含重复元素这时候nums[mid] nums[right]无法判断最小值在左还是在右只能把right减一退化为O(n)的最坏情况。这个退化过程也是面试官喜欢追问的点。3.4 链表类每K个一组反转链表链表操作是研发笔试里区分度很高的一类题因为涉及指针操作每步都不能错。题目描述通常是给定一个单链表每K个节点一组进行反转最后不足K个的保持原样。这道题的通用解法是使用dummy哨兵节点避免处理头节点时的边缘情况。每次先检查剩余节点是否够K个够的话就把这K个节点反转然后接入原链表。ListNode* reverseKGroup(ListNode* head, int k) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (true) { ListNode* check prev; for (int i 0; i k check; i) { check check-next; } if (!check) break; ListNode* cur prev-next; ListNode* next cur-next; for (int i 0; i k - 1; i) { ListNode* tmp next-next; next-next cur; cur next; next tmp; } ListNode* tail prev-next; tail-next next; prev-next cur; prev tail; } return dummy.next; }这段代码里反转过程用的是头插法的思路每一轮把next节点从后一段提到当前段的头部。写的时候建议在草稿纸上画出prev、cur、next、tail四个指针的位置逐步推进否则很容易出现指针丢失。这个题的考察重点不是会不会调用某个库函数而是能不能用指针精确控制链表结构。3.5 动态规划最长递增子序列最长递增子序列LIS是算法题里的经典也是阿里那几年笔试和面试都爱问的题目。给定一个无序数组求其中最长的严格递增子序列长度。子序列不要求连续但要求相对顺序保持一致。最直观的思路是动态规划。定义dp[i]表示以nums[i]结尾的最长递增子序列长度转移时遍历i之前的所有元素找到nums[j] nums[i]且dp[j]最大的那个加1即可。初始时每个dp[i]都是1最终答案是dp数组的最大值。时间复杂度O(n²)。进阶做法是贪心加二分时间复杂度O(n log n)。维护一个数组tails其中tails[len]表示长度为len的递增子序列中末尾元素最小的那个值。遍历原数组时用二分在tails里找到第一个大于等于当前元素的位置并替换它如果找不到就追加到末尾。tails的长度就是最长递增子序列的长度。int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }我先建议初学者把O(n²)的DP写法练熟因为它的转移逻辑很直观容易扩展到最长公共子序列等变题。O(n log n)的写法则更适合面试时展示优化能力。两道题都能做出来说明你既理解基础又能往更优解上思考。4. 阿里的场景化命题业务是最大的题库阿里笔试有一个很鲜明的特点就是会把一些技术考点包装成业务场景题尤其喜欢结合电商领域。这也是它和其它互联网公司相比出题风格上差异比较大的地方。即使是客观题题干也可能是一个下单流程、一个库存查询接口、一个商品推荐列表考察你在真实业务里会不会用技术解决问题。4.1 并发场景库存扣减如何保证不超卖电商场景里最经典的问题之一就是秒杀场景下的库存扣减。假设一个商品只有100件库存同时有10万用户抢购怎么设计扣减逻辑才能保证不出现超卖这个问题重点考察并发控制。方案可以是数据库层的悲观锁使用SELECT ... FOR UPDATE把库存行锁住扣减完再提交也可以是乐观锁更新时带上版本号或库存数条件如果更新影响行数为0就重试。再往上走还有Redis的原子操作和Lua脚本这个属于高并发架构的范畴。笔试阶段一般不会让你写完整系统但至少要能说出超卖产生的本质原因多个请求同时读到旧库存同时执行扣减。4.2 数据场景商品SKU如何设计存储电商平台上一个商品通常会有多个规格属性比如手机的颜色、内存、版本这些规格组合成了一个可售卖的SKU。笔试里可能会给一张商品表、一张规格表、一张SKU表让你设计表结构或者问怎么根据用户选择的规格快速定位到具体的SKU。这个考点的核心是理解SPU和SKU的区别。SPU是标准产品单元比如“某品牌手机”SKU是库存量单位比如“某品牌手机 蓝色 128G”。多个SKU属于同一个SPU区别在规格属性的组合上。存储设计上一般会把规格属性拆成键值对或JSON存储同时为SKU生成一个摘要ID方便检索。这种题没有标准答案考察的是你面对模糊需求时能不能给出结构清晰、可扩展的方案。4.3 算法场景订单超时自动关闭怎么做还有一个比较经典的场景题用户下单后如果30分钟内未支付系统需要自动关闭订单并释放库存。问你会怎么实现。初级方案是用定时任务定期扫描订单表把超时未支付的订单关掉但这样存在时间窗口不准、扫描压力大的问题。进阶一点的方案是在订单创建时放入延迟队列设置30分钟的延时消费者收到消息后检查订单状态如果仍未支付就关闭。分布式场景下还可以引入时间轮、Redis过期键监听等手段。笔试里你不需要写完整代码但要把方案的演进逻辑说清楚让面试官看到你对实时性和性能的理解。这类场景题让我印象很深的是它不考一个孤立的知识点而是考察“遇到一个业务问题你能不能把它拆解成技术问题再用合适的工具方案去解决”的能力。这也是阿里笔试区别于纯算法比赛题目的最大特点。5. 实战经验这套题告诉我们要怎么准备5.1 时间分配与作答顺序在线笔试的时间限制通常比较紧张我的习惯是先花两分钟把所有题目快速扫一遍心里对题量、难度分布有个底。客观题部分一眼会做的先做拿不准的先跳过并在草稿上记下题号最后再回来处理不要在一道题上死磕超过两分钟。编程题的时间要预留充足一般至少占总时长的一半以上。做题顺序上建议先做自己最有把握的那一道先把基础分拿到手再去攻难题。如果一道题看完三分钟还没有任何思路果断换下一道。笔试是筛选不是竞赛把该拿的分拿到才是策略。5.2 在线笔试的代码提交习惯很多人在本地IDE里写得很好一上在线OJ就挂经常是因为没注意输入输出格式。这里总结几个我自己的经验先看清题目要求的是核心代码模式还是ACM模式。前者只需要实现核心函数后者要自己处理输入输出。如果遇到字符串和数字混合输入注意空格和换行的处理必要的时候用getline或cin.ignore。代码风格要清晰变量名不要用a、b、tmp满天飞面试官可能会看你的代码回放。提交前在脑子里跑几个用例空输入、只有一个元素的输入、边界数值、负数、最大长度。这些用例往往能提前暴露问题。5.3 从笔试到面试的延展准备笔试题的时候不要只满足于把题做出来。每道题都可以问自己三个问题这道题还有没有更优解数据范围变大一个数量级解法还成立吗如果加一个限制条件比如元素无序、有重复、内存受限又该怎么改笔试里的题目在面试中经常被重新拿出来追问。你写了一个O(n²)的解法面试官就会问能不能优化到O(n log n)你用了排序面试官就问你空间复杂度能不能降下来。所以练习的时候要有意识地把一道题吃透把暴力解法、优化解法和最优解法的推导过程都走一遍这样面试时才能接得住追问。6. 写在最后基础越扎实越不怕题新我每年看这套2015年的题目都有新体会。题目本身是固定的但折射出的要求是稳定的好的研发工程师要有扎实的计算机基础、能快速把业务问题抽象成技术问题、并且真的有能力把方案变成代码。准备这类笔试最忌讳的是死记题海战术。你能刷完1000道LeetCode但你不知道时间复杂度怎么推导、不知道哈希冲突怎么办、不知道TCP为什么三次握手笔试照样会露出破绽。反过来把数据结构、操作系统、网络、数据库这些核心基础打牢再配合一定量的代码训练无论题目怎么包装你都能找到切入点。最后分享一个我自己的习惯每次做完一套笔试题不管结果好坏我都会把错题和卡壳的题整理到一份笔记里标注它考察的底层知识点而不是只记答案。校招笔试从来不是为了难倒谁它只是用一套标准化的方式帮你和公司双向确认你是否具备成为一个研发工程师的基本盘。这个基本盘无论十年前还是现在都一样。