2026年軟件開發(fā)工程師編程面試題及答案一、編程基礎(chǔ)（共5題，每題10分，總分50分）1.題目：請實現(xiàn)一個函數(shù)，輸入一個正整數(shù)`n`，返回`n`的二進(jìn)制表示中`1`的個數(shù)。例如，輸入`11`，輸出`3`（因為`11`的二進(jìn)制表示為`1011`）。答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount解析：使用位運(yùn)算高效統(tǒng)計`1`的個數(shù)。`n&1`檢查最低位是否為`1`，`n>>=1`將`n`右移一位。時間復(fù)雜度為O(logn)。2.題目：給定一個字符串`s`，請判斷它是否是一個有效的括號組合。例如，輸入`"(())"`，返回`True`；輸入`"()[]{}"`，返回`True`；輸入`"([)]"`，返回`False`。答案：pythondefisValid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：使用棧結(jié)構(gòu)，遇到右括號時與棧頂左括號匹配。若棧為空或棧頂不匹配，則無效。時間復(fù)雜度為O(n)。3.題目：請實現(xiàn)一個函數(shù)，輸入一個鏈表的頭節(jié)點`head`，返回其反轉(zhuǎn)后的鏈表。例如，輸入`1->2->3`，輸出`3->2->1`。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：迭代反轉(zhuǎn)鏈表，維護(hù)三個指針：`prev`、`current`、`next_node`。時間復(fù)雜度為O(n)。4.題目：給定一個數(shù)組`nums`，請返回其中和為`target`的兩個數(shù)的下標(biāo)。例如，輸入`nums=[2,7,11,15]`,`target=9`，輸出`[0,1]`（因為`2+7=9`）。答案：pythondeftwoSum(nums,target):num_to_index={}fori,numinenumerate(nums):complement=target-numifcomplementinnum_to_index:return[num_to_index[complement],i]num_to_index[num]=ireturn[]解析：使用哈希表記錄每個數(shù)的索引，時間復(fù)雜度為O(n)。5.題目：請實現(xiàn)一個函數(shù)，輸入一個字符串`s`，返回其最長回文子串的長度。例如，輸入`"babad"`，輸出`3`（"bab"或"aba"）。答案：pythondeflongestPalindrome(s):ifnots:return0start,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//2returnend-start+1defexpandAroundCenter(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：中心擴(kuò)展法，分別考慮奇數(shù)和偶數(shù)長度的回文。時間復(fù)雜度為O(n2)。二、算法設(shè)計（共5題，每題15分，總分75分）6.題目：設(shè)計一個LRU（最近最少使用）緩存，支持`get`和`put`操作。`get(key)`返回`key`對應(yīng)的值，若不存在返回`-1`；`put(key,value)`將鍵值對插入緩存，如果鍵已存在，則更新其值。當(dā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_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)解析：使用哈希表存儲鍵值對，雙向鏈表維護(hù)訪問順序。`get`時將鍵移到尾部，`put`時若容量滿則刪除頭部元素。時間復(fù)雜度為O(1)。7.題目：給定一個非負(fù)整數(shù)`n`，生成所有可能的括號組合。例如，輸入`3`，輸出`["((()))","(()())","(())()","()(())","()()()"]`。答案：pythondefgenerateParenthesis(n):result=[]defbacktrack(left=0,right=0,s=""):iflen(s)==2n:result.append(s)returnifleft<n:backtrack(left+1,right,s+"(")ifright<left:backtrack(left,right+1,s+")")backtrack()returnresult解析：回溯法，限制左括號數(shù)量不超過`n`，右括號數(shù)量不超過左括號。時間復(fù)雜度為O(4^n/√n)。8.題目：給定一個包含`0`和`1`的二維網(wǎng)格`grid`，找出其中最大的正方形，并返回其面積。例如，輸入`[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]`，輸出`4`。答案：pythondefmaximalSquare(matrix):ifnotmatrix:return0m,n=len(matrix),len(matrix[0])dp=[[0](n+1)for_inrange(m+1)]max_side=0foriinrange(1,m+1):forjinrange(1,n+1):ifmatrix[i-1][j-1]=='1':dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1max_side=max(max_side,dp[i][j])returnmax_sidemax_side解析：動態(tài)規(guī)劃，`dp[i][j]`表示以`(i-1,j-1)`為右下角的正方形邊長。時間復(fù)雜度為O(mn)。9.題目：設(shè)計一個算法，判斷一個無向圖是否是二分圖。二分圖是指可以將圖分成兩個不相交的集合，使得每條邊的兩個頂點分別屬于不同的集合。答案：pythondefisBipartite(graph):color={}fornodeingraph:ifnodenotincolor:stack=[node]color[node]=0whilestack:current=stack.pop()forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=1-color[current]stack.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTrue解析：使用深度優(yōu)先搜索（DFS）進(jìn)行著色，若遇到相鄰節(jié)點顏色相同則不是二分圖。時間復(fù)雜度為O(V+E)。10.題目：給定一個整數(shù)數(shù)組`nums`，請返回其中第三大的數(shù)。如果不存在，返回最大數(shù)。例如，輸入`[3,2,1,5,6,4]`，輸出`5`；輸入`[1,2]`，輸出`2`。答案：pythondefthirdMax(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst解析：維護(hù)三個變量記錄前三大的數(shù)，遍歷數(shù)組更新。時間復(fù)雜度為O(n)。三、系統(tǒng)設(shè)計（共5題，每題10分，總分50分）11.題目：設(shè)計一個簡單的URL緩存系統(tǒng)，支持`get`和`put`操作。`get(url)`返回對應(yīng)內(nèi)容，若不存在返回`""`；`put(url,content)`插入或更新URL及其內(nèi)容。當(dāng)緩存容量滿時，刪除最久未使用（LRU）的URL。答案：pythonclassURLCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,url:str)->str:ifurlinself.cache:self.order.remove(url)self.order.append(url)returnself.cache[url]return""defput(self,url:str,content:str)->None:ifurlinself.cache:self.order.remove(url)eliflen(self.cache)==self.capacity:oldest_url=self.order.pop(0)delself.cache[oldest_url]self.cache[url]=contentself.order.append(url)解析：與LRU緩存類似，使用哈希表存儲URL及其內(nèi)容，雙向鏈表維護(hù)訪問順序。時間復(fù)雜度為O(1)。12.題目：設(shè)計一個簡單的消息隊列系統(tǒng)，支持`publish`和`subscribe`操作。`publish(topic,message)`將消息發(fā)送到所有訂閱了該主題的客戶端；`subscribe(topic,client)`使客戶端訂閱一個主題。答案：pythonclassMessageQueue:def__init__(self):self.topics={}defpublish(self,topic:str,message:str)->None:iftopicinself.topics:forclientinself.topics[topic]:client.receive(message)defsubscribe(self,topic:str,client)->None:iftopicnotinself.topics:self.topics[topic]=[]self.topics[topic].append(client)解析：使用哈希表存儲主題及其訂閱的客戶端列表。`publish`時遍歷所有訂閱者發(fā)送消息。時間復(fù)雜度為O(n)（n為訂閱者數(shù)量）。13.題目：設(shè)計一個簡單的分布式鎖服務(wù)，支持`lock`和`unlock`操作。`lock()`獲取鎖，若已鎖定則阻塞等待；`unlock()`釋放鎖。答案：pythonimportthreadingclassDistributedLock:def__init__(self):self.lock=threading.Lock()deflock(self):self.lock.acquire()defunlock(self):self.lock.release()解析：使用Python的`threading.Lock`實現(xiàn)簡單分布式鎖。注意：實際分布式鎖需結(jié)合Redis或ZooKeeper等中間件。時間復(fù)雜度為O(1)。14.題目：設(shè)計一個簡單的計數(shù)器系統(tǒng)，支持`increment`和`get_value`操作。`increment()`遞增計數(shù)器；`get_value()`返回當(dāng)前值。答案：pythonimportthreadingclassCounter:def__init__(self):self.value=0self.lock=threading.Lock()defincrement(self):withself.lock:self.value+=1defget_value(self):withself.lock:returnself.value解析：使用互斥鎖保證線程安全。時間復(fù)雜度為O(1)。15.題目：設(shè)計一個簡單的限流器，限制每個用戶每秒最多訪問`N`次。例如，`N=5`，用戶`A`在`1`秒內(nèi)最多訪問`5`次。答案：pythonfromcollectionsimportdequeclassRateLimiter:def__init__(self,limit:int):self.limit=limitself.history={}defis_allowed(self,user_id:str)->bool:current_time=time.time()ifuser_idnotinself.history:self.history[user_id]=d