2026年聯(lián)想集團軟件工程師面試題集一、編程能力測試（共5題，每題20分，總分100分）題目1（20分）：數(shù)組旋轉(zhuǎn)問題問題描述：給定一個數(shù)組`nums`和一個整數(shù)`k`，將數(shù)組中的元素向右旋轉(zhuǎn)`k`步。例如，輸入`nums=[1,2,3,4,5]`,`k=2`，輸出`[4,5,1,2,3]`。要求：1.不使用額外數(shù)組空間，原地旋轉(zhuǎn)數(shù)組2.時間復(fù)雜度O(n)，空間復(fù)雜度O(1)3.寫出完整Java/Python實現(xiàn)代碼題目2（20分）：鏈表合并問題問題描述：合并兩個排序鏈表，合并后的鏈表也應(yīng)該是排序的。例如，輸入`l1=[1,2,4]`,`l2=[1,3,4]`，輸出`[1,1,2,3,4,4]`。要求：1.實現(xiàn)遞歸和非遞歸兩種解法2.考慮邊界情況（空鏈表、不同長度的鏈表）3.寫出完整代碼及復(fù)雜度分析題目3（20分）：字符串匹配問題問題描述：實現(xiàn)KMP（Knuth-Morris-Pratt）字符串匹配算法的核心函數(shù)`kmpTable`，用于構(gòu)建部分匹配表。給定模式串`pattern`，返回部分匹配表。要求：1.解釋KMP算法原理2.實現(xiàn)部分匹配表構(gòu)建函數(shù)3.分析時間復(fù)雜度題目4（20分）：二叉樹遍歷問題問題描述：給定一個二叉樹，返回其層序遍歷（按從上到下、從左到右的順序）。例如：3/\920/\157輸出：`[[3],[9,20],[15,7]]`要求：1.使用隊列實現(xiàn)BFS（廣度優(yōu)先搜索）2.使用遞歸實現(xiàn)DFS（深度優(yōu)先搜索）3.對比兩種方法的優(yōu)缺點題目5（20分）：動態(tài)規(guī)劃問題問題描述：給定一個數(shù)組`nums`，返回其中連續(xù)子數(shù)組的最大和。例如，輸入`nums=[-2,1,-3,4,-1,2,1,-5,4]`，輸出`6`（因為`[4,-1,2,1]`的和最大）。要求：1.實現(xiàn)動態(tài)規(guī)劃解法2.解釋貪心策略3.寫出完整代碼及復(fù)雜度分析二、系統(tǒng)設(shè)計能力測試（共4題，每題25分，總分100分）題目1（25分）：短鏈接系統(tǒng)設(shè)計問題描述：設(shè)計一個短鏈接系統(tǒng)（如tinyURL），要求：1.將長鏈接轉(zhuǎn)換為短鏈接2.從短鏈接解析出原始長鏈接3.支持高并發(fā)訪問要求：1.描述系統(tǒng)架構(gòu)2.解釋核心算法（如Base62編碼）3.說明高可用、高并發(fā)解決方案題目2（25分）：實時消息推送系統(tǒng)設(shè)計問題描述：設(shè)計一個實時消息推送系統(tǒng)（如微信通知），要求：1.支持多用戶實時接收消息2.具備消息持久化機制3.處理消息失敗重試邏輯要求：1.描述系統(tǒng)組件（如消息隊列、緩存）2.說明數(shù)據(jù)一致性保證方法3.分析QPS和消息延遲問題題目3（25分）：分布式存儲系統(tǒng)設(shè)計問題描述：設(shè)計一個類似AWSS3的分布式存儲系統(tǒng)，要求：1.支持海量文件存儲2.具備文件分片和冗余機制3.實現(xiàn)文件訪問權(quán)限控制要求：1.描述系統(tǒng)架構(gòu)（如MD五分片算法）2.說明數(shù)據(jù)一致性和可用性保障3.分析數(shù)據(jù)熱點問題解決方案題目4（25分）：秒殺系統(tǒng)設(shè)計問題描述：設(shè)計一個高并發(fā)秒殺系統(tǒng)（如雙十一商品搶購），要求：1.防止超賣和惡意下單2.支持秒殺流量削峰3.保證交易一致性要求：1.描述系統(tǒng)架構(gòu)（如分布式鎖）2.說明庫存扣減和訂單生成邏輯3.分析系統(tǒng)瓶頸和優(yōu)化方案三、算法與數(shù)據(jù)結(jié)構(gòu)（共5題，每題15分，總分75分）題目1（15分）：LRU緩存算法問題描述：實現(xiàn)LRU（LeastRecentlyUsed）緩存算法，支持get和put操作。要求：1.使用鏈表和哈希表實現(xiàn)2.解釋數(shù)據(jù)結(jié)構(gòu)選擇原因3.分析時間復(fù)雜度題目2（15分）：圖算法問題問題描述：給定一個無向圖，判斷它是否是二分圖（BipartiteGraph）。二分圖是指可以將頂點分成兩個集合，使得每條邊連接的兩個頂點屬于不同集合。要求：1.實現(xiàn)BFS或DFS解法2.說明算法原理3.分析時間復(fù)雜度題目3（15分）：堆排序問題問題描述：實現(xiàn)堆排序算法，并用給定的數(shù)組`[12,11,13,5,6,7]`進行排序。要求：1.實現(xiàn)建堆和堆調(diào)整函數(shù)2.解釋堆排序工作原理3.分析時間復(fù)雜度題目4（15分）：字符串處理問題問題描述：找到字符串中最長回文子串。例如，輸入`s="babad"`，可以輸出`"bab"`或`"aba"`。要求：1.實現(xiàn)動態(tài)規(guī)劃解法2.解釋中心擴展法原理3.分析時間復(fù)雜度題目5（15分）：樹的最大深度問題問題描述：給定一個二叉樹，返回其最大深度。例如：3/\920/\157最大深度為3。要求：1.實現(xiàn)遞歸或迭代解法2.解釋算法原理3.分析時間復(fù)雜度答案與解析編程能力測試答案題目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--;}}}解析：通過三次反轉(zhuǎn)實現(xiàn)數(shù)組旋轉(zhuǎn)：1.整個數(shù)組反轉(zhuǎn)；2.前k個元素反轉(zhuǎn)；3.剩余元素反轉(zhuǎn)。時間復(fù)雜度O(n)，空間復(fù)雜度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解析：遞歸解法通過比較節(jié)點值并遞歸合并子鏈表；非遞歸解法使用dummy節(jié)點遍歷合并。時間復(fù)雜度O(n)，空間復(fù)雜度遞歸為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算法通過構(gòu)建部分匹配表避免重復(fù)比較，時間復(fù)雜度O(m)，空間復(fù)雜度O(m)。題目4答案（Python）pythonBFS實現(xiàn)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實現(xiàn)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使用隊列實現(xiàn)層序遍歷，DFS使用棧實現(xiàn)。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;}解析：動態(tài)規(guī)劃解法使用兩個變量記錄當前最大和全局最大，時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。系統(tǒng)設(shè)計能力測試答案題目1答案系統(tǒng)架構(gòu)：1.前端服務(wù)：接收長鏈接請求，生成短鏈接2.緩存層：存儲熱點短鏈接（Redis）3.基礎(chǔ)設(shè)施：分布式存儲（HDFS）+數(shù)據(jù)庫（MySQL）4.接入層：負載均衡（Nginx）核心算法：-Base62編碼：將數(shù)字轉(zhuǎn)換為62進制字符-哈希算法：如SHA-256保證唯一性高可用方案：-負載均衡（多副本）-讀寫分離-異地多活題目2答案系統(tǒng)組件：1.消息隊列（Kafka/RabbitMQ）2.緩存層（Redis）3.推送服務(wù)（WebSocket/Server-SentEvents）4.數(shù)據(jù)庫（存儲消息記錄）數(shù)據(jù)一致性：-分布式鎖（Redisson）-2PC事務(wù)QPS處理：-消息分片-流量控制（令牌桶算法）題目3答案系統(tǒng)架構(gòu)：1.分片服務(wù)：將數(shù)據(jù)哈希分片2.節(jié)點集群：存儲分片數(shù)據(jù)3.元數(shù)據(jù)管理：記錄分片位置4.讀寫代理：處理客戶端請求MD五分片算法：-將文件哈希值映射到5個分片-每個分片存儲不同部分數(shù)據(jù)一致性：-多副本機制-Paxos/Raft一致性協(xié)議題目4答案系統(tǒng)架構(gòu)：1.接入層：限流（令牌桶）2.庫存服務(wù)：分布式鎖（Redis）3.訂單服務(wù)：事務(wù)補償4.支付服務(wù)：異步處理防超賣策略：-庫存預(yù)扣減-分布式鎖-異步下單系統(tǒng)瓶頸：-庫存扣減鎖競爭-訂單生成延遲優(yōu)化方案：-熔斷降級-熱點庫存預(yù)加載算法與數(shù)據(jù)結(jié)構(gòu)答案題目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實現(xiàn)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);}}解析：堆排序通過建最大堆實現(xiàn)，時間復(fù)雜度O(nlogn)。題目4答案pythondeflongestPalindrome(s:str)->str:ifnots:return""start,end=0,0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,