2026年高級程序員面試寶典：編程題及答案解析一、算法設(shè)計（3題，每題20分）1.題目（15分）：給定一個無重復(fù)元素的整數(shù)數(shù)組，返回其所有可能的子集。示例輸入：`[1,2,3]`示例輸出：`[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]`要求：-不能使用遞歸或回溯算法。-時間復(fù)雜度盡可能低。2.題目（25分）：設(shè)計一個LRU（最近最少使用）緩存，支持以下操作：-`get(key)`：獲取鍵`key`對應(yīng)的值，如果不存在返回-1。-`put(key,value)`：插入或更新鍵值對。當緩存容量滿時，刪除最近最少使用的元素。示例：-初始化容量為2的LRU緩存。-`put(1,1)`→緩存為`{1:1}`。-`put(2,2)`→緩存為`{1:1,2:2}`。-`get(1)`→返回1。-`put(3,3)`→哈希表為`{1:1,3:3}`，刪除鍵2。-`get(2)`→返回-1。要求：-使用哈希表和雙向鏈表實現(xiàn)，時間復(fù)雜度為O(1)。3.題目（20分）：給定一個排序數(shù)組，找出其中重復(fù)的數(shù)字，但數(shù)組中最多只有兩個重復(fù)的數(shù)字。示例輸入：`[1,2,3,3,4,4,5]`示例輸出：`[3,4]`（順序不重要）要求：-不能使用額外空間。-時間復(fù)雜度O(n)。二、系統(tǒng)設(shè)計（2題，每題30分）1.題目（30分）：設(shè)計一個簡單的微博系統(tǒng)，支持以下功能：-用戶發(fā)布微博（包含文本、時間戳、用戶ID）。-用戶關(guān)注其他用戶。-用戶獲取關(guān)注者的最新微博（最多顯示10條）。要求：-描述核心數(shù)據(jù)結(jié)構(gòu)。-說明如何實現(xiàn)高并發(fā)下的數(shù)據(jù)一致性。-簡述如何支持百萬級用戶。2.題目（30分）：設(shè)計一個短鏈接生成服務(wù)，要求：-輸入長鏈接，輸出6位隨機短鏈接（如`/abc123`）。-短鏈接唯一且可逆。-高并發(fā)場景下仍能快速響應(yīng)。要求：-說明短鏈接的生成算法。-如何解決重復(fù)問題？-如何保證高可用性？三、數(shù)據(jù)庫與存儲（2題，每題25分）1.題目（25分）：設(shè)計一個電商訂單表，包含以下字段：-`order_id`（主鍵，自增）-`user_id`（用戶ID，索引）-`product_id`（商品ID，索引）-`quantity`（數(shù)量）-`total_price`（總價）-`order_time`（下單時間，索引）要求：-說明字段設(shè)計理由。-編寫SQL查詢：按用戶ID分組統(tǒng)計訂單總金額，時間范圍在過去30天。2.題目（25分）：假設(shè)你需要存儲一個大型文件（如1GB），如何設(shè)計存儲方案？要求：-分片存儲還是對象存儲？-如何保證數(shù)據(jù)可靠性和訪問速度？-是否需要緩存？如何設(shè)計緩存策略？四、并發(fā)與分布式（2題，每題25分）1.題目（25分）：在分布式環(huán)境下，如何保證數(shù)據(jù)庫事務(wù)的原子性、一致性、隔離性和持久性（ACID）？要求：-說明分布式事務(wù)的解決方案（如2PC或TCC）。-比較兩種方案的優(yōu)缺點。2.題目（25分）：設(shè)計一個高并發(fā)的秒殺系統(tǒng)，要求：-防止超賣。-降低數(shù)據(jù)庫壓力。要求：-說明核心邏輯（如Redis+Lua腳本）。-如何處理系統(tǒng)雪崩問題？五、代碼實現(xiàn)（3題，每題15分）1.題目（15分）：實現(xiàn)一個簡單的LRU緩存，使用Python或Java。要求：-使用雙向鏈表和哈希表。-提供`get`和`put`方法。2.題目（15分）：實現(xiàn)快速排序算法，要求：-手寫代碼，不能使用內(nèi)置函數(shù)。-處理重復(fù)元素的情況。3.題目（15分）：實現(xiàn)一個簡單的消息隊列，支持：-生產(chǎn)者發(fā)送消息。-消費者接收消息。要求：-使用Python，可使用`queue.Queue`。-說明如何保證消息不丟失。答案與解析一、算法設(shè)計1.子集問題思路：迭代法。從空集開始，依次添加每個元素，生成新的子集。pythondefsubsets(nums):res=[[]]fornuminnums:res+=[curr+[num]forcurrinres]returnres解析：-第一步：`res=[[]]`。-第二步：`num=1`，`res=[[]]+[[1]]=[[],[1]]`。-第三步：`num=2`，`res=[[],[1]]+[[2],[1,2]]=[[],[1],[2],[1,2]]`。-依此類推。時間復(fù)雜度O(2^n)，空間復(fù)雜度O(2^n)。2.LRU緩存思路：使用哈希表記錄鍵值對，雙向鏈表記錄訪問順序。pythonclassNode: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=Node(),Node()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=Node(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=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres解析：-使用雙向鏈表維護訪問順序，頭為最近使用，尾為最久未使用。-哈希表實現(xiàn)O(1)時間復(fù)雜度的查找。-`put`時，如果超出容量，刪除鏈表尾部節(jié)點。3.重復(fù)數(shù)字思路：排序后遍歷，相鄰比較。pythondeffindDuplicates(nums):res=[]nums.sort()foriinrange(1,len(nums)):ifnums[i]==nums[i-1]:res.append(nums[i])whilei+1<len(nums)andnums[i]==nums[i+1]:i+=1returnres解析：-先排序，重復(fù)數(shù)字會相鄰。-避免重復(fù)添加同一個重復(fù)數(shù)字。時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(1)。二、系統(tǒng)設(shè)計1.微博系統(tǒng)核心數(shù)據(jù)結(jié)構(gòu)：-用戶表：`user_id`,`name`,`followed`（關(guān)注列表）。-微博表：`id`,`user_id`,`text`,`timestamp`,`likes`（使用Redis）。高并發(fā)處理：-使用Redis緩存熱點微博。-數(shù)據(jù)庫讀寫分離，主庫處理寫操作，從庫處理讀操作。-分布式鎖保證發(fā)微博時用戶在線狀態(tài)。百萬級支持：-微博分表（按時間或用戶ID）。-使用消息隊列（Kafka）異步處理點贊等操作。2.短鏈接生成算法：-使用62進制（a-z,A-Z,0-9）映射ID。-哈希函數(shù)：`hash(str)%1e12`生成12位數(shù)字。-轉(zhuǎn)換：數(shù)字轉(zhuǎn)62進制。防重復(fù)：-使用自增ID，沖突概率極低。-若沖突，重新哈希。高可用性：-負載均衡分發(fā)請求。-分布式緩存（Redis）存儲短鏈接映射。三、數(shù)據(jù)庫與存儲1.電商訂單表字段設(shè)計：-`order_id`：自增主鍵。-`user_id`：索引，用于快速查找用戶訂單。-`product_id`：索引，用于統(tǒng)計商品銷量。-`quantity`：整數(shù)。-`total_price`：浮點數(shù)。-`order_time`：索引，用于時間范圍查詢。SQL查詢：sqlSELECTuser_id,SUM(total_price)AStotal_amountFROMordersWHEREorder_time>=NOW()-INTERVAL30DAYGROUPBYuser_id;2.大文件存儲方案：對象存儲（如AWSS3）分片存儲。理由：-對象存儲支持海量文件，高并發(fā)訪問。-分片存儲提高容錯性。緩存策略：-熱文件放入CDN緩存。-冷文件使用Redis緩存元數(shù)據(jù)。四、并發(fā)與分布式1.分布式事務(wù)2PC方案：-準備階段：所有參與者事務(wù)準備，并鎖定資源。-提交階段：全部成功則提交，否則回滾。TCC方案：-Try階段：預(yù)占資源。-Confirm階段：確認操作。-Cancel階段：回滾操作。優(yōu)缺點：-2PC強一致性，但阻塞嚴重。-TCC靈活，但實現(xiàn)復(fù)雜。2.秒殺系統(tǒng)核心邏輯：-用戶請求先經(jīng)過Redis，使用Lua腳本原子性扣減庫存。-庫存不足則拒絕。luaifredis.call('get',KEYS[1])>tonumber(ARGV[1])thenredis.call('decr',KEYS[1],ARGV[1])return1elsereturn0end雪崩處理：-限流（熔斷）。-異步處理請求。五、代碼實現(xiàn)1.LRU緩存（已給出）2.快速排序pythondefquicksort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquicksort(left)+middle+quicksort(right)3.消息隊列pythonfromqueueimportQueuecla