2026年程序員面試筆試經驗一、編程語言基礎（5題，每題10分，共50分）1.題目：在Python中，編寫一個函數`merge_sorted_lists`，輸入兩個已排序的鏈表（鏈表節(jié)點定義如下），返回合并后的新鏈表。要求不使用額外的存儲空間，時間復雜度為O(n)。pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmerge_sorted_lists(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.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next解析：采用虛擬頭節(jié)點`dummy`簡化邊界處理，雙指針遍歷兩個鏈表，逐個比較節(jié)點值并按順序連接。不使用額外空間，時間復雜度為O(n)，空間復雜度為O(1)。2.題目：在Java中，實現一個方法`reverse_string`，將輸入的字符串原地反轉（不使用額外字符串變量）。答案：javapublicclassSolution{publicStringreverse_string(Strings){char[]arr=s.toCharArray();intleft=0,right=s.length()-1;while(left<right){chartemp=arr[left];arr[left]=arr[right];arr[right]=temp;left++;right--;}returnnewString(arr);}}解析：將字符串轉為字符數組，雙指針從首尾向中間遍歷并交換字符。原地修改，不占用額外空間，時間復雜度為O(n)。3.題目：在C++中，編寫一個函數`find_first_unique_char`，輸入一個字符串，返回第一個不重復字符的索引，若不存在返回-1。答案：cppinclude<vector>include<string>usingnamespacestd;intfind_first_unique_char(conststring&s){vector<int>freq(256,0);for(charc:s){freq[c]++;}for(inti=0;i<s.size();i++){if(freq[s[i]]==1)returni;}return-1;}解析：使用哈希表統計字符頻率，遍歷字符串時查找第一個頻率為1的字符。時間復雜度為O(n)，空間復雜度為O(1)（哈希表大小固定為256）。4.題目：在JavaScript中，實現一個函數`flatten_nested_array`，輸入一個嵌套數組，返回一個一維扁平數組。要求不使用內置的`flat`方法。答案：javascriptfunctionflatten_nested_array(arr){letresult=[];functionflatten(subArr){for(letitemofsubArr){if(Array.isArray(item)){flatten(item);}else{result.push(item);}}}flatten(arr);returnresult;}解析：采用遞歸方式處理嵌套數組，每次遍歷子數組時判斷是否為嵌套數組，若是則繼續(xù)遞歸，否則添加到結果數組中。時間復雜度為O(n)，空間復雜度為O(n)（遞歸棧和結果數組）。5.題目：在Go中，編寫一個函數`count_primes`，輸入一個正整數n，返回小于等于n的質數數量。答案：gopackagemainimport"fmt"funccount_primes(nint)int{ifn<2{return0}count:=1//2是第一個質數sieve:=make([]bool,n+1)fori:=3;i<=n;i+=2{if!sieve[i]{count++forj:=ii;j<=n;j+=i2{sieve[j]=true}}}returncount}解析：采用篩法統計質數數量，初始化布爾數組`sieve`標記非質數，從3開始遍歷奇數，跳過偶數（除了2）。時間復雜度為O(n√n)，空間復雜度為O(n)。二、數據結構與算法（5題，每題10分，共50分）1.題目：設計一個LRU（LeastRecentlyUsed）緩存，支持`get`和`put`操作。使用哈希表+雙向鏈表實現，要求`get`和`put`的時間復雜度為O(1)。答案：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:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)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.prevnext:=node.nextprev.next=nextnext.prev=prevdef_pop_tail(self):res:=self.tail.prevself._remove_node(res)returnres解析：LRU緩存的核心是雙向鏈表+哈希表。鏈表頭部為最近使用節(jié)點，尾部為最久未使用節(jié)點。`get`操作將節(jié)點移動到頭部，`put`操作插入新節(jié)點并淘汰最久未使用節(jié)點（若超出容量）。所有操作均通過哈希表實現O(1)時間復雜度。2.題目：給定一個無重復字符的字符串`s`和一個目標字符串`p`，返回所有`p`在`s`中的起始索引（子串需連續(xù)）。要求時間復雜度為O(n)。答案：pythondeffind_substring(s:str,p:str)->list:ifnotpornots:return[]len_p,len_s:=len(p),len(s)p_count,s_count:=[0]26,[0]26forcinp:p_count[ord(c)-ord('a')]+=1result=[]foriinrange(len_s-len_p+1):forjinrange(len_p):s_count[ord(s[i+j])-ord('a')]+=1ifs_count==p_count:result.append(i)s_count=[0]26returnresult解析：采用滑動窗口方法，分別統計目標串`p`和滑動窗口內字符的頻率數組。每次滑動時更新頻率數組并比較，若相等則記錄起始索引。時間復雜度為O(n)，空間復雜度為O(1)（哈希表大小固定為26）。3.題目：給定一個數組`nums`，返回所有可能的子集（不包含重復子集）。答案：pythondefsubsets(nums):res=[]nums.sort()defbacktrack(start,path):res.append(path.copy())foriinrange(start,len(nums)):path.append(nums[i])backtrack(i+1,path)path.pop()backtrack(0,[])returnres解析：采用回溯算法，排序數組去重，通過遞歸枚舉所有子集。每次選擇當前元素或跳過，確保不重復。時間復雜度為O(2^n)，空間復雜度為O(n)（遞歸棧）。4.題目：設計一個`MinStack`，支持`push`、`pop`、`top`和`getMin`操作。要求`getMin`的時間復雜度為O(1)。答案：pythonclassMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,val:int)->None:self.stack.append(val)ifnotself.min_stackorval<=self.min_stack[-1]:self.min_stack.append(val)defpop(self)->int:ifnotself.stack:returnNonetop:=self.stack.pop()iftop==self.min_stack[-1]:self.min_stack.pop()returntopdeftop(self)->int:ifnotself.stack:returnNonereturnself.stack[-1]defgetMin(self)->int:ifnotself.min_stack:returnNonereturnself.min_stack[-1]解析：使用兩個棧實現：主棧`stack`存儲所有元素，輔助棧`min_stack`存儲當前最小值。`push`時若新元素小于等于`min_stack`棧頂，則將其也壓入`min_stack`；`pop`時若彈出元素等于`min_stack`棧頂，則同時彈出`min_stack`棧頂。`getMin`直接返回`min_stack`棧頂。所有操作均O(1)。5.題目：給定一個整數`n`，判斷其是否為完全平方數。答案：pythondefis_perfect_square(n:int)->bool:ifn<2:returnTrueleft,right:=2,n//2whileleft<=right:mid:=left+(right-left)//2square:=midmidifsquare==n:returnTrueelifsquare<n:left=mid+1else:right=mid-1returnFalse解析：采用二分查找法，在[2,n/2]區(qū)間內查找平方根。每次計算中間值平方并與n比較，調整左右邊界。時間復雜度為O(logn)，空間復雜度為O(1)。三、系統設計（2題，每題25分，共50分）1.題目：設計一個短鏈接服務（如TinyURL），要求：-輸入任意長URL，返回固定長度短鏈接。-支持通過短鏈接反查原始URL。-支持高并發(fā)訪問。答案：核心思路：1.URL編碼：將原始URL哈希為固定長度的短碼（如6位62進制字符）。2.分布式存儲：使用哈希表+分布式緩存（如RedisCluster）存儲短碼與原始URL映射。3.高并發(fā)優(yōu)化：-使用異步寫入緩存。-熔斷限流，防雪崩。4.反查服務：通過短碼查詢緩存，若未命中則反查數據庫。偽代碼示例：pythondefencode_url(url):hash_code:=hash(url)short_code:=to_base62(hash_code,6)redis.set(short_code,url)return"/"+short_codedefdecode_url(short_code):url=redis.get(short_code)ifnoturl:url=db.query(short_code)redis.set(short_code,url)returnurldefto_base62(num,length):base62:="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"result:=""whilenum>0:result=base62[num%62]+resultnum=num//62returnresult.rjust(length,'0')解析：-URL編碼：哈希函數需保證唯一性，可使用MD5+隨機前綴防沖突。-分布式存儲：RedisCluster分片存儲，支持百萬級并發(fā)。-高并發(fā)優(yōu)化：異步寫入+本地緩存（如Memcached）降低Redis壓力。-容錯性：數據庫備份+定期遷移舊數據到冷存儲。2.題目：設計一個實時聊天系統，要求：-支持多用戶實時收發(fā)消息。-支持離線消息推送。-支持消息已讀回執(zhí)。答案：核心思路：1.消息存儲：-使用關系型數據庫（如PostgreSQL）存儲消息記錄（發(fā)送者、接收者、時間、已讀狀態(tài)）。-離線消息暫存Redis隊列，用戶上線后同步。2.實時通信：-WebSocket長連接，客戶端主動拉取未讀消息。-服務器端使用消息隊列（如RabbitMQ）異步處理消息分發(fā)。3.已讀回執(zhí)：-用戶讀取消息時更新數據庫已讀狀態(tài)。-WebSocket推送已讀事件給發(fā)送者。偽代碼示例：pythonWebSocket連接處理defon_m