2025年軟件開(kāi)發(fā)面試技巧及常見(jiàn)問(wèn)題解析中級(jí)1.編程實(shí)現(xiàn)題（3題，每題20分）題目1問(wèn)題描述：實(shí)現(xiàn)一個(gè)函數(shù)，將字符串中的所有空格替換為`%20`。假設(shè)字符串有足夠的空間存儲(chǔ)轉(zhuǎn)換后的字符串，并且你可以返回一個(gè)新的字符串。要求：-不使用額外的庫(kù)函數(shù)-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度O(1)示例：輸入："HelloWorld"輸出："Hello%20World%20"題目2問(wèn)題描述：實(shí)現(xiàn)一個(gè)二叉樹(shù)的中序遍歷算法?？梢允褂眠f歸或迭代的方式完成。要求：-支持遞歸和迭代兩種方式-輸出遍歷結(jié)果為列表形式示例：輸入：二叉樹(shù)`[1,null,2,3]`輸出：`[1,3,2]`題目3問(wèn)題描述：實(shí)現(xiàn)一個(gè)LRU（最近最少使用）緩存。緩存容量為固定值，當(dāng)緩存滿時(shí)，應(yīng)該驅(qū)逐最久未使用的項(xiàng)目。要求：-支持get和put操作-時(shí)間復(fù)雜度O(1)-使用雙向鏈表和哈希表實(shí)現(xiàn)示例：輸入：-put(1,1)-put(2,2)-get(1)//返回1-put(3,3)//去除鍵2-get(2)//返回-1(未找到)-put(4,4)//去除鍵1-get(1)//返回-1(未找到)-get(3)//返回3-get(4)//返回42.算法題（5題，每題15分）題目1問(wèn)題描述：給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，返回目標(biāo)值的索引。如果不存在，返回-1。你可以假設(shè)數(shù)組中不存在重復(fù)元素。要求：-時(shí)間復(fù)雜度O(logn)-可以使用二分查找算法示例：輸入：nums=[-1,0,3,5,9,12],target=9輸出：4題目2問(wèn)題描述：給定一個(gè)非空整數(shù)數(shù)組，返回其中出現(xiàn)次數(shù)超過(guò)一半的元素。要求：-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度O(1)示例：輸入：[3,2,3]輸出：3題目3問(wèn)題描述：給定一個(gè)包含非負(fù)整數(shù)的數(shù)組，返回其中三個(gè)數(shù)之和最接近給定的數(shù)target。要求：-時(shí)間復(fù)雜度O(n^2)-可以使用雙指針?lè)ㄊ纠狠斎耄簄ums=[1,2,4,8,9,19,20,21],target=37輸出：51(20+21+10)題目4問(wèn)題描述：給定一個(gè)字符串，判斷它是否是有效的括號(hào)字符串。要求：-可以使用棧來(lái)輔助判斷-時(shí)間復(fù)雜度O(n)示例：輸入："()[]{}"輸出：true題目5問(wèn)題描述：給定一個(gè)非空二叉樹(shù)，返回其最大深度。要求：-最大深度是指從根到最遠(yuǎn)葉節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)-可以使用遞歸或迭代方式示例：輸入：二叉樹(shù)`[3,9,20,null,null,15,7]`輸出：33.數(shù)據(jù)結(jié)構(gòu)與系統(tǒng)設(shè)計(jì)題（4題，每題20分）題目1問(wèn)題描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的LRU緩存系統(tǒng)。系統(tǒng)需要支持以下操作：-get(key)：獲取鍵key對(duì)應(yīng)的值，如果鍵不存在返回-1-put(key,value)：添加或更新鍵值對(duì)要求：-支持動(dòng)態(tài)擴(kuò)容-使用雙向鏈表和哈希表實(shí)現(xiàn)-時(shí)間復(fù)雜度O(1)題目2問(wèn)題描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的文件系統(tǒng)。系統(tǒng)需要支持以下操作：-create(path,name)：創(chuàng)建一個(gè)新文件或目錄-read(path)：讀取文件內(nèi)容-write(path,content)：寫(xiě)入文件內(nèi)容要求：-使用樹(shù)形結(jié)構(gòu)表示文件系統(tǒng)-支持多級(jí)目錄-時(shí)間復(fù)雜度O(n)題目3問(wèn)題描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的分布式緩存系統(tǒng)。系統(tǒng)需要支持以下操作：-get(key)：獲取鍵值-put(key,value)：添加或更新鍵值-delete(key)：刪除鍵值要求：-支持多個(gè)節(jié)點(diǎn)-使用一致性哈希算法-時(shí)間復(fù)雜度O(1)題目4問(wèn)題描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的消息隊(duì)列系統(tǒng)。系統(tǒng)需要支持以下操作：-publish(message)：發(fā)布消息-subscribe(topic)：訂閱主題-unsubscribe(topic)：取消訂閱主題要求：-支持多個(gè)主題-支持多個(gè)訂閱者-時(shí)間復(fù)雜度O(1)4.代碼調(diào)試與優(yōu)化題（3題，每題15分）題目1問(wèn)題描述：以下代碼存在錯(cuò)誤，請(qǐng)指出并修正。pythondeffactorial(n):ifn==0:return1returnfactorial(n)*n要求：-解釋錯(cuò)誤原因-提供修正后的代碼題目2問(wèn)題描述：以下代碼效率較低，請(qǐng)優(yōu)化。pythondeffind_duplicates(nums):duplicates=[]foriinrange(len(nums)):forjinrange(i+1,len(nums)):ifnums[i]==nums[j]:duplicates.append(nums[i])breakreturnduplicates要求：-解釋優(yōu)化思路-提供優(yōu)化后的代碼題目3問(wèn)題描述：以下代碼存在性能問(wèn)題，請(qǐng)優(yōu)化。javapublicList<String>findWords(List<String>words){List<String>result=newArrayList<>();for(Stringword:words){booleanisValid=true;charprev=0;for(charc:word.toCharArray()){if(prev!=0&&Character.toUpperCase(prev)!=Character.toUpperCase(c)){isValid=false;break;}prev=c;}if(isValid){result.add(word);}}returnresult;}要求：-解釋優(yōu)化思路-提供優(yōu)化后的代碼5.行為與系統(tǒng)設(shè)計(jì)題（2題，每題25分）題目1問(wèn)題描述：假設(shè)你要設(shè)計(jì)一個(gè)在線購(gòu)物平臺(tái)，請(qǐng)描述以下關(guān)鍵組件的設(shè)計(jì)思路：-用戶認(rèn)證系統(tǒng)-商品管理系統(tǒng)-購(gòu)物車(chē)系統(tǒng)-支付系統(tǒng)要求：-每個(gè)組件需要說(shuō)明核心功能-使用簡(jiǎn)潔的架構(gòu)圖或文字描述-考慮高可用性和可擴(kuò)展性題目2問(wèn)題描述：假設(shè)你要設(shè)計(jì)一個(gè)實(shí)時(shí)推薦系統(tǒng)，請(qǐng)描述以下關(guān)鍵組件的設(shè)計(jì)思路：-數(shù)據(jù)采集系統(tǒng)-數(shù)據(jù)處理系統(tǒng)-推薦算法-推薦接口要求：-每個(gè)組件需要說(shuō)明核心功能-使用簡(jiǎn)潔的架構(gòu)圖或文字描述-考慮實(shí)時(shí)性和準(zhǔn)確性答案編程實(shí)現(xiàn)題答案題目1答案pythondefreplace_spaces(s:str)->str:#計(jì)算空格數(shù)量space_count=s.count('')#創(chuàng)建足夠大的新字符串new_str=['']*(len(s)+space_count*2)#從后向前遍歷，避免覆蓋index=len(s)+space_count*2-1forcharinreversed(s):ifchar=='':new_str[index]='0'new_str[index-1]='2'new_str[index-2]='%'index-=3else:new_str[index]=charindex-=1return''.join(new_str)題目2答案python#遞歸方式definorder_traversal_recursive(root):ifnotroot:return[]returninorder_traversal_recursive(root.left)+[root.val]+inorder_traversal_recursive(root.right)#迭代方式definorder_traversal_iterative(root):stack,result=[],[]current=rootwhilestackorcurrent:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()result.append(current.val)current=current.rightreturnresult題目3答案pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres算法題答案題目1答案pythondefsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1題目2答案pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate題目3答案pythondefthree_sum_closest(nums,target):nums.sort()n=len(nums)closest_sum=float('inf')foriinrange(n-2):left,right=i+1,n-1whileleft<right:current_sum=nums[i]+nums[left]+nums[right]ifabs(current_sum-target)<abs(closest_sum-target):closest_sum=current_sumifcurrent_sum<target:left+=1elifcurrent_sum>target:right-=1else:returncurrent_sumreturnclosest_sum題目4答案pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping.values():stack.append(char)elifcharinmapping:ifnotstackorstack.pop()!=mapping[char]:returnFalseelse:returnFalsereturnnotstack題目5答案python#遞歸方式defmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))#迭代方式defmaxDepth_iterative(root):ifnotroot:return0stack=[(root,1)]max_depth=0whilestack:node,depth=stack.pop()ifnode:max_depth=max(max_depth,depth)stack.append((node.left,depth+1))stack.append((node.right,depth+1))returnmax_depth數(shù)據(jù)結(jié)構(gòu)與系統(tǒng)設(shè)計(jì)題答案題目1答案pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres題目2答案pythonclassFileSystem:def__init__(self):self.files={}self.directories={"/":{}}defcreate(self,path:str,name:str)->None:parts=path.split('/')current=self.directories["/"]forpartinparts[1:]:ifpartnotincurrent:current[part]={}current=current[part]current[name]=""defread(self,path:str)->str:parts=path.split('/')current=self.directories["/"]forpartinparts[1:]:ifpartnotincurrent:return""current=current[part]returncurrent.get("","")defwrite(self,path:str,content:str)->None:parts=path.split('/')current=self.directories["/"]forpartinparts[1:-1]:ifpartnotincurrent:current[part]={}current=current[part]current[parts[-1]]=content題目3答案pythonclassDistributedCache:def__init__(self,nodes):self.nodes=nodesself.hash_map={}self.node_map=self._consistent_hashing(nodes)def_consistent_hashing(self,nodes):node_map={}fornodeinnodes:node_map[node]=self._hash(node)returnnode_mapdef_hash(self,key):returnhash(key)%256defget(self,key):node=self.node_map[self._hash(key)]returnself.nodes[node].get(key,None)defput(self,key,value):node=self.node_map[self._hash(key)]self.nodes[node][key]=valuedefdelete(self,key):node=self.node_map[self._hash(key)]ifkeyinself.nodes[node]:delself.nodes[node][key]題目4答案pythonclassMessageQueue:def__init__(self):self.topics={}self.subscribers={}defpublish(self,topic:str,message:str)->None:iftopicnotinself.topics:self.topics[topic]=[]forsubscriberinself.topics[topic]:subscriber.append(message)defsubscribe(self,topic:str,subscriber:str)->None:iftopicnotinself.topics:self.topics[topic]=[]ifsubscribernotinself.subscribers:self.subscribers[subscriber]=set()self.subscribers[subscriber].add(topic)self.topics[topic].append(subscriber)defunsubscribe(self,topic:str,subscriber:str)->None:iftopicinself.topics:ifsubscriberinself.topics[topic]:self.topics[topic].remove(subscriber)ifsubscriberinself.subscribers:iftopicinself.subscribers[subscriber]:self.subscribers[subscriber].remove(topic)代碼調(diào)試與優(yōu)化題答案題目1答案pythondeffactorial(n):ifn==0:return1returnfactorial(n-1)*n題目2答案pythondeffind_duplicates(nums):nums.sort()duplicates=[]foriinrange(1,len(nums)):ifnums[i]==nums[i-1]and(notduplicatesorduplicates[-1]!=nums[i]):duplicates.append(nums[i])returnduplicates題目3答案javapublicList<String>findWords(List<String>words){List<String>result=newArrayList<>();for(Stringword:words){booleanisValid=true;charprev=Character.toUpperCase(word.charAt(0));for(inti=1;i<word.length();i++){charc=Character.toUpperCase(word.charAt(i));if(c!=prev){isValid=false;break;}prev=c;}if(isValid){result.add(word);}}returnresult;}行為與系統(tǒng)設(shè)計(jì)題答案題目1答案plaintext用戶認(rèn)證系統(tǒng)：-功能：用戶注冊(cè)、登錄、密碼找回、權(quán)限管理-架構(gòu)：使用JWT進(jìn)行無(wú)狀態(tài)認(rèn)證，結(jié)合OAuth2.0協(xié)議-關(guān)鍵組件：用戶數(shù)據(jù)庫(kù)、認(rèn)證服務(wù)、令牌服務(wù)商品管理系統(tǒng)：-功能：商品分類(lèi)、商品信息管理、庫(kù)存管理-架構(gòu)：使用RESTfulAPI設(shè)計(jì)，支持分頁(yè)查詢-關(guān)鍵組件：商品數(shù)據(jù)庫(kù)、商品服務(wù)、緩存服務(wù)購(gòu)物車(chē)系統(tǒng)：-功能：添加商品、修改數(shù)量、刪除商品、結(jié)算-架構(gòu)：使用Redis緩存購(gòu)物車(chē)數(shù)據(jù)，支持分布式