2025年軟件開發(fā)工程師面試題及備考策略一、編程題（共5題，每題10分，總分50分）題目1：字符串反轉(zhuǎn)題目描述：給定一個(gè)字符串`s`，原地反轉(zhuǎn)字符串中的字符順序。示例：輸入：`"hello"`輸出：`"olleh"`要求：1.不能使用額外的字符串變量存儲(chǔ)結(jié)果。2.只能使用常數(shù)額外空間。題目2：二叉樹最大深度題目描述：給定一個(gè)二叉樹的根節(jié)點(diǎn)`root`，返回其最大深度。示例：輸入：3/\920/\157輸出：`3`要求：1.可以使用遞歸或迭代方法。2.時(shí)間復(fù)雜度不超過O(n)。題目3：滑動(dòng)窗口最大值題目描述：給定一個(gè)整數(shù)數(shù)組`nums`和一個(gè)整數(shù)`k`，找到長(zhǎng)度為`k`的滑動(dòng)窗口內(nèi)的最大值。示例：輸入：`nums=[1,3,-1,-3,5,3,6,7]`,`k=3`輸出：`[3,3,5,5,6,7]`要求：1.不能使用排序。2.時(shí)間復(fù)雜度不超過O(n)。題目4：合并兩個(gè)排序鏈表題目描述：將兩個(gè)排序鏈表合并為一個(gè)新的排序鏈表。示例：輸入：-鏈表1：`1->2->4`-鏈表2：`1->3->4`輸出：`1->1->2->3->4->4`要求：1.必須原地修改其中一個(gè)鏈表。2.不能使用額外的存儲(chǔ)空間。題目5：動(dòng)態(tài)規(guī)劃：爬樓梯題目描述：假設(shè)你正在爬樓梯。每次你可以爬1或2個(gè)臺(tái)階。給定一個(gè)整數(shù)`n`，返回到達(dá)頂部所需的最少步數(shù)。示例：輸入：`n=2`輸出：`2`要求：1.可以使用遞歸或動(dòng)態(tài)規(guī)劃。2.不能使用遞歸（避免棧溢出）。二、系統(tǒng)設(shè)計(jì)題（共2題，每題25分，總分50分）題目6：設(shè)計(jì)LRU緩存題目描述：設(shè)計(jì)一個(gè)LRU（LeastRecentlyUsed）緩存系統(tǒng)，支持以下操作：1.`get(key)`：獲取鍵`key`對(duì)應(yīng)的值，如果不存在返回-1。2.`put(key,value)`：向緩存中插入一個(gè)鍵值對(duì)。如果鍵已存在，則更新其值；如果緩存已滿，則刪除最久未使用的鍵。要求：1.支持O(1)時(shí)間復(fù)雜度的`get`和`put`操作。2.描述數(shù)據(jù)結(jié)構(gòu)和核心邏輯。題目7：設(shè)計(jì)短URL服務(wù)題目描述：設(shè)計(jì)一個(gè)短URL服務(wù)，實(shí)現(xiàn)以下功能：1.將長(zhǎng)URL轉(zhuǎn)換為短URL。2.根據(jù)短URL解析回原始長(zhǎng)URL。示例：輸入：`longURL="/very/long/path"`輸出：-短URL：`/abc123`-解析回：`/very/long/path`要求：1.短URL應(yīng)具有唯一性且長(zhǎng)度盡可能短。2.描述核心算法和數(shù)據(jù)結(jié)構(gòu)。三、算法題（共5題，每題10分，總分50分）題目8：快速排序題目描述：實(shí)現(xiàn)快速排序算法，并說明其平均時(shí)間復(fù)雜度和最壞情況復(fù)雜度。示例：輸入：`[10,7,8,9,1,5]`輸出：`[1,5,7,8,9,10]`要求：1.不能使用內(nèi)置排序函數(shù)。2.解釋分區(qū)（partition）過程。題目9：鏈表反轉(zhuǎn)題目描述：反轉(zhuǎn)一個(gè)單鏈表。示例：輸入：`1->2->3->4->5`輸出：`5->4->3->2->1`要求：1.只能使用常數(shù)額外空間。2.時(shí)間復(fù)雜度O(n)。題目10：斐波那契數(shù)列題目描述：給定一個(gè)整數(shù)`n`，計(jì)算斐波那契數(shù)列的第`n`項(xiàng)（從0開始）。示例：輸入：`n=4`輸出：`3`（斐波那契序列：0,1,1,2,3）要求：1.不能使用遞歸（避免棧溢出）。2.時(shí)間復(fù)雜度O(1)空間復(fù)雜度。題目11：合并區(qū)間題目描述：給定一個(gè)區(qū)間數(shù)組`intervals`，合并所有重疊的區(qū)間。示例：輸入：`[[1,3],[2,6],[8,10],[15,18]]`輸出：`[[1,6],[8,10],[15,18]]`要求：1.不能使用內(nèi)置函數(shù)。2.時(shí)間復(fù)雜度O(nlogn)。題目12：最長(zhǎng)回文子串題目描述：給定一個(gè)字符串`s`，找到其中最長(zhǎng)的回文子串的長(zhǎng)度。示例：輸入：`"babad"`輸出：`3`（"bab"或"aba"）要求：1.可以使用動(dòng)態(tài)規(guī)劃或中心擴(kuò)展法。2.時(shí)間復(fù)雜度O(n^2)。四、面試官提問（共3題，每題15分，總分45分）題目13：項(xiàng)目經(jīng)驗(yàn)提問題目描述：請(qǐng)介紹你在最近項(xiàng)目中遇到的最大的技術(shù)挑戰(zhàn)，你是如何解決的？要求：1.描述問題背景和解決方案。2.說明你從中學(xué)習(xí)的經(jīng)驗(yàn)。題目14：系統(tǒng)設(shè)計(jì)擴(kuò)展題目描述：如果LRU緩存需要支持并發(fā)訪問（多線程），你會(huì)如何設(shè)計(jì)？要求：1.描述鎖的粒度和選擇。2.說明如何避免死鎖。題目15：職業(yè)規(guī)劃題目描述：請(qǐng)談?wù)勀銓?duì)未來3-5年職業(yè)發(fā)展的規(guī)劃，以及你希望提升哪些技術(shù)能力？要求：1.結(jié)合行業(yè)趨勢(shì)和技術(shù)方向。2.說明如何實(shí)現(xiàn)這些目標(biāo)。答案部分編程題答案答案1：字符串反轉(zhuǎn)pythondefreverseString(s:str)->str:#原地反轉(zhuǎn)：雙指針法s=list(s)#將字符串轉(zhuǎn)為列表（Python中字符串不可變）left,right=0,len(s)-1whileleft<right:s[left],s[right]=s[right],s[left]left+=1right-=1return''.join(s)答案2：二叉樹最大深度python#定義二叉樹節(jié)點(diǎn)classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root:TreeNode)->int:#遞歸方法ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))答案3：滑動(dòng)窗口最大值pythonfromcollectionsimportdequedefmaxSlidingWindow(nums,k):ifnotnums:return[]res=[]dq=deque()#存儲(chǔ)最大值的索引foriinrange(len(nums)):#移除窗口外的元素ifdqanddq[0]<i-k+1:dq.popleft()#移除小于當(dāng)前元素的索引whiledqandnums[i]>=nums[dq[-1]]:dq.pop()dq.append(i)#窗口形成后，記錄最大值ifi>=k-1:res.append(nums[dq[0]])returnres答案4：合并兩個(gè)排序鏈表pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<=l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.next#合并剩余部分current.next=l1ifl1elsel2returndummy.next答案5：爬樓梯（動(dòng)態(tài)規(guī)劃）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ǒng)設(shè)計(jì)題答案答案6：LRU緩存設(shè)計(jì)plaintext數(shù)據(jù)結(jié)構(gòu)：-使用雙向鏈表（DoublyLinkedList）存儲(chǔ)鍵值對(duì)，鏈表頭部為最近使用的節(jié)點(diǎn)，尾部為最久未使用的節(jié)點(diǎn)。-使用哈希表（HashMap）存儲(chǔ)鍵到鏈表節(jié)點(diǎn)的映射，實(shí)現(xiàn)O(1)時(shí)間復(fù)雜度的查找。核心邏輯：1.get(key):-在哈希表中查找鍵對(duì)應(yīng)的節(jié)點(diǎn)。-如果存在，將該節(jié)點(diǎn)移動(dòng)到鏈表頭部（作為最近使用），并返回值。-如果不存在，返回-1。2.put(key,value):-在哈希表中查找鍵對(duì)應(yīng)的節(jié)點(diǎn)：-如果存在，更新節(jié)點(diǎn)的值為value，并將節(jié)點(diǎn)移動(dòng)到鏈表頭部。-如果不存在：-創(chuàng)建新節(jié)點(diǎn)，插入到鏈表頭部。-如果鏈表長(zhǎng)度超過容量，刪除鏈表尾部節(jié)點(diǎn)（最久未使用）。-在哈希表中插入新鍵值對(duì)。答案7：短URL服務(wù)設(shè)計(jì)plaintext核心算法：-使用哈希函數(shù)將長(zhǎng)URL映射為短URL。-使用自增ID或隨機(jī)碼作為短URL部分。-存儲(chǔ)長(zhǎng)URL和短URL的映射關(guān)系（數(shù)據(jù)庫或緩存）。數(shù)據(jù)結(jié)構(gòu)：-哈希表：存儲(chǔ)短URL到長(zhǎng)URL的映射（實(shí)現(xiàn)快速查找）。-數(shù)據(jù)庫：持久化存儲(chǔ)映射關(guān)系，支持高并發(fā)讀寫。實(shí)現(xiàn)步驟：1.接收長(zhǎng)URL，生成短URL：-生成唯一標(biāo)識(shí)符（如UUID或自增ID）。-構(gòu)造短URL：`/{唯一標(biāo)識(shí)符}`。-存儲(chǔ)映射關(guān)系到數(shù)據(jù)庫/緩存。2.解析短URL：-從路徑中提取唯一標(biāo)識(shí)符。-查詢哈希表/數(shù)據(jù)庫獲取對(duì)應(yīng)長(zhǎng)URL。-返回長(zhǎng)URL。算法題答案答案8：快速排序pythondefquickSort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquickSort(left)+middle+quickSort(right)復(fù)雜度：平均O(nlogn)，最壞O(n^2)答案9：鏈表反轉(zhuǎn)pythondefreverseList(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.next#保存下一個(gè)節(jié)點(diǎn)current.next=prev#反轉(zhuǎn)指針prev=current#移動(dòng)prevcurrent=next_node#移動(dòng)currentreturnprev答案10：斐波那契數(shù)列（動(dòng)態(tài)規(guī)劃）pythondeffib(n:int)->int:ifn==0:return0dp=[0,1]+[0]*(n-1)foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]答案11：合并區(qū)間pythondefmerge(intervals):ifnotintervals:return[]#按左端點(diǎn)排序intervals.sort(key=lambdax:x[0])merged=[]forintervalinintervals:ifnotmergedormerged[-1][1]<interval[0]:merged.append(interval)else:merged[-1][1]=max(merged[-1][1],interval[1])returnmerged答案12：最長(zhǎng)回文子串（中心擴(kuò)展法）pythondeflongestPalindrome(s:str)->int:ifnots:return0start,end=0,0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)#奇數(shù)長(zhǎng)度len2=expandAroundCenter(s,i,i+1)#偶數(shù)長(zhǎng)度max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returnend-start+1defexpandAroundCenter(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1面試官提問答案答案13：項(xiàng)目經(jīng)驗(yàn)提問plaintext問題：在XX項(xiàng)目中，我們面臨高并發(fā)場(chǎng)景下的緩存穿透問題。解決方案：1.問題背景：由于部分熱點(diǎn)數(shù)據(jù)未被緩存，