2026年軟件工程師崗位面試題庫及答案參考一、編程語言基礎(chǔ)（共5題，每題10分）題目1（Java）java請編寫一個Java方法，實現(xiàn)將一個字符串中的所有空格替換為%20。要求：不使用內(nèi)置的替換方法，時間復雜度為O(n)。題目2（Python）python請寫一個Python函數(shù)，判斷一個字符串是否為回文（正讀和反讀相同）。例如："madam"是回文，"hello"不是。要求：不使用反轉(zhuǎn)字符串的方法。題目3（C++）cpp請實現(xiàn)一個C++函數(shù)，計算一個整數(shù)的二進制表示中1的個數(shù)。例如：5的二進制是101，返回2。題目4（JavaScript）javascript請編寫一個JavaScript函數(shù)，找出數(shù)組中所有唯一的數(shù)字（出現(xiàn)次數(shù)為1的數(shù)字）。例如：在[1,2,2,3,4,4,5]中，返回[1,3,5]。題目5（Go）go請用Go語言實現(xiàn)一個函數(shù)，檢查一個字符串是否包含所有長度為n的子串。例如：輸入字符串"abcabcbb"和n=3，返回true（包含"abc","bca","cab"）。答案與解析答案1（Java）javapublicclassReplaceSpace{publicstaticStringreplaceSpaces(Strings){if(s==null)returnnull;char[]chars=s.toCharArray();intspaceCount=0;//首先統(tǒng)計空格數(shù)量for(charc:chars){if(c=='')spaceCount++;}char[]newChars=newchar[chars.length+spaceCount2];intindex=0;for(charc:chars){if(c==''){newChars[index++]='%';newChars[index++]='2';newChars[index++]='0';}else{newChars[index++]=c;}}returnnewString(newChars,0,index);}publicstaticvoidmain(String[]args){System.out.println(replaceSpaces("Wearehappy."));//"We%20are%20happy."}}解析：通過兩次遍歷實現(xiàn)：首先統(tǒng)計空格數(shù)量，然后創(chuàng)建足夠大的數(shù)組進行替換。時間復雜度O(n)，空間復雜度O(n)。答案2（Python）pythondefis_palindrome(s):left,right=0,len(s)-1whileleft<right:跳過非字母數(shù)字字符whileleft<rightandnots[left].isalnum():left+=1whileleft<rightandnots[right].isalnum():right-=1比較字符ifs[left].lower()!=s[right].lower():returnFalseleft+=1right-=1returnTrue測試print(is_palindrome("Aman,aplan,acanal:Panama"))#Trueprint(is_palindrome("raceacar"))#False解析：雙指針法，從兩頭向中間比較，忽略大小寫和非字母數(shù)字字符。時間復雜度O(n)。答案3（C++）cppinclude<iostream>include<bitset>intcountOnes(intnum){bitset<32>bits(num);returnbits.count();}//或者不使用bitsetintcountOnesAlt(intnum){intcount=0;while(num!=0){count+=num&1;num>>=1;}returncount;}intmain(){std::cout<<countOnes(5)<<std::endl;//輸出2std::cout<<countOnesAlt(5)<<std::endl;//輸出2return0;}解析：位運算方法，每次與1做與運算統(tǒng)計1的個數(shù)，然后右移一位繼續(xù)統(tǒng)計。時間復雜度O(1)（32位整數(shù)）。答案4（JavaScript）javascriptfunctionfindUniques(arr){constcountMap={};arr.forEach(num=>{countMap[num]=(countMap[num]||0)+1;});returnObject.keys(countMap).filter(key=>countMap[key]===1).map(Number);}//測試console.log(findUniques([1,2,2,3,4,4,5]));//[1,3,5]解析：使用哈希表統(tǒng)計每個數(shù)字的出現(xiàn)次數(shù)，然后篩選出現(xiàn)次數(shù)為1的數(shù)字。時間復雜度O(n)。答案5（Go）gofunccontainsAllSubstrings(sstring,nint)bool{ifn<=0||len(s)<n{returnfalse}needed:=make(map[string]bool)fori:=0;i<=len(s)-n;i++{substr:=s[i:i+n]needed[substr]=true}returnlen(needed)==len(s)-n+1}//測試fmt.Println(containsAllSubstrings("abcabcbb",3))//true解析：滑動窗口方法，遍歷所有長度為n的子串并記錄，如果記錄的子串數(shù)量等于總可能數(shù)量(len(s)-n+1)，則返回true。時間復雜度O(n)。二、數(shù)據(jù)結(jié)構(gòu)與算法（共8題，每題12分）題目6（鏈表）plaintext請實現(xiàn)一個功能：刪除鏈表中重復的元素，使得每個元素只保留一次。要求：不使用額外的空間，時間復雜度為O(n)。題目7（樹）plaintext給定一個二叉搜索樹，找出其最小值和最大值。要求：不使用遞歸，時間復雜度為O(h)。題目8（哈希表）plaintext請設(shè)計一個LRU（最近最少使用）緩存。要求：支持get和put操作，時間復雜度為O(1)。題目9（動態(tài)規(guī)劃）plaintext斐波那契數(shù)列：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)。請實現(xiàn)一個函數(shù)計算F(n)，要求時間復雜度為O(logn)。題目10（排序算法）plaintext比較歸并排序和快速排序的優(yōu)缺點，并說明在什么情況下選擇哪種排序算法更合適。題目11（圖算法）plaintext請實現(xiàn)Dijkstra算法，找出從起點到所有點的最短路徑。要求：使用優(yōu)先隊列實現(xiàn)。題目12（字符串算法）plaintext請實現(xiàn)KMP（Knuth-Morris-Pratt）算法的搜索函數(shù)，找出模式串在主串中的位置。題目13（貪心算法）plaintext給定一個整數(shù)數(shù)組，表示天平上的砝碼重量。請判斷是否可以用這些砝碼平衡天平。如果是，請給出一種平衡方案。答案與解析答案6（鏈表）javapublicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}publicListNodedeleteDuplicates(ListNodehead){ListNodecurrent=head;while(current!=null){ListNodenextDistinct=current.next;while(nextDistinct!=null&&nextDistinct.val==current.val){nextDistinct=nextDistinct.next;}current.next=nextDistinct;current=current.next;}returnhead;}解析：不使用額外空間，遍歷鏈表時直接刪除重復節(jié)點。時間復雜度O(n)。答案7（樹）pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeffindMinMax(root):ifnotroot:returnNone,Nonemin_node=rootmax_node=rootqueue=[root]whilequeue:node=queue.pop(0)ifnode.val<min_node.val:min_node=nodeifnode.val>max_node.val:max_node=nodeifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnmin_node.val,max_node.val解析：BFS遍歷二叉樹，同時記錄最小和最大值。時間復雜度O(n)。答案8（哈希表）pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=self.Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：使用雙向鏈表和哈希表實現(xiàn)，get時移動到頭部，put時檢查容量，時間復雜度O(1)。答案9（動態(tài)規(guī)劃）pythondeffib(n):ifn==0:return0ifn==1:return1a,b=0,1for_inrange(2,n+1):a,b=b,a+breturnb解析：迭代法實現(xiàn)斐波那契數(shù)列，時間復雜度O(n)。更高效的O(logn)解法需要矩陣快速冪或通項公式。答案10（排序算法）plaintext歸并排序：優(yōu)點：穩(wěn)定排序，時間復雜度O(nlogn)，適合外部排序，對數(shù)據(jù)分布不敏感缺點：需要額外空間O(n)，最壞情況下時間復雜度仍為O(nlogn)快速排序：優(yōu)點：平均時間復雜度O(nlogn)，原地排序，空間復雜度O(logn)缺點：不穩(wěn)定排序，最壞情況下時間復雜度O(n^2)，對數(shù)據(jù)分布敏感選擇：-當需要穩(wěn)定排序且內(nèi)存足夠時，選擇歸并排序-當內(nèi)存有限或需要平均性能時，選擇快速排序-對于小規(guī)模數(shù)據(jù)，插入排序可能更優(yōu)-對于幾乎已排序的數(shù)據(jù)，歸并排序更優(yōu)答案11（圖算法）pythonimportheapqdefdijkstra(graph,start):distances={vertex:float('infinity')forvertexingraph}distances[start]=0priority_queue=[(0,start)]whilepriority_queue:current_distance,current_vertex=heapq.heappop(priority_queue)ifcurrent_distance>distances[current_vertex]:continueforneighbor,weightingraph[current_vertex].items():distance=current_distance+weightifdistance<distances[neighbor]:distances[neighbor]=distanceheapq.heappush(priority_queue,(distance,neighbor))returndistances解析：使用優(yōu)先隊列實現(xiàn)Dijkstra算法，每次選擇距離最小的節(jié)點。時間復雜度O((E+V)logV)。答案12（字符串算法）pythondefkmpSearch(text,pattern):構(gòu)建部分匹配表defbuildLPS(pattern):lps=[0]len(pattern)length=0i=1whilei<len(pattern):ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlpslps=buildLPS(pattern)i=j=0whilei<len(text):ifpattern[j]==text[i]:i+=1j+=1ifj==len(pattern):returni-j#找到匹配，返回起始位置j=lps[j-1]elifi<len(text)andpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1return-1#未找到匹配解析：KMP算法通過部分匹配表避免重復比較。時間復雜度O(m+n)。答案13（貪心算法）pythondefcanBalance(weights):total=sum(weights)current=0forweightinweights:current+=weightifcurrent==total-current:returnTruereturnFalsedeffindBalance(weights):ifnotcanBalance(weights):returnNonetotal=sum(weights)current=0left=[]right=weights.copy()forweightinweights:current+=weightleft.append(weight)right.remove(weight)ifcurrent==total-current:returnleft,rightreturnNone解析：貪心算法檢查總和是否可以平分，然后嘗試找到分割點。時間復雜度O(n)。三、系統(tǒng)設(shè)計（共4題，每題15分）題目14（分布式系統(tǒng)）plaintext請設(shè)計一個高可用的分布式計數(shù)器系統(tǒng)。要求：支持高并發(fā)訪問，支持分布式部署，能夠處理故障。題目15（數(shù)據(jù)庫設(shè)計）plaintext設(shè)計一個電商訂單系統(tǒng)數(shù)據(jù)庫。需要包含訂單、商品、用戶、地址等實體，并說明關(guān)鍵字段和索引。題目16（微服務(wù)）plaintext請設(shè)計一個短鏈接服務(wù)。要求：支持自定義短鏈接，支持統(tǒng)計點擊量，高可用。題目17（網(wǎng)絡(luò)協(xié)議）plaintext請解釋TCP和UDP的區(qū)別，并說明在什么場景下選擇TCP，什么場景下選擇UDP。答案與解析答案14（分布式系統(tǒng)）plaintext設(shè)計分布式計數(shù)器系統(tǒng)：1.架構(gòu)：-使用Redis或ZooKeeper作為分布式鎖或協(xié)調(diào)服務(wù)-每個節(jié)點維護本地計數(shù)，定期同步到中央服務(wù)器-使用Raft或Paxos算法保證一致性2.實現(xiàn)要點：-每個節(jié)點啟動時從中央服務(wù)器拉取最新計數(shù)-增加計數(shù)時使用分布式鎖確保原子性-定期的心跳機制檢測節(jié)點健康狀態(tài)-使用分片(sharding)技術(shù)分散負載3.處理故障：-使用領(lǐng)導者選舉算法自動處理節(jié)點故障-使用副本機制保證數(shù)據(jù)不丟失-使用熔斷器防止故障擴散4.性能優(yōu)化：-使用本地緩存減少中央服務(wù)器負載-使用異步更新機制提高吞吐量-使用批量操作減少網(wǎng)絡(luò)開銷答案15（數(shù)據(jù)庫設(shè)計）plaintext電商訂單系統(tǒng)數(shù)據(jù)庫設(shè)計：1.實體關(guān)系圖：-用戶(User):id,name,email,phone,address,created_at-商品(Product):id,name,price,stock,category,created_at-訂單(Order):id,user_id,total_amount,status,created_at-訂單項(OrderItem):order_id,product_id,quantity,price-地址(Address):id,user_id,street,city,zip,