2026年软件开发工程师校招考试题

2026年软件开发工程师校招考试题一、编程语言与基础算法（共5题，每题10分，总计50分）1.题目（10分）：编写一个Python函数，实现将任意进制数（2-16进制）转换为十进制数。输入参数为字符串形式的原数字和其进制数（整数），输出为十进制整数。例如：`convert_to_decimal("1A",16)`应返回`26`，`convert_to_decimal("101",2)`应返回`5`。2.题目（10分）：给定一个字符串`s`，请编写代码实现删除字符串中的所有重复字符（重复按首次出现顺序保留），并返回新字符串。例如：`remove_duplicates("abaccdeff")`应返回`"abcdef"`。3.题目（10分）：实现快速排序算法（QuickSort），要求使用递归方式编写，并说明其时间复杂度。输入为一个无序整数数组，输出为排序后的数组。4.题目（10分）：编写一个函数，计算二叉树的最大深度。二叉树用列表表示，例如：tree=[3,9,20,None,None,15,7]表示为：3/\920/\157函数应返回`3`。5.题目（10分）：实现一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。缓存容量为`capacity`，使用哈希表和双向链表结合实现，要求说明核心思路。二、数据结构与数据库（共4题，每题12分，总计48分）1.题目（12分）：解释什么是“平衡二叉树”（如AVL树或红黑树），并说明其为什么能保证最坏情况下查找、插入、删除的时间复杂度为O(logn)。2.题目（12分）：设计一个数据库表结构，用于存储“用户-商品购买记录”，要求支持以下查询：-查询用户A购买过的所有商品；-查询购买过商品X的所有用户；-查询商品X的总购买次数。说明至少两种索引设计思路。3.题目（12分）：给定一个无向图（用邻接矩阵表示），编写代码实现深度优先搜索（DFS），并输出遍历顺序。例如：graph=[[0,1,0,0],[1,0,1,1],[0,1,0,1],[0,1,1,0]]DFS遍历顺序为`[0,1,3,2]`。4.题目（12分）：解释SQL中的“事务”（Transaction）概念，并说明ACID特性分别代表什么。举一个需要使用事务的业务场景（如银行转账）。三、系统设计（共3题，每题15分，总计45分）1.题目（15分）：设计一个简单的微博“关注-粉丝”系统，要求：-用户可以关注/取关其他用户；-每个用户可以发布动态；-动态发布后，关注该用户的粉丝可以实时看到（简化版，不考虑实时推送）。说明核心数据结构和可能的数据库表设计。2.题目（15分）：设计一个“短链接”服务（如tinyurl），要求：-输入长URL，生成短URL；-输入短URL，解析为长URL；-高并发场景下保证唯一性和快速响应。说明主要技术方案（如使用hash算法或分布式ID生成器）。3.题目（15分）：设计一个“秒杀”活动系统，要求：-用户可以提前加购商品；-活动开始后，用户点击购买时需秒杀成功（即库存瞬间减1）；-防止超卖和恶意刷单。说明核心流程和可能的优化方案（如使用分布式锁或Redis）。四、综合编程（共2题，每题25分，总计50分）1.题目（25分）：编写一个函数，实现“文本编辑器”的基本功能，支持以下操作：-`insert(text)`：在光标位置插入文本；-`delete(n)`：删除光标左边的n个字符；-`move_left(n)`：光标向左移动n个位置；-`move_right(n)`：光标向右移动n个位置。要求用栈或链表实现，并考虑边界情况（如光标移动超出范围）。2.题目（25分）：实现一个简单的“消息队列”服务，要求：-支持生产者（Producer）发送消息；-支持消费者（Consumer）接收消息；-消息先进先出（FIFO）；-允许消息持久化（如写入文件或数据库）。说明核心数据结构和可能的实现方式（如使用RabbitMQ原理简化版）。答案与解析一、编程语言与基础算法1.答案：pythondefconvert_to_decimal(num_str,base):ifnot2<=base<=16:raiseValueError("Basemustbebetween2and16")digits="0123456789ABCDEF"result=0fori,charinenumerate(num_str[::-1]):value=digits.index(char.upper())ifvalue>=base:raiseValueError(f"Invaliddigit{char}forbase{base}")result+=value(basei)returnresult解析：-从字符串末尾开始遍历，将每个字符转换为对应数值（`digits`表）；-用`basei`计算权重并累加；-检查字符是否合法（如`'G'`在16进制中无效）；2.答案：pythondefremove_duplicates(s):seen=set()result=[]forcharins:ifcharnotinseen:seen.add(char)result.append(char)return''.join(result)解析：-使用`set`记录已出现字符；-遍历字符串，仅添加未出现字符；-时间复杂度O(n)，空间复杂度O(n)。3.答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：-选择基准值（`pivot`）；-分区为`<pivot`、`==pivot`、`>pivot`；-递归排序左右子数组；-时间复杂度平均O(nlogn)，最坏O(n²)。4.答案：pythondefmax_depth(tree):ifnottree:return0return1+max(max_depth(tree[1]),max_depth(tree[2]))iftree[1]ortree[2]else1解析：-递归计算左右子树深度；-根节点深度为1；-时间复杂度O(n)，n为节点数。5.答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key):ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:iflen(self.cache)==self.capacity:lru=self.tail.prevdelself.cache[lru.key]self._remove_node(lru)new_node=self.Node(key,value)self.cache[key]=new_nodeself._add_node(new_node)解析：-使用`双向链表+哈希表`实现；-`get`时移动节点到头部；-`put`时先删除最久未使用节点（尾节点），再添加新节点；-时间复杂度O(1)。二、数据结构与数据库1.答案：平衡二叉树通过旋转操作（如AVL树的左旋/右旋）保证任意节点的左右子树高度差不超过1，从而将树的高度控制在logn，确保操作复杂度O(logn)。2.答案：表结构设计：sqlCREATETABLEorders(idINTAUTO_INCREMENTPRIMARYKEY,user_idINT,product_idINT,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(id),FOREIGNKEY(product_id)REFERENCESproducts(id));索引设计：-主键索引`id`；-聚合索引`(user_id,product_id)`支持多条件查询；-单独索引`product_id`优化“查询购买过商品X的用户”。3.答案：pythondefdfs(graph,node,visited=None):ifvisitedisNone:visited=set()visited.add(node)print(node,end='')forneighborinrange(len(graph)):ifgraph[node][neighbor]==1andneighbornotinvisited:dfs(graph,neighbor,visited)解析：-使用递归或栈实现；-标记已访问节点避免重复；-时间复杂度O(V+E)。4.答案：事务是数据库执行操作的一个逻辑单元，需满足ACID特性：-原子性（Atomicity）：事务要么全部完成，要么全部不做；-一致性（Consistency）：事务执行后数据库从一种状态变为另一种一致状态；-隔离性（Isolation）：并发事务互不干扰；-持久性（Durability）：事务提交后结果永久保存。银行转账场景中，扣款和收款必须同时成功或失败。三、系统设计1.答案：数据结构：-用户表：`user_id`,`name`,`follows`（存储关注用户列表）；-动态表：`post_id`,`user_id`,`content`,`timestamp`;-粉丝表：`user_id`,`followers`（存储粉丝列表）；核心逻辑：-关注/取关操作更新`follows`和`followers`；-发布动态时写入`post_id`和`user_id`，粉丝通过`user_id`订阅动态。2.答案：技术方案：-使用`hash函数`（如SHA1）将长URL映射为短ID；-短ID作为键，长URL作为值存储在Redis中；-反向解析时直接查Redis。优化：-分布式ID生成器（如Twitter的base62编码）；-负载均衡多副本部署。3.答案：核心流程：1.用户加购时，使用分布式锁（如Redis）或数据库乐观锁锁定库存；2.检查库存是否>0，是则减1并下单，否则返回失败；优化：-队列限流：将请求放入队列，按顺序处理；-预减库存+异步下单：避免超卖但可能存在数据不一致风险。四、综合编程1.答案：pythonclassTextEditor:def__init__(self):self.cursor=0self.text=[]definsert(self,chars):self.text.insert(self.cursor,chars)self.cursor+=len(chars)defdelete(self,n):delete_count=min(n,self.cursor)self.text=self.text[:self.cursor-delete_count]+self.text[self.cursor:]self.cursor-=delete_countdefmove_left(self,n):self.cursor=max(0