2026年技术部软件工程师面试题及答案

2026年技术部软件工程师面试题及答案一、编程题（共3题，每题20分，总分60分）1.题目（20分）：编写一个函数，实现将任意长度为N的链表进行反转。链表节点定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next要求：-时间复杂度O(N)，空间复杂度O(1)。-示例输入：`1->2->3->4->5`，输出：`5->4->3->2->1`。2.题目（20分）：实现一个LRU（LeastRecentlyUsed）缓存机制，支持以下操作：-`get(key)`:获取键对应的值，若不存在返回-1。-`put(key,value)`:插入或更新键值对，当缓存容量满时，删除最久未使用的项。要求：-使用哈希表和双向链表实现，支持O(1)时间复杂度。-示例：-`put(1,1)`→缓存：{1:1}-`put(2,2)`→缓存：{1:1,2:2}-`get(1)`→返回1-`put(3,3)`→缓存容量满，删除键1，缓存：{2:2,3:3}-`get(2)`→返回23.题目（20分）：给定一个包含重复元素的数组，返回所有不重复的全排列。要求：-使用回溯法实现，避免重复排列。-示例输入：`[1,1,2]`，输出：`[1,1,2],[1,2,1],[2,1,1]`。二、算法题（共4题，每题15分，总分60分）1.题目（15分）：给定一个非空字符串，统计其中字母的频率（区分大小写），并返回按频率降序排列的字符串。示例输入：`"tree"`，输出：`"eetr"`（e:2,t:1,r:1）。2.题目（15分）：实现二叉树的层序遍历（BFS），返回结果为列表形式。示例输入：3/\920/\157输出：`[[3],[9,20],[15,7]]`。3.题目（15分）：给定两个字符串，判断是否可以通过插入少量字符使其中一个字符串变为另一个字符串的子序列。示例输入：`s="abc"`,`t="ahbgdc"`，输出：`True`（插入`h`和`g`）。4.题目（15分）：实现快速排序算法，要求不使用递归，改用迭代方式实现。三、系统设计题（共2题，每题25分，总分50分）1.题目（25分）：设计一个高并发的短链接服务（如TinyURL），要求：-支持高并发访问（QPS>10000）。-支持自定义短链接前缀（如`/abc`）。-支持链路状态监控（如点击统计）。2.题目（25分）：设计一个分布式任务队列（如Kafka），要求：-支持消息持久化（不丢失）。-支持消息重试机制（失败任务自动重发）。-支持消息分片和负载均衡。四、数据库题（共2题，每题20分，总分40分）1.题目（20分）：设计一个电商订单表，要求：-支持高并发写入（每秒数千笔订单）。-支持订单状态实时查询（如待支付、已发货）。-支持按时间范围和用户ID统计订单数量。2.题目（20分）：解释MySQL中的事务隔离级别（读未提交、读已提交、可重复读、串行化），并说明脏读、不可重复读、幻读的区别。五、综合题（共2题，每题20分，总分40分）1.题目（20分）：某电商平台需要实时计算用户购买行为的热度指数（如“爆款”商品），要求：-数据源包括用户点击、加购、下单等行为。-热度指数需考虑时间衰减（如近1小时权重更高）。-支持实时更新和异步计算。2.题目（20分）：设计一个分布式爬虫系统，要求：-支持URL去重（使用布隆过滤器）。-支持多线程/多进程并发抓取。-支持反爬虫策略应对（如验证码识别）。答案与解析一、编程题答案与解析1.链表反转（20分）：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.next#暂存下一个节点current.next=prev#反转指针prev=current#移动prev和currentcurrent=next_nodereturnprev解析：-使用迭代法，通过`prev`和`current`两个指针实现。每次将当前节点的`next`指向前一个节点，并移动指针。-时间复杂度O(N)，空间复杂度O(1)。2.LRU缓存（20分）：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=ListNode(0,0),ListNode(0,0)self.head.next,self.tail.prev=self.tail,self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valreturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=ListNode(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node:ListNode)->None:delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node:ListNode)->None:node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：-使用双向链表+哈希表实现。链表头部为最近使用，尾部为最久未使用。哈希表记录键值对，支持O(1)访问。-`get`操作将节点移动到链表头部，`put`操作先删除旧节点，再插入新节点并检查是否需要淘汰。3.全排列（20分）：pythondefpermuteUnique(nums):res=[]nums.sort()#排序去重used=[False]len(nums)defbacktrack(path):iflen(path)==len(nums):res.append(path[:])returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path)path.pop()used[i]=Falsebacktrack([])returnres解析：-使用回溯法，通过`used`数组记录已使用节点，避免重复。-排序后跳过相同元素的前一个（若当前元素与前一元素相同且前一元素未使用），防止重复排列。二、算法题答案与解析1.字母频率统计（15分）：pythondeffrequencySort(s:str)->str:freq=[0]128forcins:freq[ord(c)]+=1chars=sorted(s,key=lambdax:(-freq[ord(x)],x))return''.join(chars)解析：-统计每个字符频率，然后按频率降序排列（频率相同按字母顺序）。-时间复杂度O(NlogN)，空间复杂度O(N)。2.二叉树层序遍历（15分）：pythonfromcollectionsimportdequefromtypingimportList,OptionalclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevelOrder(root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]res,queue=[],deque([root])whilequeue:level=[]for_inrange(len(queue)):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres解析：-使用队列实现BFS，按层遍历节点。每层将节点值加入`level`，最后加入`res`。3.子序列判断（15分）：pythondefisSubsequence(s:str,t:str)->bool:m,n=len(s),len(t)i,j=0,0whilei<mandj<n:ifs[i]==t[j]:i+=1j+=1returni==m解析：-双指针法，`i`遍历`s`，`j`遍历`t`。若`s[i]==t[j]`，则`i`移动。最终判断`s`是否全部匹配。4.快速排序（迭代版）（15分）：pythondefquickSort(arr):stack=[(0,len(arr)-1)]whilestack:left,right=stack.pop()ifleft>=right:continuepivot=arr[right]i=left-1forjinrange(left,right):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[right]=arr[right],arr[i+1]stack.append((left,i))stack.append((i+2,right))returnarr解析：-使用栈模拟递归，避免递归调用栈。核心思想与递归版一致：分治法，选择基准值并分区。三、系统设计题答案与解析1.短链接服务（25分）：核心组件：-ID生成器：使用Snowflake算法生成唯一ID（含时间戳、机器ID、序列号）。-哈希映射：将ID映射到短链接（如`/a1b2c3`）。-缓存层：Redis缓存热点短链接，加速访问。-数据库：MySQL存储完整映射关系，支持查询和更新。-负载均衡：Nginx分发请求，支持水平扩展。伪代码：pythondefgenerate_short_url(long_url):id=snowflake_generator()hash_url=hash(id)#简化示例short_url=f"/{hash_url}"db.insert(id,long_url)redis.set(short_url,long_url,expire=3600)returnshort_url解析：-Snowflake算法保证ID唯一性，哈希映射快速查询。缓存层提升性能，数据库持久化数据。2.分布式任务队列（25分）：核心组件：-生产者：添加任务到Kafka分区（如`tasks`主题）。-消费者：按分区消费任务，失败重试（如RabbitMQ死信队列）。-消息存储：Kafka持久化消息，保证不丢失。-监控：Prometheus统计延迟、失败率。伪代码：pythondefadd_task(task):kafka_producer.send("tasks",task)解析：-Kafka支持分区和副本，保证高可用。死信队列处理失败任务，监控组件实时反馈系统状态。四、数据库题答案与解析1.电商订单表设计（20分）：sqlCREATETABLEorders(idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINT,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,statusENUM('pending','paid','shipped','completed'),amountDECIMAL(10,2),INDEXidx_user_time(user_id,order_time));解析：-使用`BIGINT`存储ID和用户ID，避免溢出。`TIMESTAMP`记录时间，`ENUM`限制状态。索引优化查询。2.事务隔离级别（20分）：-读未提交：可能脏读（B读取A未提交的数据，A回滚）。-读已提交：避免脏读，但不可重复读（B读取A已提交的数据，A再次修改）。-可重复读：避免脏读和不可重复读，但幻读（B扫描A已提交的新行）。-串行化：完全隔离，但性能最低。解析：-MySQL默认隔离级别为可重复读，可通过`SETTRANSACTIONISOLATIONLEVEL`调整。五、综合题答案与解析1.热度指数计算（20分）：核心逻辑：-用户行为加权：点击0.1+加购0.3+下单1.0。-时间衰减：`weight=deca