2025年开发工程师校招试题及答案

2025年开发工程师校招试题及答案一、单项选择题（每题2分，共20分）1.以下关于红黑树的描述中，错误的是（）A.每个节点要么是红色，要么是黑色B.根节点和叶子节点（NIL）是黑色C.红色节点的子节点可以是红色D.从任一节点到其每个叶子的所有路径包含相同数量的黑色节点答案：C解析：红黑树的性质要求红色节点的两个子节点必须是黑色（避免连续红节点），因此C错误。2.若某二叉树的前序遍历序列为ABCDE，中序遍历序列为BADCE，则后序遍历序列为（）A.BDECAB.BEDCAC.BDAECD.BDEAC答案：A解析：前序根为A，中序中A左侧B为左子树，右侧DCE为右子树。左子树前序B→中序B，故左子树后序为B；右子树前序CDE→中序DCE，根为C，左子树D，右子树E，后序为DEC。整体后序为B+DEC+A→BDECA。3.以下关于TCP三次握手的描述，正确的是（）A.第一次握手客户端发送SYN=1，ACK=1B.第二次握手服务器发送SYN=1，ACK=1，确认号为客户端初始序列号+1C.第三次握手客户端发送SYN=1，ACK=1，序列号为服务器初始序列号+1D.三次握手完成后，客户端进入ESTABLISHED状态，服务器仍处于SYN_RCVD状态答案：B解析：第一次握手客户端发送SYN=1，ACK=0（A错误）；第二次握手服务器回复SYN=1，ACK=1，确认号为客户端序列号+1（B正确）；第三次握手客户端发送ACK=1（SYN=0），序列号为客户端初始序列号+1（C错误）；三次握手完成后双方均进入ESTABLISHED状态（D错误）。4.下列关于数据库索引的说法，错误的是（）A.B+树索引适合范围查询，而哈希索引不适合B.聚集索引决定了数据在磁盘上的存储顺序C.联合索引的顺序会影响查询效率，应将高选择性字段放在前面D.索引越多，写操作（INSERT/UPDATE/DELETE）的性能越高答案：D解析：索引越多，写操作时需要维护更多索引结构，性能会下降（D错误）。5.若一个进程的虚拟地址空间为4GB，页大小为4KB，则页表项的数量为（）A.1MB.1KC.1GD.4M答案：A解析：虚拟地址空间大小4GB=4×2³⁰B，页大小4KB=4×2¹⁰B，页表项数量=4×2³⁰/4×2¹⁰=2²⁰=1M（A正确）。6.以下Python代码的输出结果是（）```pythondeffunc(a):a=a+[5]x=[1,2,3]func(x)print(len(x))```A.3B.4C.5D.报错答案：A解析：函数func中a是x的引用，但a=a+[5]会生成新列表，原x未被修改，故x长度仍为3（A正确）。7.以下关于Java垃圾回收的描述，错误的是（）A.新生代通常采用复制算法B.老年代通常采用标记-整理算法C.可达性分析中，静态变量不会被作为GCRootsD.System.gc()会建议JVM执行垃圾回收，但不一定立即执行答案：C解析：静态变量属于类，存储在方法区，会被作为GCRoots（C错误）。8.若要对数组[3,1,4,1,5,9,2,6]进行快速排序，选择首元素为基准，第一次划分后的数组是（）A.[1,1,2,3,5,9,4,6]B.[1,1,2,3,4,9,5,6]C.[2,1,4,1,5,9,3,6]D.[1,3,4,1,5,9,2,6]答案：A解析：首元素3为基准，左指针找大于3的元素（4），右指针找小于3的元素（2→1→1），交换4和1→数组变为[3,1,1,2,5,9,4,6]；继续移动指针，左指针到5（>3），右指针到2（≤3），交换5和2→[3,1,1,2,2,9,4,6]？不，正确步骤应为：初始数组[3,1,4,1,5,9,2,6]，左指针i=0（基准位置），右指针j=7。j左移找<3的元素，找到2（索引6）；i右移找>3的元素，找到4（索引2）。交换索引2和6→数组变为[3,1,2,1,5,9,4,6]。继续i右移（索引3，值1≤3），i=4（值5>3）；j左移（索引5，值9>3；索引4，值5>3；索引3，值1≤3），此时i=4>j=3，交换基准（索引0）和j=3→数组变为[1,1,2,3,5,9,4,6]（A正确）。9.以下关于微服务架构的描述，正确的是（）A.微服务必须使用相同的编程语言和技术栈B.服务间通信应尽可能使用共享数据库C.每个微服务应拥有独立的数据库，避免共享状态D.微服务架构一定比单体架构性能更优答案：C解析：微服务强调松耦合，每个服务独立数据库（C正确），其他选项均违背微服务设计原则。10.以下哪种情况不会导致死锁？（）A.进程A持有资源1，请求资源2；进程B持有资源2，请求资源1B.进程A持有资源1，请求资源2；进程B持有资源2，请求资源3；进程C持有资源3，请求资源1C.进程A请求资源1，进程B请求资源1D.系统采用非抢占式分配策略，且资源分配图存在环答案：C解析：死锁的必要条件包括互斥、不可抢占、请求和保持、循环等待。C中资源1被两个进程请求，但未发生“保持并请求”，不会导致死锁（C正确）。二、编程题（共50分）11.最短回文子串计数（15分）题目：给定一个仅由小写字母组成的字符串s，计算s的所有回文子串中，长度最短的子串数量。（注：单个字符视为长度为1的回文子串）示例：输入："abc"输出：3解释：所有回文子串为"a","b","c"，长度均为1，共3个。输入："aaa"输出：3解释：最短回文子串为长度1的"a"（3个），长度2的"aa"（2个），长度3的"aaa"（1个），故最短数量为3。要求：时间复杂度O(n²)以内。解题思路：最短回文子串长度为1时，数量为字符串长度（每个字符自身）。若存在长度为2的回文子串（即相邻两字符相同），则最短长度仍为1（因为1<2），故只需统计长度为1的子串数量。若不存在长度为1的回文子串（不可能，因每个字符自身是回文），所以最短长度始终为1，数量为n。代码（Python）：```pythondefcount_shortest_palindromes(s):所有长度为1的子串都是回文，数量为字符串长度returnlen(s)测试用例print(count_shortest_palindromes("abc"))3print(count_shortest_palindromes("aaa"))3```12.二叉树中的路径和（20分）题目：给定二叉树的根节点root和一个整数target，计算该二叉树中路径和等于target的路径总数。路径不需要从根开始，也不需要在叶子结束，但路径必须至少包含一个节点，且路径上的节点是父子连接的。示例：输入：root=[10,5,-3,3,2,null,11,3,-2,null,1],target=8输出：3解释：路径为5→3（5+3=8），5→2→1（5+2+1=8），-3→11（-3+11=8）。要求：使用递归或迭代方法，时间复杂度O(n²)以内。解题思路：双递归法：外层递归遍历每个节点作为路径起点，内层递归计算以该节点为起点的路径和是否等于target。优化方法：使用前缀和（哈希表记录路径前缀和出现次数），时间复杂度O(n)。代码（Java，前缀和优化）：```javaimportjava.util.HashMap;importjava.util.Map;classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicclassPathSum{Map<Long,Integer>prefixSum=newHashMap<>();inttarget;publicintpathSum(TreeNoderoot,inttargetSum){target=targetSum;prefixSum.put(0L,1);//初始前缀和0出现1次returndfs(root,0);}privateintdfs(TreeNodenode,longcurrentSum){if(node==null)return0;currentSum+=node.val;intres=prefixSum.getOrDefault(currentSumtarget,0);//当前路径和-目标=前缀和存在的次数prefixSum.put(currentSum,prefixSum.getOrDefault(currentSum,0)+1);//记录当前前缀和res+=dfs(node.left,currentSum);res+=dfs(node.right,currentSum);prefixSum.put(currentSum,prefixSum.get(currentSum)1);//回溯，删除当前前缀和returnres;}}```13.任务调度优化（15分）题目：给定一个任务列表tasks，每个任务有开始时间start和结束时间end（start<end），同一时间只能执行一个任务。要求选择尽可能多的任务，使得任务之间不重叠。若有多个最优解，选择结束时间最早的组合。示例：输入：[[1,3],[2,4],[3,5],[4,6]]输出：2解释：选择[1,3]和[3,5]，或[1,3]和[4,6]，但前者结束时间更早，故数量为2。要求：时间复杂度O(nlogn)。解题思路：贪心算法：按结束时间排序，每次选择当前可选的最早结束的任务，以留出更多时间给后续任务。代码（C++）：```cppinclude<vector>include<algorithm>usingnamespacestd;intmaxTasks(vector<vector<int>>&tasks){if(tasks.empty())return0;//按结束时间升序排序sort(tasks.begin(),tasks.end(),[](constvector<int>&a,constvector<int>&b){returna[1]<b[1];});intcount=1;intlastEnd=tasks[0][1];for(inti=1;i<tasks.size();++i){if(tasks[i][0]>=lastEnd){count++;lastEnd=tasks[i][1];}}returncount;}//测试用例intmain(){vector<vector<int>>tasks={{1,3},{2,4},{3,5},{4,6}};cout<<maxTasks(tasks)<<endl;//输出2return0;}```三、系统设计题（20分）题目：设计一个支持高并发的短链接服务（如将/longpath转换为/aB3d），要求：1.支持百万级/秒的请求量；2.短链接需全局唯一；3.允许用户自定义短码（如指定短码为"mycode"）；4.短链接有过期时间（默认30天）。请从以下维度描述设计方案：核心模块及功能；关键技术选型及原因；如何保证短码全局唯一；如何处理高并发下的读写性能；如何实现过期自动清理。解答：1.核心模块及功能短码生成模块：处理随机短码生成和自定义短码校验；存储模块：存储原始URL、短码、过期时间等信息；路由跳转模块：根据短码查询原始URL并跳转；监控与运维模块：统计访问量、监控服务状态、自动清理过期数据。2.关键技术选型及原因短码生成：随机短码：使用Base62编码（0-9a-zA-Z，62个字符），6位短码可生成62⁶≈568亿个唯一值，满足长期需求；自定义短码：校验是否已存在（通过缓存或数据库唯一索引），存在则返回错误。存储：主存储：Redis（内存数据库）+MySQL（持久化）。Redis存储高频访问的短码映射（设置过期时间），MySQL存储全量数据（主键为短码，唯一索引）；分布式存储：若数据量超单库容量，采用分片（如按短码哈希取模分片）。高并发处理：负载均衡：Nginx或K8sService进行流量分发；异步写入：用户生成短链接时，先返回结果，异步将数据写入MySQL（通过消息队列如Kafka缓冲）；读操作：优先从Redis查询，未命中则查MySQL并回种Redis。3.保证短码全局唯一的方法随机短码：使用雪花算法（Snowflake）生成唯一ID，再转换为Base62短码；生成后校验是否已存在（通过数据库唯一索引或Redis原子操作），冲突则重试（概率极低，6位短码冲突概率<1e-9）。自定义短码：写入时检查数据库/Redis是否已存在该短码，存在则返回“短码已被占用”错误。4.高并发下的读写性能优化写性能：异步化：用户请求先返回成功，通过消息队列（如RocketMQ）将写操作异步写入数据库，减少响应时间；批量写入：将消息队列中的数据按批次写入MySQL，减少数据库IO次数；分布式锁：防止同一短码被重复写入（仅当使用自定义短码时需要）。读性能：多级缓存：CDN缓存热门短码（如访问量TOP1000），Redis缓存最近访问的短码（设置LRU淘汰策略）；分片查询：MySQL按短码哈希分片，减少单库压力；连接池：使用数据库连接池（如HikariCP）复用连接，降低建立连接的开销。5.过期自动清理Redis：设置key的过期时间（默认30天），Redis自动删除过期数据；MySQL：定时任务（如XXL-Job）每天扫描过期数据，批量删除；或使用MySQL的事件调度器（EventScheduler）定期执行DELETE语句；异步清理：删除MySQL数据时，通过消息队列通知缓存层（如Redis）删除对应key（若存在），避免脏数据。四、综合题（10分）题目：假设你是某电商公司的开发工程师，需参与“双11”秒杀系统的设计。请描述你会关注哪些核心问题，并说明对应的解决方案。解答：核心问题及解决方案1.高并发流量冲击问题：秒杀开始时短时间内涌入百万级请求，超出服务器处理能力。解决方案：流量分层：前端做限流（如验证码、点击频率限制），网关层做Nginx限流（如限制IP每秒请求数），应用层做分布式限流（如Sentinel，限制QPS）；流量削峰：将请求放入消息队列（如Kafka），按系统处理能力匀速消费；静态资源优化：商品详情页、按钮等静态资源通过CDN分发，减少源站压力。2.库存超卖问题：多个请求同时扣减库存，导致库存变为负数。解决方案：数据库乐观锁：库存字段增加版本号，更新时检查版