2026年計算機編程面試題及編程解決方案一、編程實現(xiàn)題（共5題，每題20分，總分100分）題目1（15分）：實現(xiàn)一個函數(shù)，輸入一個非空字符串，返回該字符串中所有唯一字符的列表。要求時間復雜度為O(n)，空間復雜度為O(1)。示例：輸入："leetcode"輸出：["l","d"]題目2（25分）：設計一個LRU（LeastRecentlyUsed）緩存系統(tǒng)，支持以下操作：1.`get(key)`：獲取鍵key對應的值，如果鍵不存在返回-1。2.`put(key,value)`：向緩存中插入鍵值對，如果鍵已存在則更新其值。當緩存容量達到限制時，刪除最久未使用的鍵。要求：-使用雙向鏈表和哈希表實現(xiàn)，確保`get`和`put`操作的時間復雜度為O(1)。-提供Python或Java實現(xiàn)。題目3（20分）：給定一個包含n個整數(shù)的數(shù)組，設計一個算法，找到數(shù)組中第三大的數(shù)。如果數(shù)組中少于三個不同的數(shù)，返回最大的數(shù)。示例：輸入：[3,2,1,5,6,4]輸出：2輸入：[1,2]輸出：2題目4（20分）：實現(xiàn)一個簡單的文本編輯器，支持以下操作：1.`addText(text)`：在光標位置插入文本。2.`deleteText(k)`：刪除光標左邊的k個字符（如果k大于光標左邊的字符數(shù)，則全部刪除）。3.`cursorLeft(k)`：將光標向左移動k個位置（如果移動到開頭，則停留在開頭）。4.`cursorRight(k)`：將光標向右移動k個位置（如果移動到末尾，則停留在末尾）。要求：-使用?；蜴湵韺崿F(xiàn)，確保所有操作的時間復雜度為O(1)。-提供Python實現(xiàn)。題目5（20分）：設計一個算法，判斷一個無向圖是否是二分圖。二分圖是指可以將圖的節(jié)點分成兩個集合，使得每條邊的兩個節(jié)點分別屬于不同的集合。要求：-使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）實現(xiàn)。-提供Python或Java實現(xiàn)。二、算法設計題（共3題，每題30分，總分90分）題目6（30分）：設計一個算法，給定一個包含n個整數(shù)的數(shù)組和一個目標值target，找出數(shù)組中和為目標值的三元組數(shù)量。要求：-不考慮順序，重復的三元組只計算一次。-時間復雜度盡可能低。示例：輸入：nums=[1,5,-10,0,7,10],target=5輸出：3（三元組為[-10,5,10],[0,5,0],[1,5,-10]）題目7（30分）：設計一個算法，給定一個字符串s和一個整數(shù)k，返回s中長度為k的所有子字符串的最小字典序。示例：輸入：s="dbdbdd",k=3輸出："bdb"題目8（30分）：設計一個算法，給定一個包含n個整數(shù)的數(shù)組，返回一個新數(shù)組，其中新數(shù)組的第i個元素是原數(shù)組中比第i個元素大的元素的數(shù)量。示例：輸入：[5,2,6,1]輸出：[2,1,1,0]（第一個元素5右邊有2個比它大，第二個元素2右邊有1個比它大，以此類推）三、系統(tǒng)設計題（共2題，每題35分，總分70分）題目9（35分）：設計一個簡單的分布式緩存系統(tǒng)，支持以下功能：1.`get(key)`：從緩存中獲取鍵key對應的值。2.`put(key,value)`：向緩存中插入或更新鍵值對。3.緩存數(shù)據(jù)在多個節(jié)點間同步（使用一致性哈?；蝾愃茩C制）。4.支持基本的故障恢復（一個節(jié)點失效時，其他節(jié)點可以接管其部分數(shù)據(jù)）。要求：-描述系統(tǒng)架構(gòu)、數(shù)據(jù)存儲方式、一致性協(xié)議。-提供偽代碼或高層次設計思路。題目10（35分）：設計一個簡單的實時推薦系統(tǒng)，支持以下功能：1.用戶每次瀏覽商品時，記錄瀏覽行為。2.根據(jù)用戶的瀏覽歷史，實時推薦用戶可能感興趣的商品。3.推薦算法需要考慮：-用戶最近瀏覽的商品優(yōu)先。-商品之間的關聯(lián)性（如購買同一商品的用戶的瀏覽習慣）。-推薦結(jié)果的多樣性（避免推薦過多同類商品）。要求：-描述系統(tǒng)架構(gòu)、數(shù)據(jù)存儲方式、推薦算法。-提供偽代碼或高層次設計思路。答案與解析一、編程實現(xiàn)題題目1（15分）：解決方案：使用一個固定大小的哈希表記錄字符出現(xiàn)的次數(shù)，然后遍歷一次字符串，收集出現(xiàn)次數(shù)為1的字符。pythondefunique_chars(s:str)->list:counts=[0]256#假設ASCII字符集forcharins:counts[ord(char)]+=1return[chr(i)foriinrange(256)ifcounts[i]==1]解析：-時間復雜度：O(n)，n為字符串長度。-空間復雜度：O(1)，哈希表大小固定為256。題目2（25分）：解決方案：使用雙向鏈表和哈希表實現(xiàn)。雙向鏈表頭節(jié)點為最近使用，尾節(jié)點為最久未使用。哈希表存儲鍵到鏈表節(jié)點的映射。pythonclassListNode:def__init__(self,key=None,val=None):self.key=keyself.val=valself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode()self.tail=ListNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node:ListNode):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:ListNode):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:ListNode):self._remove_node(node)self._add_node(node)def_pop_tail(self)->ListNode:res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valdefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.val=valueself._move_to_head(node)解析：-`get`和`put`操作通過哈希表和鏈表的結(jié)合，確保時間復雜度為O(1)。-鏈表維護最近使用順序，哈希表快速查找節(jié)點。題目3（20分）：解決方案：維護三個變量分別記錄第一大、第二大、第三大的數(shù)，遍歷數(shù)組時更新這三個變量。pythondefthird_largest(nums:list)->int:first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:third=secondsecond=firstfirst=numeliffirst>num>second:third=secondsecond=numelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst解析：-遍歷一次數(shù)組，時間復雜度O(n)。-使用三個變量記錄最大值，空間復雜度O(1)。題目4（20分）：解決方案：使用棧實現(xiàn)光標位置左側(cè)的文本，另一個棧記錄光標右側(cè)的文本。通過操作兩個棧實現(xiàn)插入、刪除和光標移動。pythonclassTextEditor:def__init__(self):self.left=[]self.right=[]defaddText(self,text:str)->None:self.left.extend(list(text))defdeleteText(self,k:int)->None:delself.left[:min(k,len(self.left))]defcursorLeft(self,k:int)->None:for_inrange(min(k,len(self.left))):self.right.append(self.left.pop())defcursorRight(self,k:int)->None:for_inrange(min(k,len(self.right))):self.left.append(self.right.pop())defgetCurrentText(self)->str:return''.join(self.left)+''.join(reversed(self.right))解析：-棧實現(xiàn)插入和刪除操作，時間復雜度O(1)。-光標移動通過棧操作實現(xiàn)，時間復雜度O(k)。題目5（20分）：解決方案：使用DFS或BFS遍歷圖，嘗試將節(jié)點分成兩個集合，檢查每條邊是否連接不同集合的節(jié)點。pythondefisBipartite(graph:list)->bool:color={}defdfs(node,c):color[node]=cforneighboringraph[node]:ifneighborincolor:ifcolor[neighbor]==color[node]:returnFalseelse:ifnotdfs(neighbor,1-c):returnFalsereturnTruefornodeinrange(len(graph)):ifnodenotincolor:ifnotdfs(node,0):returnFalsereturnTrue解析：-使用DFS遍歷圖，時間復雜度O(V+E)。-使用哈希表記錄節(jié)點顏色，空間復雜度O(V)。二、算法設計題題目6（30分）：解決方案：先對數(shù)組排序，然后使用雙指針法。pythondefthree_sum(nums:list,target:int)->int:nums.sort()n=len(nums)count=0foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:count+=1left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1eliftotal<target:left+=1else:right-=1returncount解析：-排序后時間復雜度O(nlogn)，雙指針遍歷為O(n^2)。-使用去重避免重復計數(shù)。題目7（30分）：解決方案：滑動窗口法，記錄當前窗口的最小值。pythondefsmallest_window(s:str,k:int)->str:n=len(s)ifn<k:return""min_window=s[:k]foriinrange(n-k+1):window=s[i:i+k]ifwindow<min_window:min_window=windowreturnmin_window解析：-滑動窗口遍歷字符串，時間復雜度O(n)。-每次比較窗口字符串，時間復雜度O(k)。題目8（30分）：解決方案：使用單調(diào)棧記錄每個元素右邊比它大的元素數(shù)量。pythondefcount_of_larger(nums:list)->list:n=len(nums)res=[0]nstack=[]foriinrange(n):whilestackandnums[stack[-1]]<nums[i]:res[stack.pop()]+=1stack.append(i)whilestack:res[stack.pop()]+=0returnres解析：-單調(diào)棧遍歷數(shù)組，時間復雜度O(n)。-棧輔助計數(shù)，空間復雜度O(n)。三、系統(tǒng)設計題題目9（35分）：解決方案：-架構(gòu)：-使用一致性哈希算法將數(shù)據(jù)均勻分布在多個節(jié)點上。-每個節(jié)點存儲其負責的數(shù)據(jù)塊。-使用Raft或Paxos協(xié)議保證數(shù)據(jù)一致性。-數(shù)據(jù)存儲：-每個節(jié)點使用本地磁盤或SSD存儲數(shù)據(jù)。-使用布隆過濾器快速判斷數(shù)據(jù)是否在本地節(jié)點。-一致性協(xié)議：-`put`操作時，先向leader節(jié)點請求，leader節(jié)點通過Raft協(xié)議廣播到所有節(jié)點。-`get`操作時，先查詢本地節(jié)點，如果未命中則通過一致性哈希查找其他節(jié)點。plaintext偽代碼：functionput(key,value):leader=find_leader(key)ifleader:leader.append(key,value)propagateRaft(leader,key,value)functionget(key):node=find_node(key)ifnode.contains(key):returnnode.get(key)else:return-1解析：-一致性哈希保證數(shù)據(jù)均勻分布，減少