2026年联想集团软件工程师面试题集

2026年联想集团软件工程师面试题集一、编程能力测试（共5题，每题20分，总分100分）题目1（20分）：数组旋转问题问题描述：给定一个数组`nums`和一个整数`k`，将数组中的元素向右旋转`k`步。例如，输入`nums=[1,2,3,4,5]`,`k=2`，输出`[4,5,1,2,3]`。要求：1.不使用额外数组空间，原地旋转数组2.时间复杂度O(n)，空间复杂度O(1)3.写出完整Java/Python实现代码题目2（20分）：链表合并问题问题描述：合并两个排序链表，合并后的链表也应该是排序的。例如，输入`l1=[1,2,4]`,`l2=[1,3,4]`，输出`[1,1,2,3,4,4]`。要求：1.实现递归和非递归两种解法2.考虑边界情况（空链表、不同长度的链表）3.写出完整代码及复杂度分析题目3（20分）：字符串匹配问题问题描述：实现KMP（Knuth-Morris-Pratt）字符串匹配算法的核心函数`kmpTable`，用于构建部分匹配表。给定模式串`pattern`，返回部分匹配表。要求：1.解释KMP算法原理2.实现部分匹配表构建函数3.分析时间复杂度题目4（20分）：二叉树遍历问题问题描述：给定一个二叉树，返回其层序遍历（按从上到下、从左到右的顺序）。例如：3/\920/\157输出：`[[3],[9,20],[15,7]]`要求：1.使用队列实现BFS（广度优先搜索）2.使用递归实现DFS（深度优先搜索）3.对比两种方法的优缺点题目5（20分）：动态规划问题问题描述：给定一个数组`nums`，返回其中连续子数组的最大和。例如，输入`nums=[-2,1,-3,4,-1,2,1,-5,4]`，输出`6`（因为`[4,-1,2,1]`的和最大）。要求：1.实现动态规划解法2.解释贪心策略3.写出完整代码及复杂度分析二、系统设计能力测试（共4题，每题25分，总分100分）题目1（25分）：短链接系统设计问题描述：设计一个短链接系统（如tinyURL），要求：1.将长链接转换为短链接2.从短链接解析出原始长链接3.支持高并发访问要求：1.描述系统架构2.解释核心算法（如Base62编码）3.说明高可用、高并发解决方案题目2（25分）：实时消息推送系统设计问题描述：设计一个实时消息推送系统（如微信通知），要求：1.支持多用户实时接收消息2.具备消息持久化机制3.处理消息失败重试逻辑要求：1.描述系统组件（如消息队列、缓存）2.说明数据一致性保证方法3.分析QPS和消息延迟问题题目3（25分）：分布式存储系统设计问题描述：设计一个类似AWSS3的分布式存储系统，要求：1.支持海量文件存储2.具备文件分片和冗余机制3.实现文件访问权限控制要求：1.描述系统架构（如MD五分片算法）2.说明数据一致性和可用性保障3.分析数据热点问题解决方案题目4（25分）：秒杀系统设计问题描述：设计一个高并发秒杀系统（如双十一商品抢购），要求：1.防止超卖和恶意下单2.支持秒杀流量削峰3.保证交易一致性要求：1.描述系统架构（如分布式锁）2.说明库存扣减和订单生成逻辑3.分析系统瓶颈和优化方案三、算法与数据结构（共5题，每题15分，总分75分）题目1（15分）：LRU缓存算法问题描述：实现LRU（LeastRecentlyUsed）缓存算法，支持get和put操作。要求：1.使用链表和哈希表实现2.解释数据结构选择原因3.分析时间复杂度题目2（15分）：图算法问题问题描述：给定一个无向图，判断它是否是二分图（BipartiteGraph）。二分图是指可以将顶点分成两个集合，使得每条边连接的两个顶点属于不同集合。要求：1.实现BFS或DFS解法2.说明算法原理3.分析时间复杂度题目3（15分）：堆排序问题问题描述：实现堆排序算法，并用给定的数组`[12,11,13,5,6,7]`进行排序。要求：1.实现建堆和堆调整函数2.解释堆排序工作原理3.分析时间复杂度题目4（15分）：字符串处理问题问题描述：找到字符串中最长回文子串。例如，输入`s="babad"`，可以输出`"bab"`或`"aba"`。要求：1.实现动态规划解法2.解释中心扩展法原理3.分析时间复杂度题目5（15分）：树的最大深度问题问题描述：给定一个二叉树，返回其最大深度。例如：3/\920/\157最大深度为3。要求：1.实现递归或迭代解法2.解释算法原理3.分析时间复杂度答案与解析编程能力测试答案题目1答案（Java）javapublicclassSolution{publicvoidrotate(int[]nums,intk){if(nums==null||nums.length<=1)return;k=k%nums.length;reverse(nums,0,nums.length-1);reverse(nums,0,k-1);reverse(nums,k,nums.length-1);}privatevoidreverse(int[]nums,intstart,intend){while(start<end){inttemp=nums[start];nums[start]=nums[end];nums[end]=temp;start++;end--;}}}解析：通过三次反转实现数组旋转：1.整个数组反转；2.前k个元素反转；3.剩余元素反转。时间复杂度O(n)，空间复杂度O(1)。题目2答案（Python）python递归解法classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextclassSolution:defmergeTwoLists(self,l1,l2):ifnotl1:returnl2ifnotl2:returnl1ifl1.val<l2.val:l1.next=self.mergeTwoLists(l1.next,l2)returnl1else:l2.next=self.mergeTwoLists(l1,l2.next)returnl2非递归解法defmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next解析：递归解法通过比较节点值并递归合并子链表；非递归解法使用dummy节点遍历合并。时间复杂度O(n)，空间复杂度递归为O(logn)，迭代为O(1)。题目3答案（Java）javapublicint[]kmpTable(Stringpattern){int[]table=newint[pattern.length()];intpos=2;intcnd=0;table[0]=0;table[1]=0;while(pos<pattern.length()){if(pattern.charAt(pos-1)==pattern.charAt(cnd)){table[pos]=cnd+1;pos++;cnd++;}elseif(cnd>0){cnd=table[cnd];}else{table[pos]=0;pos++;}}returntable;}解析：KMP算法通过构建部分匹配表避免重复比较，时间复杂度O(m)，空间复杂度O(m)。题目4答案（Python）pythonBFS实现deflevelOrder(root):ifnotroot:return[]result,queue=[],[root]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresultDFS实现deflevelOrderDFS(root):ifnotroot:return[]result,stack=[],[(root,0)]whilestack:node,depth=stack.pop()ifdepth==len(result):result.append([])result[depth].append(node.val)ifnode.left:stack.append((node.left,depth+1))ifnode.right:stack.append((node.right,depth+1))returnresult解析：BFS使用队列实现层序遍历，DFS使用栈实现。BFS更直观适合层序需求。题目5答案（Java）javapublicintmaxSubArray(int[]nums){if(nums==null||nums.length==0)return0;intmaxSum=nums[0];intcurrentSum=nums[0];for(inti=1;i<nums.length;i++){currentSum=Math.max(nums[i],currentSum+nums[i]);maxSum=Math.max(maxSum,currentSum);}returnmaxSum;}解析：动态规划解法使用两个变量记录当前最大和全局最大，时间复杂度O(n)，空间复杂度O(1)。系统设计能力测试答案题目1答案系统架构：1.前端服务：接收长链接请求，生成短链接2.缓存层：存储热点短链接（Redis）3.基础设施：分布式存储（HDFS）+数据库（MySQL）4.接入层：负载均衡（Nginx）核心算法：-Base62编码：将数字转换为62进制字符-哈希算法：如SHA-256保证唯一性高可用方案：-负载均衡（多副本）-读写分离-异地多活题目2答案系统组件：1.消息队列（Kafka/RabbitMQ）2.缓存层（Redis）3.推送服务（WebSocket/Server-SentEvents）4.数据库（存储消息记录）数据一致性：-分布式锁（Redisson）-2PC事务QPS处理：-消息分片-流量控制（令牌桶算法）题目3答案系统架构：1.分片服务：将数据哈希分片2.节点集群：存储分片数据3.元数据管理：记录分片位置4.读写代理：处理客户端请求MD五分片算法：-将文件哈希值映射到5个分片-每个分片存储不同部分数据一致性：-多副本机制-Paxos/Raft一致性协议题目4答案系统架构：1.接入层：限流（令牌桶）2.库存服务：分布式锁（Redis）3.订单服务：事务补偿4.支付服务：异步处理防超卖策略：-库存预扣减-分布式锁-异步下单系统瓶颈：-库存扣减锁竞争-订单生成延迟优化方案：-熔断降级-热点库存预加载算法与数据结构答案题目1答案pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：使用OrderedDict实现LRU，get时移动元素，put时检查容量。题目2答案pythondefisBipartite(graph):color={}defdfs(node,c):ifnodeincolor:returncolor[node]==ccolor[node]=creturnall(dfs(nei,notc)forneiingraph[node])fornodeingraph:ifnodenotincolor:ifnotdfs(node,True):returnFalsereturnTrue解析：BFS/DFS着色问题，交替颜色判断二分性。题目3答案javapublicvoidheapSort(int[]arr){//建堆for(inti=arr.length/2-1;i>=0;i--){heapify(arr,arr.length,i);}//排序for(inti=arr.length-1;i>0;i--){swap(arr,0,i);heapify(arr,i,0);}}privatevoidheapify(int[]arr,intn,inti){intlargest=i;intleft=2i+1;intright=2i+2;if(left<n&&arr[left]>arr[largest])largest=left;if(right<n&&arr[right]>arr[largest])largest=right;if(largest!=i){swap(arr,i,largest);heapify(arr,n,largest);}}解析：堆排序通过建最大堆实现，时间复杂度O(nlogn)。题目4答案pythondeflongestPalindrome(s:str)->str:ifnots:return""start,end=0,0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,