2026年软件工程师中级技术面试模拟题

2026年软件工程师中级技术面试模拟题一、编程实现题（共3题，每题15分，总分45分）题目1（15分）：题目描述：设计一个函数，实现字符串的压缩。输入一个字符串，其中只包含大小写字母和数字，压缩规则如下：1.连续的相同字符，压缩为字符+连续出现的次数。例如，"aabcccaaa"压缩后为"a2b2c3a4"。2.压缩后的字符串长度如果小于原字符串长度，则返回原字符串。3.大小写字母和数字视为不同字符，不区分大小写。示例：-输入：`"aabcccaaa"`-输出：`"a2b2c3a4"`-输入：`"aabbcc"`-输出：`"aabbcc"`要求：-时间复杂度O(n)，空间复杂度O(1)。-请使用Python或Java实现该函数。答案与解析：pythondefcompress_string(s:str)->str:ifnots:return""compressed=[]count=1foriinrange(1,len(s)):ifs[i]==s[i-1]:count+=1else:compressed.append(s[i-1]+str(count))count=1compressed.append(s[-1]+str(count))#Appendthelastgroupcompressed_str=''.join(compressed)returncompressed_striflen(compressed_str)<len(s)elses解析：1.遍历字符串：使用单次遍历，记录当前字符的连续出现次数。2.压缩逻辑：当字符变化时，将前一个字符和计数追加到结果中，重置计数。3.最终判断：比较压缩后字符串与原字符串长度，选择更短的输出。4.复杂度分析：时间复杂度O(n)，空间复杂度O(1)（忽略输出字符串的空间）。题目2（15分）：题目描述：实现一个LRU（LeastRecentlyUsed）缓存。LRU缓存支持以下操作：-`get(key)`:获取键`key`对应的值，如果键不存在返回-1。-`put(key,value)`:插入或更新键值对。如果缓存已满，则删除最久未使用的键。要求：-使用双向链表和哈希表实现，确保`get`和`put`操作的时间复杂度为O(1)。-请使用Python或Java实现该数据结构。答案与解析：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}Createdummyheadandtailself.head=DLinkedNode()self.tail=DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node:DLinkedNode):Alwaysaddthenewnoderightafterheadnode.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:DLinkedNode):Removeanexistingnodefromthelinkedlistprev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:DLinkedNode):Movecertainnodeinbetweentotheheadself._remove_node(node)self._add_node(node)def_pop_tail(self)->DLinkedNode:Popthecurrenttailres=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1Movetheaccessednodetotheheadself._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:Popthetailtail=self._pop_tail()delself.cache[tail.key]else:Updatethevaluenode.value=valueself._move_to_head(node)解析：1.双向链表：维护最近使用顺序，头节点为最近使用，尾节点为最久未使用。2.哈希表：快速查找节点，O(1)时间复杂度。3.核心操作：-`get`：查找节点，移动到头部。-`put`：插入或更新节点，若超出容量则删除尾部节点。4.复杂度分析：`get`和`put`均为O(1)。题目3（15分）：题目描述：实现一个二叉树的深度优先遍历（前序、中序、后序）的迭代版本。不使用递归，使用栈实现。要求：-请分别实现前序、中序、后序遍历的迭代版本。-请使用Python或Java实现该函数。答案与解析：pythonDefinitionforabinarytreenode.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorder_iterative(root:TreeNode):ifnotroot:return[]stack,output=[root],[]whilestack:node=stack.pop()output.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnoutputdefinorder_iterative(root:TreeNode):stack,output,current=[],[],rootwhilestackorcurrent:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()output.append(current.val)current=current.rightreturnoutputdefpostorder_iterative(root:TreeNode):ifnotroot:return[]stack,output=[(root,False)],[]whilestack:node,visited=stack.pop()ifnode:ifvisited:output.append(node.val)else:stack.append((node,True))stack.append((node.right,False))stack.append((node.left,False))returnoutput解析：1.前序遍历：访问节点->右子树->左子树，使用栈实现时，先压右子树再压左子树。2.中序遍历：左子树->访问节点->右子树，使用栈时，访问节点后处理右子树。3.后序遍历：左子树->右子树->访问节点，可使用两个栈或单栈模拟（此处为单栈模拟）。4.复杂度分析：时间复杂度O(n)，空间复杂度O(n)。二、系统设计题（共2题，每题20分，总分40分）题目4（20分）：题目描述：设计一个高并发的短链接生成系统。系统需满足以下要求：1.输入任意长度的URL，输出固定长度的短链接（如6位随机字母数字组合）。2.短链接必须全局唯一，且可快速反向解析为原URL。3.支持高并发访问，每秒可处理数千次请求。4.系统应具备一定的容错性，如短链接被误删除时能自动恢复。要求：-说明核心设计思路，包括数据结构、分布式架构（可选）。-请简述高并发处理方案。答案与解析：核心设计思路：1.短链接生成：-使用Base62编码（a-z,A-Z,0-9），将长URL映射为6位短链接。-哈希函数：`hash(url)%62`，映射到Base62字符串。2.数据存储：-使用分布式缓存（如RedisCluster）存储URL与短链接的映射关系。-使用布隆过滤器快速判断短链接是否存在，减少数据库查询。3.反向解析：-通过缓存查询短链接对应的长URL。若缓存未命中，则查询数据库。4.容错性：-使用分布式事务或最终一致性方案（如Redis的Lua脚本）。-定期备份短链接映射关系，防止数据丢失。高并发处理方案：1.限流：使用令牌桶算法或漏桶算法控制请求速率。2.异步处理：使用消息队列（如Kafka）异步生成短链接，减轻前端压力。3.分布式架构：-多个服务节点共享缓存，使用负载均衡（如Nginx）分发请求。-数据库读写分离，使用分片（Sharding）扩展容量。复杂度分析：-时间复杂度：O(1)（缓存命中），O(logn)（缓存未命中）。-空间复杂度：O(n)（存储所有短链接映射）。题目5（20分）：题目描述：设计一个支持高并发的实时消息推送系统。系统需满足以下要求：1.支持多用户订阅主题（Topic），用户可实时接收主题更新。2.消息推送需保证至少一次传递（At-Least-OnceDelivery）。3.系统应具备削峰填谷能力，避免单次流量高峰压垮服务。4.支持消息重试机制，若推送失败可自动重试。要求：-说明核心设计思路，包括数据结构、分布式架构（可选）。-请简述消息重试和削峰填谷的方案。答案与解析：核心设计思路：1.数据结构：-使用发布-订阅模式，用户订阅Topic，Topic与消息队列（如Kafka）关联。-消息队列保证消息的顺序性和至少一次传递。2.分布式架构：-使用多个消费者副本处理消息，通过负载均衡（如RabbitMQCluster）扩展性能。-使用Redis缓存用户订阅关系，快速匹配消息与消费者。3.消息重试：-消息推送失败时，记录重试次数，超过阈值后移至死信队列（DLQ）。-使用定时任务（如CeleryBeat）重新推送死信消息。削峰填谷方案：1.限流：前端使用令牌桶算法限流，防止突发请求。2.消息队列：消息队列缓冲流量，平滑处理高峰。3.动态扩缩容：根据流量动态调整消费者数量，如Kubernetes自动伸缩。复杂度分析：-时间复杂度：O(1)（消息推送），O(n)（重试处理）。-空间复杂度：O(n)（存储所有订阅关系和消息）。三、数据库与SQL题（共2题，每题15分，总分30分）题目6（15分）：题目描述：给定一个电商订单表`orders`，字段如下：-`order_id`(INT,主键)-`user_id`(INT,用户ID)-`product_id`(INT,商品ID)-`quantity`(INT,购买数量)-`order_time`(DATETIME,订单时间)要求：-写出SQL查询：统计每个用户的总购买数量，只显示购买数量大于100的用户。-请优化查询性能，说明索引优化方案。答案与解析：sql--SQL查询SELECTuser_id,SUM(quantity)AStotal_quantityFROMordersGROUPBYuser_idHAVINGtotal_quantity>100;索引优化方案：1.索引字段：在`user_id`上创建索引，加速分组统计。sqlCREATEINDEXidx_user_idONorders(user_id);2.复合索引：若`order_time`或`product_id`常用于查询，可创建复合索引。sqlCREATEINDEXidx_user_id_timeONorders(user_id,order_time);复杂度分析：-时间复杂度：O(n)（未使用索引时），O(logn)（使用索引时）。-空间复杂度：O(1)（仅返回统计结果）。题目7（15分）：题目描述：给定两个表：-`employees`(员工表)：`emp_id`(INT,主键),`name`(VARCHAR),`department`(VARCHAR)-`salaries`(薪资表)：`emp_id`(INT,外键),`salary`(INT,薪资),`date`(DATE)要求：-写出SQL查询：查找每个部门平均薪资最高的员工姓名和部门，若平均薪资相同，则选择`emp_id`最小的员工。-请优化查询性能，说明索引优化方案。答案与解析：sql--SQL查询SELECT,e.departmentFROMemployeeseJOIN(SELECTdepartment,AVG(salary)ASavg_salary,RANK()OVER(PARTITIONBYdepartmentORDERBYAVG(salary)DESC,emp_idASC)ASrankFROMsalariesGROUPBYdepartment)sONe.department=s.departmentWHEREs.rank=1;索引优化方案：1.索引字段：在`employees(department)`上创建索引，加速表连接。sqlCREATEINDEXidx_departmentONemployees(department);2.复合索引：在`salaries`表上创建`(department,salary,emp_id)`索引，优化窗口函数计算。sqlCREATEINDEXidx_salary_empidONsalaries(department,salary,emp_id);复杂度分析：-时间复杂度：O(nlogn)（窗口函数计算），O(logn)（使用索引时）。-空间复杂度：O(1)（仅返回统计结果）。四、算法与数据结构题（共2题，每题15分，总分30分）题目8（15分）：题目描述：给定一个包含重复数字的数组`nums`，返回所有不重复的三元组`[a,b,c]`，满足`a+b+c=0`。要求：-请使用Python或Java实现该函数。-说明时间复杂度。答案与解析：pythondefthree_sum(nums):nums.sort()n=len(nums)res=[]foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums