2026年軟件工程師面試練習(xí)題一、編程題（共3題，每題20分，總分60分）1.（20分）實現(xiàn)一個簡單的LRU（LeastRecentlyUsed）緩存機制題目描述：設(shè)計一個LRU緩存系統(tǒng)，支持以下操作：-`get(key)`:獲取鍵`key`對應(yīng)的值，如果鍵存在，則返回值并將該鍵值對移動到緩存的最前面（表示最近使用過）；如果鍵不存在，返回-1。-`put(key,value)`:插入或更新鍵值對。如果鍵已存在，則更新其值并移動到緩存最前面；如果鍵不存在，則插入該鍵值對。如果插入后緩存大小超過限制`capacity`，則刪除最久未使用的鍵值對。要求：-使用Python或Java實現(xiàn)。-時間復(fù)雜度為`O(1)`。示例：LRUCachecache=newLRUCache(2);cache.put(1,1);cache.put(2,2);cache.get(1);//返回1cache.put(3,3);//去除鍵2cache.get(2);//返回-1(未找到)cache.put(4,4);//去除鍵1cache.get(1);//返回-1(未找到)cache.get(3);//返回3cache.get(4);//返回4答案與解析：pythonclassLRUCache:def__init__(self,capacity:int):fromcollectionsimportOrderedDictself.cache=OrderedDict()self.capacity=capacitydefget(self,key:int)->int:ifkeynotinself.cache:return-1else:self.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緩存，因為`OrderedDict`可以在`O(1)`時間內(nèi)移動或刪除元素。-`get`操作時，如果鍵存在，將其移動到`OrderedDict`的末尾表示最近使用。-`put`操作時，如果鍵已存在，先移動到末尾，然后更新值；如果超出容量，刪除`OrderedDict`的第一個元素（最久未使用）。2.（20分）實現(xiàn)一個二叉樹的層序遍歷（BFS）題目描述：給定一個二叉樹，返回其層序遍歷的結(jié)果（從上到下，同一層從左到右）。示例：輸入：`[3,9,20,None,None,15,7]`輸出：`[[3],[9,20],[15,7]]`要求：-使用Python或Java實現(xiàn)。-可以使用隊列輔助遍歷。答案與解析：pythonfromcollectionsimportdequefromtypingimportList,Optional定義二叉樹節(jié)點classTreeNode:def__init__(self,val:int=0,left:Optional['TreeNode']=None,right:Optional['TreeNode']=None):self.val=valself.left=leftself.right=rightclassSolution:deflevelOrder(self,root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult解析：-使用隊列實現(xiàn)BFS遍歷，每次處理一層的所有節(jié)點。-初始化隊列時加入根節(jié)點，然后逐層出隊并加入子節(jié)點。-每次循環(huán)處理一層的節(jié)點，將值加入`current_level`，最后將`current_level`加入`result`。3.（20分）實現(xiàn)快速排序（QuickSort）的非遞歸版本題目描述：編寫一個快速排序算法的非遞歸版本。要求：-使用Python或Java實現(xiàn)。-可以使用棧來模擬遞歸過程。示例：輸入：`[4,5,1,3,2]`輸出：`[1,2,3,4,5]`答案與解析：pythondefquick_sort_iterative(arr:List[int])->List[int]:ifnotarr:return[]stack=[(0,len(arr)-1)]whilestack:start,end=stack.pop()ifstart>=end:continuepivot=arr[end]left=startforiinrange(start,end):ifarr[i]<=pivot:arr[i],arr[left]=arr[left],arr[i]left+=1arr[left],arr[end]=arr[end],arr[left]stack.append((start,left-1))stack.append((left+1,end))returnarr解析：-使用棧記錄每次分區(qū)操作的`start`和`end`索引。-模擬遞歸過程：先對左邊區(qū)間入棧，再對右邊區(qū)間入棧。-分區(qū)時，選擇最后一個元素作為`pivot`，將小于`pivot`的元素移到左邊，大于`pivot`的元素移到右邊。二、算法題（共3題，每題20分，總分60分）1.（20分）合并K個有序鏈表題目描述：給定`k`個有序鏈表，合并它們?yōu)橐粋€新的有序鏈表。示例：輸入：`[1->4->5,1->3->4,2->6]`輸出：`1->1->2->3->4->4->5->6`要求：-使用Python或Java實現(xiàn)。-可以使用最小堆（優(yōu)先隊列）優(yōu)化時間復(fù)雜度。答案與解析：pythonfromheapqimportheappush,heappopfromtypingimportList,OptionalclassListNode:def__init__(self,val:int=0,next:Optional['ListNode']=None):self.val=valself.next=nextclassSolution:defmergeKLists(self,lists:List[Optional[ListNode]])->Optional[ListNode]:min_heap=[]fori,headinenumerate(lists):ifhead:heappush(min_heap,(head.val,i,head))dummy=ListNode(0)current=dummywhilemin_heap:val,idx,node=heappop(min_heap)current.next=nodecurrent=current.nextifnode.next:heappush(min_heap,(node.next.val,idx,node.next))returndummy.next解析：-使用最小堆維護當前所有鏈表頭部節(jié)點的最小值。-每次從堆中取出最小節(jié)點，并將其下一個節(jié)點加入堆（如果存在）。-最終合并所有鏈表為一個有序鏈表。2.（20分）字符串的子集排列（無重復(fù)字符）題目描述：給定一個字符串`s`，返回其所有唯一的子集排列（不含重復(fù)字符）。示例：輸入：`"abc"`輸出：`["abc","acb","bac","bca","cab","cba"]`要求：-使用Python或Java實現(xiàn)。-可以使用回溯法。答案與解析：pythondefpermute_unique(s:str)->List[str]:result=[]s=sorted(s)#排序去重used=[False]len(s)path=[]defbacktrack():iflen(path)==len(s):result.append("".join(path))returnforiinrange(len(s)):ifused[i]or(i>0ands[i]==s[i-1]andnotused[i-1]):continueused[i]=Truepath.append(s[i])backtrack()path.pop()used[i]=Falsebacktrack()returnresult解析：-先對字符串排序，方便跳過重復(fù)字符。-使用`used`數(shù)組記錄每個字符是否已使用。-回溯時，如果當前字符與前一個字符相同且前一個字符未使用，則跳過以避免重復(fù)。3.（20分）爬樓梯的最少步數(shù)（動態(tài)規(guī)劃）題目描述：假設(shè)你正在爬樓梯，每次可以爬1或2步，給定樓梯總數(shù)`n`，返回最少需要多少步到達頂部。示例：輸入：`n=2`輸出：`2`（1+1或2）要求：-使用Python或Java實現(xiàn)。-可以使用動態(tài)規(guī)劃或數(shù)學(xué)方法（斐波那契數(shù)列）。答案與解析：pythondefclimbStairs(n:int)->int:ifn==1:return1dp=[0](n+1)dp[1],dp[2]=1,2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：-動態(tài)規(guī)劃：`dp[i]=dp[i-1]+dp[i-2]`，因為每次可以爬1或2步。-初始條件：`dp[1]=1`，`dp[2]=2`。-最終結(jié)果為`dp[n]`。三、系統(tǒng)設(shè)計題（共1題，40分）1.（40分）設(shè)計一個短鏈接（TinyURL）服務(wù)題目描述：設(shè)計一個短鏈接服務(wù)，如`/abc123`可以映射到實際的URL（如`/very-long-url`）。要求：-系統(tǒng)需要支持高并發(fā)訪問。-短鏈接應(yīng)具有唯一性且易于生成。-支持快速查詢和更新。設(shè)計要點：1.短鏈接生成算法。2.數(shù)據(jù)存儲方案（數(shù)據(jù)庫或緩存）。3.高并發(fā)處理。4.系統(tǒng)擴展性。答案與解析：1.短鏈接生成算法：-使用Base62編碼（包含`a-z`、`A-Z`、`0-9`共62個字符）將長URL轉(zhuǎn)換為固定長度的短鏈接。-例如：`123456`->`1H5uP`。pythonimportbase64defencode_url(id:int)->str:returnbase64.urlsafe_b64encode(f"{id}".encode()).decode().rstrip('=')[:6]defdecode_url(short_url:str)->int:returnint(base64.urlsafe_b64decode(short_url.encode()+b'=='),62)2.數(shù)據(jù)存儲方案：-使用Redis緩存存儲短鏈接與長URL的映射關(guān)系，支持高并發(fā)讀寫。-使用關(guān)系型數(shù)據(jù)庫（如MySQL）存儲持久化數(shù)據(jù)。redisRedis