2026年軟件工程師面試筆試模擬題一、編程題（共5題，每題20分，總分100分）1.數(shù)組旋轉(zhuǎn)問(wèn)題（20分）題目：給定一個(gè)數(shù)組`nums`和一個(gè)整數(shù)`k`，將數(shù)組向右旋轉(zhuǎn)`k`次。假設(shè)`k`是非負(fù)數(shù)且可能大于數(shù)組長(zhǎng)度。請(qǐng)編寫(xiě)一個(gè)函數(shù)實(shí)現(xiàn)這一功能，并返回旋轉(zhuǎn)后的數(shù)組。示例：輸入：`nums=[1,2,3,4,5]`,`k=2`輸出：`[4,5,1,2,3]`要求：-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)2.二叉樹(shù)最大深度（20分）題目：給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn)`root`，計(jì)算它的最大深度。最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。示例：輸入：`root=[3,9,20,null,null,15,7]`輸出：`3`要求：-可以使用遞歸或迭代方法實(shí)現(xiàn)-請(qǐng)描述你的解法思路3.字符串匹配問(wèn)題（20分）題目：實(shí)現(xiàn)`strStr()`函數(shù)，返回`haystack`中`needle`第一次出現(xiàn)的索引。如果`needle`不存在，返回`-1`。示例：輸入：`haystack="hello"`,`needle="ll"`輸出：`2`要求：-可以使用KMP算法或其他高效方法實(shí)現(xiàn)-請(qǐng)說(shuō)明你的實(shí)現(xiàn)原理4.排序鏈表（20分）題目：給定一個(gè)鏈表的頭節(jié)點(diǎn)`head`，對(duì)鏈表進(jìn)行排序，返回排序后的鏈表。你可以選擇使用歸并排序或快速排序。示例：輸入：`head=[4,2,1,3]`輸出：`1->2->3->4`要求：-時(shí)間復(fù)雜度：O(nlogn)-請(qǐng)描述你的排序策略5.缺失數(shù)字（20分）題目：給定一個(gè)包含`0`到`n`中`n`個(gè)不同整數(shù)的數(shù)組，但其中一個(gè)數(shù)字缺失，請(qǐng)找出缺失的數(shù)字。示例：輸入：`nums=[3,0,1]`輸出：`2`要求：-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)二、算法題（共5題，每題20分，總分100分）1.最長(zhǎng)回文子串（20分）題目：給定一個(gè)字符串`s`，找到其中最長(zhǎng)的回文子串的長(zhǎng)度。示例：輸入：`s="babad"`輸出：`3`（"bab"或"aba"）要求：-可以使用動(dòng)態(tài)規(guī)劃或中心擴(kuò)展法-請(qǐng)描述你的解法2.三數(shù)之和（20分）題目：給定一個(gè)包含`n`個(gè)整數(shù)的數(shù)組，找出所有和為`target`的三元組。示例：輸入：`nums=[-1,0,1,2]`,`target=0`輸出：`[-1,0,1]`要求：-不考慮輸出順序-時(shí)間復(fù)雜度：O(n2)3.盈利能力最大化（20分）題目：給定一個(gè)非負(fù)整數(shù)數(shù)組`prices`，其中`prices[i]`表示第`i`天的股票價(jià)格。最多可以進(jìn)行兩次交易（每次交易由買(mǎi)入和賣出組成），返回最大利潤(rùn)。示例：輸入：`prices=[3,3,5,0,0,3,1,4]`輸出：`6`（在第4天買(mǎi)入，第6天賣出；第5天買(mǎi)入，第7天賣出）要求：-可以使用動(dòng)態(tài)規(guī)劃解決4.爬樓梯問(wèn)題（20分）題目：假設(shè)你正在爬樓梯，每次可以爬1或2級(jí)臺(tái)階。給定樓梯的總階數(shù)`n`，返回到達(dá)頂部的不同方法數(shù)。示例：輸入：`n=3`輸出：`3`（1+1+1，1+2，2+1）要求：-可以使用遞歸或動(dòng)態(tài)規(guī)劃5.有效括號(hào)（20分）題目：給定一個(gè)字符串`s`，判斷其中的括號(hào)（`()`、`[]`、`{}`）是否有效。有效括號(hào)滿足：-左括號(hào)必須與相同類型的右括號(hào)匹配-左括號(hào)必須在右括號(hào)之前-括號(hào)必須正確嵌套示例：輸入：`s="{[]}"`輸出：`true`要求：-可以使用棧實(shí)現(xiàn)三、系統(tǒng)設(shè)計(jì)題（共2題，每題50分，總分100分）1.設(shè)計(jì)URL短鏈接系統(tǒng)（50分）題目：設(shè)計(jì)一個(gè)URL短鏈接系統(tǒng)，將長(zhǎng)URL轉(zhuǎn)換為短URL，并能夠通過(guò)短URL解析回原始長(zhǎng)URL。要求：-系統(tǒng)應(yīng)支持高并發(fā)訪問(wèn)-短URL應(yīng)具有唯一性和可讀性（可選）-需要考慮數(shù)據(jù)存儲(chǔ)和緩存策略-請(qǐng)描述系統(tǒng)架構(gòu)和數(shù)據(jù)模型2.設(shè)計(jì)社交動(dòng)態(tài)（Feed）系統(tǒng)（50分）題目：設(shè)計(jì)一個(gè)社交動(dòng)態(tài)（Feed）系統(tǒng)，用戶可以發(fā)布動(dòng)態(tài)、關(guān)注/取消關(guān)注其他用戶、查看動(dòng)態(tài)列表。要求：-動(dòng)態(tài)列表應(yīng)按照時(shí)間倒序顯示-支持關(guān)注/取消關(guān)注功能-需要考慮數(shù)據(jù)存儲(chǔ)（如數(shù)據(jù)庫(kù)表設(shè)計(jì)）和性能優(yōu)化（如分頁(yè)）-請(qǐng)描述系統(tǒng)架構(gòu)和關(guān)鍵模塊答案與解析1.數(shù)組旋轉(zhuǎn)問(wèn)題（20分）解法：-使用三次反轉(zhuǎn)法1.反轉(zhuǎn)整個(gè)數(shù)組2.反轉(zhuǎn)前`k`個(gè)元素3.反轉(zhuǎn)剩余元素代碼示例：pythondefrotate(nums,k):n=len(nums)k%=nnums.reverse()reverse(nums,0,k-1)reverse(nums,k,n-1)defreverse(nums,start,end):whilestart<end:nums[start],nums[end]=nums[end],nums[start]start+=1end-=1解析：-時(shí)間復(fù)雜度：O(n)，因?yàn)槿畏崔D(zhuǎn)操作都是線性時(shí)間-空間復(fù)雜度：O(1)，只使用常數(shù)個(gè)額外空間2.二叉樹(shù)最大深度（20分）解法：-遞歸方法：pythondefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))解析：-每次遞歸計(jì)算左右子樹(shù)的最大深度，取較大值加1-時(shí)間復(fù)雜度：O(n)，訪問(wèn)每個(gè)節(jié)點(diǎn)一次-空間復(fù)雜度：O(h)，遞歸棧的深度3.字符串匹配問(wèn)題（20分）解法：-KMP算法：1.構(gòu)建next數(shù)組2.滑動(dòng)匹配代碼示例：pythondefstrStr(haystack,needle):ifnotneedle:return0next_arr=computeNext(needle)i,j=0,0whilei<len(haystack):ifhaystack[i]==needle[j]:i+=1j+=1ifj==len(needle):returni-jelifj>0:j=next_arr[j-1]else:i+=1return-1defcomputeNext(needle):next_arr=[0]len(needle)i,j=1,0whilei<len(needle):ifneedle[i]==needle[j]:next_arr[i]=j+1i+=1j+=1elifj>0:j=next_arr[j-1]else:next_arr[i]=0i+=1returnnext_arr解析：-KMP通過(guò)next數(shù)組避免無(wú)效回溯-時(shí)間復(fù)雜度：O(m+n)，m為haystack長(zhǎng)度，n為needle長(zhǎng)度-空間復(fù)雜度：O(n)，next數(shù)組4.排序鏈表（20分）解法：-歸并排序：1.分治鏈表為兩半2.遞歸排序兩半3.合并有序鏈表代碼示例：pythondefsortList(head):ifnotheadornothead.next:returnhead分治鏈表left,right=splitList(head)left=sortList(left)right=sortList(right)returnmergeList(left,right)defsplitList(head):slow,fast=head,head.nextwhilefastandfast.next:slow=slow.nextfast=fast.next.nextmid=slow.nextslow.next=Nonereturnhead,middefmergeList(l1,l2):dummy=ListNode(0)tail=dummywhilel1andl2:ifl1.val<l2.val:tail.next=l1l1=l1.nextelse:tail.next=l2l2=l2.nexttail=tail.nexttail.next=l1orl2returndummy.next解析：-歸并排序鏈表無(wú)需額外空間-時(shí)間復(fù)雜度：O(nlogn)-空間復(fù)雜度：O(logn)，遞歸棧深度5.缺失數(shù)字（20分）解法：-數(shù)學(xué)方法：pythondefmissingNumber(nums):n=len(nums)returnn(n+1)//2-sum(nums)解析：-0到n的和為n(n+1)/2，減去數(shù)組元素即缺失數(shù)字-時(shí)間復(fù)雜度：O(n)，求和操作-空間復(fù)雜度：O(1)1.最長(zhǎng)回文子串（20分）解法：-中心擴(kuò)展法：pythondeflongestPalindrome(s):ifnots:return""start,end=0,0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpandAroundCenter(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：-每個(gè)字符可能是回文中心，向兩邊擴(kuò)展-時(shí)間復(fù)雜度：O(n2)-空間復(fù)雜度：O(1)2.三數(shù)之和（20分）解法：-排序+雙指針：pythondefthreeSum(nums,target):nums.sort()res=[]foriinrange(len(nums)-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,len(nums)-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：-排序后固定一個(gè)數(shù)，雙指針找另外兩個(gè)數(shù)-時(shí)間復(fù)雜度：O(n2)-空間復(fù)雜度：O(1)3.盈利能力最大化（20分）解法：-動(dòng)態(tài)規(guī)劃：pythondefmaxProfit(nums):ifnotnums:return0first_buy,first_sell=float('inf'),0second_buy,second_sell=float('inf'),0fornuminnums:first_buy=min(first_buy,num)first_sell=max(first_sell,num-first_buy)second_buy=min(second_buy,num-first_sell)second_sell=max(second_sell,num-second_buy)returnsecond_sell解析：-兩次買(mǎi)賣：1.第一次買(mǎi)賣的最小買(mǎi)入和最大賣出2.第二次買(mǎi)賣考慮第一次的利潤(rùn)-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)4.爬樓梯問(wèn)題（20分）解法：-動(dòng)態(tài)規(guī)劃：pythondefclimbStairs(n):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]解析：-每次可爬1或2級(jí)，狀態(tài)轉(zhuǎn)移方程為f(n)=f(n-1)+f(n-2)-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(n)，可優(yōu)化為O(1)5.有效括號(hào)（20分）解法：-棧：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：-左括號(hào)入棧，右括號(hào)與棧頂匹