2026年軟件工程師面試技巧：編程能力考察與答案解析一、編程基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)（共5題，總分20分）1.數(shù)組輪轉(zhuǎn)（4分）題目：給定一個(gè)數(shù)組`arr`和一個(gè)正整數(shù)`k`，將數(shù)組中的元素向右輪轉(zhuǎn)`k`次。請(qǐng)編寫(xiě)代碼實(shí)現(xiàn)該功能，并說(shuō)明時(shí)間復(fù)雜度。示例：輸入：`arr=[1,2,3,4,5]`,`k=2`輸出：`[4,5,1,2,3]`答案解析：pythondefrotate(arr,k):n=len(arr)k=k%n#防止k大于數(shù)組長(zhǎng)度returnarr[-k:]+arr[:-k]示例print(rotate([1,2,3,4,5],2))#輸出:[4,5,1,2,3]解析：-將數(shù)組分為兩部分：`arr[-k:]`（后`k`個(gè)元素）和`arr[:-k]`（前`n-k`個(gè)元素），然后拼接即可。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)（可以使用原地操作優(yōu)化空間復(fù)雜度）。2.快速排序?qū)崿F(xiàn)（4分）題目：請(qǐng)實(shí)現(xiàn)快速排序算法，并解釋其核心思想。答案解析：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)示例print(quick_sort([3,6,8,10,1,2,1]))#輸出:[1,1,2,3,6,8,10]解析：-核心思想：選擇一個(gè)基準(zhǔn)值（pivot），將數(shù)組分為小于、等于、大于三部分，然后遞歸排序左右兩部分。-時(shí)間復(fù)雜度：平均O(nlogn)，最壞O(n2)（當(dāng)基準(zhǔn)值選擇不均時(shí)）。3.環(huán)形鏈表判斷（4分）題目：設(shè)計(jì)一個(gè)算法，判斷一個(gè)鏈表是否存在環(huán)。如果存在，返回環(huán)的入口節(jié)點(diǎn)；否則返回`None`。答案解析：pythonclassListNode:def__init__(self,x):self.val=xself.next=Nonedefdetect_cycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:找到環(huán)，計(jì)算入口slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone示例創(chuàng)建鏈表1->2->3->4->2(環(huán))node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node1.next=node2node2.next=node3node3.next=node4node4.next=node2#創(chuàng)建環(huán)print(detect_cycle(node1).val)#輸出:2解析：-使用快慢指針：快指針每次走兩步，慢指針每次走一步，相遇則存在環(huán)。-相遇后，慢指針回到頭節(jié)點(diǎn)，再次與快指針同步移動(dòng)，相遇點(diǎn)即為環(huán)入口。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)。4.樹(shù)的最大深度（4分）題目：給定一個(gè)二叉樹(shù)，請(qǐng)編寫(xiě)代碼計(jì)算其最大深度（即從根節(jié)點(diǎn)到最遠(yuǎn)葉節(jié)點(diǎn)的最長(zhǎng)路徑）。答案解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))示例創(chuàng)建二叉樹(shù):1/\23/\45root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(max_depth(root))#輸出:3解析：-遞歸計(jì)算左子樹(shù)和右子樹(shù)的最大深度，取較大值加1。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(h)（h為樹(shù)的高度）。5.字符串最長(zhǎng)不重復(fù)子串（4分）題目：給定一個(gè)字符串`s`，請(qǐng)找到其中最長(zhǎng)的無(wú)重復(fù)字符的子串，并返回其長(zhǎng)度。答案解析：pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len示例print(length_of_longest_substring("abcabcbb"))#輸出:3("abc")解析：-使用滑動(dòng)窗口：左指針移動(dòng)時(shí)跳過(guò)重復(fù)字符，右指針遍歷字符串。-使用哈希表記錄字符上一次出現(xiàn)的位置，更新窗口左邊界。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(min(m,n))（m為字符集大小）。二、算法設(shè)計(jì)與問(wèn)題解決（共5題，總分25分）1.排列組合問(wèn)題（5分）題目：給定兩個(gè)數(shù)組`nums1`和`nums2`，請(qǐng)編寫(xiě)代碼合并它們的所有排列，并去除重復(fù)的排列。示例：輸入：`nums1=[1,2]`,`nums2=[1,2,3]`輸出：`[[1,1,2],[1,2,1],[1,2,3],[2,1,1],[2,1,2],[2,1,3]]`答案解析：pythonfromitertoolsimportpermutationsdefunique_permutations(nums1,nums2):returnlist(set(permutations(nums1+nums2)))示例nums1=[1,2]nums2=[1,2,3]print(unique_permutations(nums1,nums2))解析：-使用`itertools.permutations`生成所有排列，然后轉(zhuǎn)換為集合去重。-注意：集合是無(wú)序的，如果需要有序輸出，可先排序再去重。2.最小路徑和（5分）題目：給定一個(gè)二維網(wǎng)格`grid`，每個(gè)格子中的值代表該位置的代價(jià)，請(qǐng)找到從左上角到右下角的最低總代價(jià)路徑。示例：輸入：`grid=[[1,3,1],[1,5,1],[4,2,1]]`輸出：7（路徑：1→3→1→1→1）答案解析：pythondefmin_path_sum(grid):ifnotgridornotgrid[0]:return0m,n=len(grid),len(grid[0])dp=[[0]nfor_inrange(m)]dp[0][0]=grid[0][0]foriinrange(1,m):dp[i][0]=dp[i-1][0]+grid[i][0]forjinrange(1,n):dp[0][j]=dp[0][j-1]+grid[0][j]foriinrange(1,m):forjinrange(1,n):dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]returndp[-1][-1]示例print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))#輸出:7解析：-動(dòng)態(tài)規(guī)劃：dp[i][j]表示到達(dá)`(i,j)`的最小代價(jià)。-狀態(tài)轉(zhuǎn)移：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]。-時(shí)間復(fù)雜度：O(mn)，空間復(fù)雜度：O(mn)。3.爬樓梯問(wèn)題（5分）題目：假設(shè)你正在爬樓梯，每次可以爬1或2級(jí)臺(tái)階。給定總臺(tái)階數(shù)`n`，請(qǐng)計(jì)算共有多少種不同的爬法。示例：輸入：`n=3`輸出：3（爬法：1+1+1，1+2，2+1）答案解析：pythondefclimb_stairs(n):ifn==1:return1dp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例print(climb_stairs(3))#輸出:3解析：-動(dòng)態(tài)規(guī)劃：dp[i]表示到達(dá)第`i`級(jí)臺(tái)階的爬法數(shù)量。-狀態(tài)轉(zhuǎn)移：dp[i]=dp[i-1]+dp[i-2]。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)（可優(yōu)化為O(1)）。4.括號(hào)匹配問(wèn)題（5分）題目：給定一個(gè)字符串`s`，請(qǐng)判斷其中的括號(hào)（`()`、`[]`、`{}`）是否匹配。示例：輸入：`s="{[()]}"`輸出：`True`輸入：`s="{[(])}"`輸出：`False`答案解析：pythondefis_valid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack示例print(is_valid("{[()]}"))#輸出:Trueprint(is_valid("{[(])}"))#輸出:False解析：-使用棧：遇到左括號(hào)入棧，右括號(hào)時(shí)與棧頂比較。-如果匹配則出棧，否則返回`False`。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)。5.翻轉(zhuǎn)二叉樹(shù)（5分）題目：給定一個(gè)二叉樹(shù)，請(qǐng)編寫(xiě)代碼將其左右子樹(shù)互換。答案解析：pythondefinvert_tree(root):ifnotroot:returnNoneleft,right=root.left,root.rightroot.left=invert_tree(right)root.right=invert_tree(left)returnroot示例創(chuàng)建二叉樹(shù):1/\23/\45root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)invert_tree(root)翻轉(zhuǎn)后:1->3->2,2->5->4解析：-遞歸交換左右子樹(shù)。-時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(h)（h為樹(shù)的高度）。三、系統(tǒng)設(shè)計(jì)（共5題，總分25分）1.設(shè)計(jì)LRU緩存（8分）題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)LRU（LeastRecentlyUsed）緩存系統(tǒng)，支持容量限制和最近最少使用淘汰策略。答案解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)示例lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#返回1lru.put(3,3)#去除鍵2print(lru.get(2))#返回-1(未找到)解析：-使用哈希表記錄鍵值，雙端隊(duì)列記錄訪(fǎng)問(wèn)順序。-`get`操作將鍵移到隊(duì)尾，`put`操作先判斷容量，淘汰最久未使用的鍵。-時(shí)間復(fù)雜度：O(1)。2.設(shè)計(jì)短URL服務(wù)（7分）題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)短URL服務(wù)，將長(zhǎng)URL轉(zhuǎn)換為短URL，并支持反向解析。答案解析：pythonimporthashlibimportrandomclassShortURL:def__init__(self):self.url_map={}self.base_url="http://short.url/"defencode(self,long_url:str)->str:hash_code=hashlib.md5(long_url.encode()).hexdigest()[:8]short_id=''.join(random.choices('0123456789abcdef',k=6))self.url_map[self.base_url+short_id]=long_urlreturnself.base_url+short_iddefdecode(self,short_url:str)->str:returnself.url_map.get(short_url,"InvalidURL")示例shortener=ShortURL()long_url="/article"short_url=shortener.encode(long_url)print(short_url)#輸出:http://short.url/xyz123print(shortener.decode(short_url))#輸出:/article解析：-使用MD5哈希長(zhǎng)URL生成短ID，結(jié)合隨機(jī)碼避免沖突。-哈希后截取前8位，隨機(jī)生成6位字母組合。-時(shí)間復(fù)雜度：O(1)。3.設(shè)計(jì)分布式計(jì)數(shù)器（6分）題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)分布式計(jì)數(shù)器，支持高并發(fā)下的原子性計(jì)數(shù)。答案解析：pythonfromthreadingimportLockclassDistributedCounter:def__init__(self):self.count=0self.lock=Lock()defincrement(self):withself.lock:self.count+=1returnself.count示例counter=DistributedCounter()for_inrange(10):print(counter.increment())#輸出:1到10解析：-使用鎖保證線(xiàn)程安全。-若需分布式支持，可結(jié)合Redis的`INCR`命令。-時(shí)間復(fù)雜度：O(1)。4.設(shè)計(jì)微博關(guān)注系統(tǒng)（5分）題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)微博關(guān)注系統(tǒng)，支持用戶(hù)關(guān)注/取消關(guān)注、獲取關(guān)注者列表等功能。答案解析：pythonclassWeiboFollowSystem:def__init__(self):self.followees={}deffollow(self,follower:str,followee:str)->None:iffollowernotinself.followees:self.followees[follower]=set()self.followees[follower].add(followee)defunfollow(self,follower:str,followee:str)->None:iffollowerinself.followeesandfolloweeinself.followees[follower]:self.followees[follower].remove(followee)defget_followees(self,user:str)->list:returnlist(self.followees.get(user,[]))示例system=WeiboFollowSystem()system.follow("Alice","Bob")system.follow("Alice","Charlie")print(system.get_followees("Alice"))#輸出:["Bob","Charlie"]system.unfollow("Alice","Bob")print(system.get_followees("Alice"))#輸出:["C