2026年新浪微博算法工程師面試問題解析一、編程基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)（共5題，總分20分）1.（4分）實(shí)現(xiàn)一個(gè)LRU（LeastRecentlyUsed）緩存，要求使用鏈表和哈希表結(jié)合的方式，支持`get`和`put`操作，時(shí)間復(fù)雜度為O(1)。2.（4分）給定一個(gè)無重復(fù)元素的數(shù)組`nums`和一個(gè)目標(biāo)值`target`，返回所有相加和為`target`的`nums`的索引組合。例如：`nums=[2,3,6,7]`,`target=7`，返回`[[0,1],[1,2]]`。3.（5分）設(shè)計(jì)一個(gè)算法，找出數(shù)組中重復(fù)次數(shù)超過`n/3`的元素，假設(shè)數(shù)組長度為`n`且至少有兩個(gè)重復(fù)元素。4.（4分）實(shí)現(xiàn)快速排序算法，要求原地排序，并寫出其平均時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度。5.（3分）解釋什么是布隆過濾器（BloomFilter），并說明其優(yōu)缺點(diǎn)及適用場景。二、算法設(shè)計(jì)（共3題，總分15分）1.（5分）新浪微博的推薦系統(tǒng)需要實(shí)時(shí)處理用戶的行為日志（如點(diǎn)擊、點(diǎn)贊、評論），設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持以下操作：-插入用戶行為日志（包含用戶ID、內(nèi)容ID、行為類型、時(shí)間戳）。-查詢某個(gè)用戶最近`k`條行為，按時(shí)間降序排列。2.（5分）假設(shè)微博消息包含大量emoji表情符號，設(shè)計(jì)一個(gè)算法去除消息中的重復(fù)emoji，同時(shí)保留首次出現(xiàn)的順序。3.（5分）微博的熱搜榜需要實(shí)時(shí)更新，要求：-支持每分鐘統(tǒng)計(jì)一次熱門話題，時(shí)間復(fù)雜度盡可能低。-熱搜榜最多顯示前10個(gè)話題，新話題需要動態(tài)插入。三、系統(tǒng)設(shè)計(jì)（共2題，總分15分）1.（8分）設(shè)計(jì)一個(gè)微博消息的分發(fā)系統(tǒng)，要求：-支持用戶發(fā)布消息（文本+圖片/視頻），消息需要異步處理并推送給關(guān)注者。-使用消息隊(duì)列解決高并發(fā)下的性能瓶頸問題。2.（7分）微博的評論系統(tǒng)需要支持以下功能：-用戶可以回復(fù)其他用戶的評論，形成樹狀結(jié)構(gòu)。-查詢某個(gè)評論的所有回復(fù)，要求前`k`級回復(fù)。四、機(jī)器學(xué)習(xí)與深度學(xué)習(xí)（共2題，總分10分）1.（5分）微博文本情感分析中，為什么需要使用詞嵌入（WordEmbedding）？列舉至少兩種常見的詞嵌入方法（如Word2Vec、BERT）。2.（5分）解釋過擬合（Overfitting）和欠擬合（Underfitting）的概念，并提出至少兩種解決方法（如正則化、交叉驗(yàn)證）。五、分布式與數(shù)據(jù)庫（共2題，總分10分）1.（5分）微博的數(shù)據(jù)庫使用MySQL+Redis組合，說明Redis在推薦系統(tǒng)中的作用（如緩存熱點(diǎn)數(shù)據(jù)）。2.（5分）設(shè)計(jì)一個(gè)分布式任務(wù)調(diào)度系統(tǒng)，要求：-支持定時(shí)任務(wù)（如每日統(tǒng)計(jì)用戶活躍度）。-處理任務(wù)失敗重試的邏輯。六、開放性問題（共1題，總分5分）1.（5分）微博推薦系統(tǒng)的冷啟動問題是什么？如何緩解冷啟動問題？答案與解析一、編程基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)1.（4分）LRU緩存實(shí)現(xiàn)pythonclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._move_to_head(node)returnnode.valuereturn-1defput(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解析：-使用雙向鏈表維護(hù)訪問順序，頭節(jié)點(diǎn)為最近訪問，尾節(jié)點(diǎn)為最久未訪問。-哈希表`cache`存儲鍵值對，實(shí)現(xiàn)O(1)的`get`和`put`操作。-刪除尾節(jié)點(diǎn)時(shí)釋放內(nèi)存，保證緩存大小不超過`capacity`。2.（4分）三數(shù)之和組合問題pythondefthreeSum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:s=nums[i]+nums[left]+nums[right]ifs==target:res.append([i,left,right])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifs<target:left+=1else:right-=1returnres解析：-排序后使用雙指針法，固定第一個(gè)數(shù)，在剩余部分找兩數(shù)和。-跳過重復(fù)元素避免重復(fù)組合。3.（5分）找出出現(xiàn)次數(shù)超過`n/3`的元素pythondefmajorityElement(nums):candidate1,candidate2,count1,count2=None,None,0,0fornuminnums:ifnum==candidate1:count1+=1elifnum==candidate2:count2+=1elifcount1==0:candidate1,count1=num,1elifcount2==0:candidate2,count2=num,1else:count1-=1count2-=1res=[]count1,count2=0,0fornuminnums:ifnum==candidate1:count1+=1elifnum==candidate2:count2+=1ifcount1>len(nums)//3:res.append(candidate1)ifcount2>len(nums)//3:res.append(candidate2)returnres解析：-Boyer-Moore多數(shù)投票算法的擴(kuò)展，維護(hù)兩個(gè)候選者和計(jì)數(shù)器。-首次遍歷排除非多數(shù)元素，第二次驗(yàn)證候選者的實(shí)際出現(xiàn)次數(shù)。4.（4分）快速排序算法pythondefquicksort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquicksort(left)+middle+quicksort(right)解析：-平均時(shí)間復(fù)雜度O(nlogn)，最壞情況O(n2)（選擇最壞樞軸）。-原地排序可通過交換實(shí)現(xiàn)，但代碼中為簡化使用列表分治。5.（3分）布隆過濾器-原理：將鍵映射為多個(gè)哈希函數(shù)，存儲在位數(shù)組中。-優(yōu)點(diǎn)：空間效率高，支持快速查詢。-缺點(diǎn)：存在誤判（假陽性），無法刪除元素（除非使用計(jì)數(shù)布隆過濾器）。-適用場景：緩存、爬蟲URL去重、惡意IP檢測。二、算法設(shè)計(jì)1.（5分）實(shí)時(shí)用戶行為日志處理pythonfromcollectionsimportdequeclassBehaviorLog:def__init__(self):self.logs={}#user_id:dequeof(timestamp,action)definsert(self,user_id,content_id,action,timestamp):ifuser_idnotinself.logs:self.logs[user_id]=deque()self.logs[user_id].append((timestamp,action,content_id))self.logs[user_id].sort(reverse=True)#保持時(shí)間降序defquery(self,user_id,k):returnself.logs.get(user_id,[])[:k]解析：-使用`deque`存儲每個(gè)用戶的最近行為，按時(shí)間降序排列。-插入時(shí)保持隊(duì)列長度不超過實(shí)時(shí)窗口（如最近1小時(shí)）。2.（5分）去重emoji的算法pythondefremove_duplicate_emojis(s):seen=set()res=[]forcharins:ifcharnotinseen:res.append(char)seen.add(char)return''.join(res)解析：-使用集合`seen`記錄已出現(xiàn)的emoji，保留首次出現(xiàn)的順序。-適用于微博消息中emoji重復(fù)的情況。3.（5分）熱搜榜設(shè)計(jì)pythonfromcollectionsimportdefaultdict,dequeclassHotSearch:def__init__(self):self.topic_counts=defaultdict(int)self.rank=deque(maxlen=10)#存儲前10個(gè)話題defupdate(self,topic):self.topic_counts[topic]+=1iftopicnotinself.rank:self.rank.append(topic)self.rank=deque(sorted(self.rank,key=lambdax:self.topic_counts[x],reverse=True),maxlen=10)defget_top(self):returnlist(self.rank)解析：-使用哈希表統(tǒng)計(jì)話題熱度，隊(duì)列維護(hù)前10名。-動態(tài)插入時(shí)按熱度排序，保證實(shí)時(shí)性。三、系統(tǒng)設(shè)計(jì)1.（8分）微博消息分發(fā)系統(tǒng)-核心組件：1.消息隊(duì)列（Kafka/RabbitMQ）：異步處理發(fā)布請求，削峰填谷。2.發(fā)布服務(wù)：接收用戶請求，寫入消息隊(duì)列。3.消費(fèi)服務(wù)：按關(guān)注者分組消費(fèi)消息，推送到WebSocket/長輪詢。-高并發(fā)解決方案：-限流：令牌桶算法控制消息寫入速度。-分片：將用戶關(guān)注關(guān)系分片存儲，避免單節(jié)點(diǎn)過載。2.（7分）評論系統(tǒng)樹狀結(jié)構(gòu)設(shè)計(jì)-數(shù)據(jù)存儲：-評論ID、父評論ID、用戶ID、內(nèi)容、時(shí)間戳。-父評論ID為空時(shí)為頂級評論，否則遞歸查詢子評論。-查詢優(yōu)化：-使用遞歸或BFS遍歷評論樹，限制遞歸層數(shù)（如前3級）。-緩存熱門評論的子樹，避免重復(fù)計(jì)算。四、機(jī)器學(xué)習(xí)與深度學(xué)習(xí)1.（5分）詞嵌入的作用與方法-作用：將文本轉(zhuǎn)化為數(shù)