2025年互聯(lián)網(wǎng)秋招筆試題及答案一、技術(shù)崗筆試題（后端/算法方向）1.算法與數(shù)據(jù)結(jié)構(gòu)（20分）給定一個包含n個整數(shù)的數(shù)組nums（n≥3），其中可能存在重復(fù)元素。設(shè)計一個時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，找出數(shù)組中是否存在三元組(i,j,k)（i≠j≠k），使得nums[i]+nums[j]+nums[k]=0。若存在，返回所有滿足條件的不重復(fù)三元組；若不存在，返回空列表。示例輸入：nums=[-1,0,1,2,-1,-4]示例輸出：[[-1,-1,2],[-1,0,1]]答案及解析：解題思路：排序+雙指針法。首先對數(shù)組排序，固定一個數(shù)nums[i]，然后用左右指針分別指向i+1和末尾，通過調(diào)整指針尋找和為-nums[i]的兩個數(shù)。需注意去重：若當(dāng)前數(shù)與前一個數(shù)相同，跳過以避免重復(fù)三元組；若左右指針遇到相同元素，也需跳過。具體步驟：（1）排序數(shù)組，時間復(fù)雜度O(nlogn)（符合題目隱含的預(yù)處理允許）；（2）遍歷數(shù)組，固定i，若nums[i]>0則直接跳出（因數(shù)組已排序，后續(xù)無法組成和為0的三元組）；（3）對i去重：若i>0且nums[i]==nums[i-1]，跳過；（4）左指針left=i+1，右指針right=n-1，計算sum=nums[i]+nums[left]+nums[right]；（5）若sum=0，記錄該三元組，然后對left和right去重（left<right且nums[left]==nums[left+1]時left++，同理right--），再移動left和right；（6）若sum<0，說明需要更大的數(shù)，left++；若sum>0，需要更小的數(shù)，right--。示例輸入排序后為[-4,-1,-1,0,1,2]。i=0時nums[i]=-4，尋找和為4的兩數(shù)，left=1（-1），right=5（2），sum=-4+(-1)+2=-3<0→left++；i=1時nums[i]=-1，尋找和為1的兩數(shù)，left=2（-1），right=5（2），sum=-1+(-1)+2=0→記錄[-1,-1,2]，然后left++到3（0），right--到4（1），sum=-1+0+1=0→記錄[-1,0,1]；后續(xù)i=2時nums[i]=-1（與i=1重復(fù)），跳過；i=3時nums[i]=0，后續(xù)數(shù)均≥0，無法組成和為0的三元組。最終輸出正確。2.操作系統(tǒng)（15分）某系統(tǒng)采用請求分頁存儲管理，頁表項包括有效位、訪問位、修改位、頁框號。假設(shè)物理內(nèi)存有4個頁框（初始為空），頁面走向為1,2,3,4,1,2,5,1,2,3,4,5。分別使用FIFO（先進先出）和LRU（最近最久未使用）頁面置換算法，計算缺頁次數(shù)及缺頁率（假設(shè)初始時頁表為空，所有頁首次訪問均缺頁）。答案及解析：（1）FIFO算法：頁框變化過程：-1（缺頁，頁框[1]）-2（缺頁，頁框[1,2]）-3（缺頁，頁框[1,2,3]）-4（缺頁，頁框[1,2,3,4]）→缺頁次數(shù)4-1（命中，頁框[1,2,3,4]）-2（命中，頁框[1,2,3,4]）-5（缺頁，置換最早進入的1→頁框[2,3,4,5]）→缺頁次數(shù)5-1（缺頁，置換2→頁框[3,4,5,1]）→缺頁次數(shù)6-2（缺頁，置換3→頁框[4,5,1,2]）→缺頁次數(shù)7-3（缺頁，置換4→頁框[5,1,2,3]）→缺頁次數(shù)8-4（缺頁，置換5→頁框[1,2,3,4]）→缺頁次數(shù)9-5（缺頁，置換1→頁框[2,3,4,5]）→缺頁次數(shù)10總?cè)表摯螖?shù)10次，缺頁率10/12≈83.33%（2）LRU算法：頁框變化過程：-1（缺頁，頁框[1]）-2（缺頁，頁框[1,2]）-3（缺頁，頁框[1,2,3]）-4（缺頁，頁框[1,2,3,4]）→缺頁次數(shù)4-1（命中，調(diào)整順序為[2,3,4,1]）-2（命中，調(diào)整順序為[3,4,1,2]）-5（缺頁，置換最久未使用的3→頁框[4,1,2,5]）→缺頁次數(shù)5-1（命中，調(diào)整順序為[4,2,5,1]）-2（命中，調(diào)整順序為[4,5,1,2]）-3（缺頁，置換最久未使用的4→頁框[5,1,2,3]）→缺頁次數(shù)6-4（缺頁，置換最久未使用的5→頁框[1,2,3,4]）→缺頁次數(shù)7-5（缺頁，置換最久未使用的1→頁框[2,3,4,5]）→缺頁次數(shù)8總?cè)表摯螖?shù)8次，缺頁率8/12≈66.67%3.計算機網(wǎng)絡(luò)（15分）假設(shè)主機A通過TCP向主機B傳輸一個大小為6MB的文件（1MB=1024KB=1024×1024B），初始擁塞窗口為2MSS（最大報文段長度），MSS=1KB，RTT=100ms，超時時間為400ms。忽略ACK段大小和處理延遲，且網(wǎng)絡(luò)始終未發(fā)生擁塞（即未觸發(fā)超時或快速重傳）。計算：（1）從開始傳輸?shù)桨l(fā)送完所有數(shù)據(jù)所需的時間（精確到ms）；（2）若主機B的接收窗口初始為4KB，且每收到2KB數(shù)據(jù)后接收窗口增加2KB（最大不超過16KB），則傳輸時間如何變化？答案及解析：（1）TCP擁塞控制采用慢開始+擁塞避免（因未發(fā)生擁塞）。初始擁塞窗口cwnd=2MSS=2KB，每RTT（100ms）后cwnd翻倍（慢開始）直到達到閾值（假設(shè)閾值初始為無窮大，未觸發(fā)擁塞避免）。文件大小6MB=6×1024KB=6144KB。各RTT內(nèi)發(fā)送的數(shù)據(jù)量：-RTT1（0-100ms）：cwnd=2KB→發(fā)送2KB，剩余6144-2=6142KB-RTT2（100-200ms）：cwnd=4KB→發(fā)送4KB，剩余6142-4=6138KB-RTT3（200-300ms）：cwnd=8KB→發(fā)送8KB，剩余6138-8=6130KB-RTT4（300-400ms）：cwnd=16KB→發(fā)送16KB，剩余6130-16=6114KB-RTT5（400-500ms）：cwnd=32KB→發(fā)送32KB，剩余6114-32=6082KB-RTT6（500-600ms）：cwnd=64KB→發(fā)送64KB，剩余6082-64=6018KB-RTT7（600-700ms）：cwnd=128KB→發(fā)送128KB，剩余6018-128=5890KB-RTT8（700-800ms）：cwnd=256KB→發(fā)送256KB，剩余5890-256=5634KB-RTT9（800-900ms）：cwnd=512KB→發(fā)送512KB，剩余5634-512=5122KB-RTT10（900-1000ms）：cwnd=1024KB→發(fā)送1024KB，剩余5122-1024=4098KB-此時cwnd達到1024KB（1MB），繼續(xù)以1024KB/RTT發(fā)送：4098KB÷1024KB/RTT≈4.002RTT，取整為5個RTT（實際最后一個RTT只需發(fā)送4098%1024=4098-4×1024=4098-4096=2KB）總時間計算：前10個RTT為10×100=1000ms，后續(xù)4個完整RTT（4×100=400ms）發(fā)送4×1024=4096KB，剩余2KB在第15個RTT的前2/1024×100≈0.195ms發(fā)送。但實際TCP是按窗口發(fā)送，最后一次窗口為1024KB，發(fā)送2KB后即完成，因此總時間為10×100+4×100+0.195≈1400.195ms，約1400ms。（2）接收窗口（rwnd）限制發(fā)送窗口的最大值（取min(cwnd,rwnd)）。初始rwnd=4KB，每收到2KB數(shù)據(jù)后rwnd增加2KB（最大16KB）。各階段rwnd變化：-初始rwnd=4KB-收到2KB→rwnd=4+2=6KB（但需滿足每次增加2KB的條件，實際每接收2KB觸發(fā)一次調(diào)整）-具體調(diào)整點：每接收2KB數(shù)據(jù)后rwnd+2KB，直到16KB。發(fā)送窗口=min(cwnd,rwnd)，需同時考慮擁塞窗口和接收窗口的增長：RTT1：cwnd=2KB，rwnd=4KB→發(fā)送2KB，接收后rwnd=4+2=6KB（因接收2KB）RTT2：cwnd=4KB，rwnd=6KB→發(fā)送4KB（累計接收6KB），rwnd=6+2×2=10KB（接收4KB，每2KB觸發(fā)一次，共2次）RTT3：cwnd=8KB，rwnd=10KB→發(fā)送8KB（累計接收14KB），rwnd=10+2×4=18KB（接收8KB，觸發(fā)4次），但上限16KB→rwnd=16KBRTT4：cwnd=16KB，rwnd=16KB→發(fā)送16KB（累計接收30KB），rwnd=16（已達上限）后續(xù)cwnd繼續(xù)增長，但rwnd固定為16KB，因此發(fā)送窗口=min(cwnd,16KB)。當(dāng)cwnd超過16KB后，發(fā)送窗口固定為16KB。文件總大小6144KB，前幾個RTT發(fā)送量：RTT1:2KB（剩余6142）RTT2:4KB（剩余6138）RTT3:8KB（剩余6130）RTT4:16KB（剩余6114）RTT5:16KB（剩余6098）...（后續(xù)每RTT發(fā)送16KB）總發(fā)送次數(shù)：前4次發(fā)送2+4+8+16=30KB，剩余6144-30=6114KB，需6114/16≈382.125→383個RTT總時間：(4+383)×100=38700ms，明顯長于無接收窗口限制的情況（原因為接收窗口增長較慢，限制了發(fā)送速率）。4.編程題（Rust語言，20分）用Rust實現(xiàn)一個并發(fā)任務(wù)調(diào)度器，要求：-支持提交任務(wù)（FnOnce()->T，T為任意類型）；-調(diào)度器維護一個線程池（線程數(shù)為N），任務(wù)提交后由線程池中的空閑線程執(zhí)行；-提供阻塞方法等待所有任務(wù)完成，并返回所有任務(wù)的執(zhí)行結(jié)果（按提交順序）；-需處理線程安全問題，避免死鎖或競態(tài)條件。答案及解析：核心思路：使用通道（channel）傳遞任務(wù)，線程池線程從通道中獲取任務(wù)執(zhí)行；用Arc<Mutex<...>>或原子變量管理任務(wù)狀態(tài)；結(jié)果收集需按提交順序，因此需為每個任務(wù)分配唯一ID，并在結(jié)果中記錄ID，最后排序。代碼實現(xiàn)（關(guān)鍵部分）：```rustusestd::collections::VecDeque;usestd::sync::{Arc,Mutex,mpsc};usestd::thread;usestd::time::Duration;structTaskScheduler<T>{sender:mpsc::Sender<Box<dynFnOnce()->T+Send+'static>>,result_receiver:mpsc::Receiver<(usize,T)>,task_counter:Arc<Mutex<usize>>,results:Arc<Mutex<VecDeque<(usize,T)>>>,worker_handles:Vec<thread::JoinHandle<()>>,}impl<T:Send+'static>TaskScheduler<T>{fnnew(thread_count:usize)->Self{let(task_sender,task_receiver)=mpsc::channel();let(result_sender,result_receiver)=mpsc::channel();lettask_counter=Arc::new(Mutex::new(0));letresults=Arc::new(Mutex::new(VecDeque::new()));letmutworker_handles=Vec::with_capacity(thread_count);for_in0..thread_count{lettask_receiver=task_receiver.clone();letresult_sender=result_sender.clone();letresults_clone=Arc::clone(&results);lethandle=thread::spawn(move||{whileletOk(task)=task_receiver.recv(){letresult=task();letmutresults=results_clone.lock().unwrap();lettask_id={letmutcounter=task_counter.lock().unwrap();counter+=1;counter-1};result_sender.send((task_id,result)).unwrap();}});worker_handles.push(handle);}Self{sender:task_sender,result_receiver,task_counter,results,worker_handles,}}fnsubmit<F>(&self,task:F)whereF:FnOnce()->T+Send+'static,{self.sender.send(Box::new(task)).unwrap();}fnwait_all(&self)->Vec<T>{drop(self.sender);//關(guān)閉發(fā)送端，讓工作線程退出forhandlein&self.worker_handles{handle.join().unwrap();}letmutordered_results=Vec::new();letmutcollected=Vec::new();whileletOk((id,result))=self.result_receiver.try_recv(){collected.push((id,result));}collected.sort_by_key(|&(id,_)|id);ordered_results=o_iter().map(|(_,res)|res).collect();ordered_results}}//測試用例fnmain(){letscheduler=TaskScheduler::new(4);//4個工作線程scheduler.submit(||{thread::sleep(Duration::from_millis(100));1});scheduler.submit(||{2});scheduler.submit(||{thread::sleep(Duration::from_millis(200));3});letresults=scheduler.wait_all();assert_eq!(results,vec![1,2,3]);}```解析：-使用mpsc通道傳遞任務(wù)，工作線程從通道接收任務(wù)并執(zhí)行；-每個任務(wù)執(zhí)行后，通過另一個通道發(fā)送結(jié)果（附帶任務(wù)ID）；-任務(wù)ID通過Arc<Mutex<usize>>生成，確保原子遞增；-wait_all方法關(guān)閉發(fā)送端，等待所有工作線程結(jié)束，收集所有結(jié)果并按ID排序，保證順序；-線程安全通過Mutex和通道的同步機制實現(xiàn)，避免競態(tài)條件；-測試用例驗證了任務(wù)按提交順序返回結(jié)果。5.系統(tǒng)設(shè)計題（20分）設(shè)計一個高并發(fā)的實時數(shù)據(jù)統(tǒng)計系統(tǒng)，用于統(tǒng)計用戶每天的點擊行為（如APP內(nèi)按鈕點擊次數(shù)）。要求：-支持億級用戶日活（DAU），單日總點擊量100億次；-統(tǒng)計延遲≤1秒；-支持按用戶ID、按鈕ID、時間段（小時/天）查詢統(tǒng)計結(jié)果；-保證數(shù)據(jù)可靠性（不丟數(shù)、不重復(fù)）。答案及解析：系統(tǒng)架構(gòu)設(shè)計需考慮數(shù)據(jù)寫入、處理、存儲、查詢四個核心環(huán)節(jié)。（1）數(shù)據(jù)寫入層-使用消息隊列（如Kafka）作為緩沖，處理高并發(fā)寫入。Kafka的分區(qū)（Partition）機制可水平擴展，每個分區(qū)對應(yīng)一個消費者組，提高吞吐量。-每條點擊事件包含：用戶ID、按鈕ID、時間戳、設(shè)備信息等，格式為JSON或Protobuf（減少序列化開銷）。-寫入時按用戶ID或按鈕ID哈希到不同分區(qū)（如按用戶ID哈希），保證同一用戶的事件順序性（若需要）。（2）數(shù)據(jù)處理層-使用流處理框架（如Flink或KafkaStreams）進行實時計算。設(shè)置窗口（Window）為1秒，按用戶ID+按鈕ID+小時（或天）維度聚合點擊次數(shù)。-聚合結(jié)果寫入緩存（如Redis）和持久化存儲（如HBase或ClickHouse）：-Redis存儲最近1天的實時統(tǒng)計結(jié)果（鍵格式：user:{uid}:button:{bid}:hour:{hour}），用于低延遲查詢；-HBase/ClickHouse存儲歷史數(shù)據(jù)（按天分區(qū)），用于離線查詢或補算。（3）數(shù)據(jù)可靠性保障-Kafka設(shè)置acks=all，確保消息寫入所有副本后確認；-Flink開啟Checkpoint（檢查點），故障時通過Checkpoint恢復(fù)狀態(tài)；-消費者處理消息后提交偏移量（Offset）到Kafka，避免重復(fù)消費；-冪等設(shè)計：若消息重復(fù)，聚合操作（如計數(shù)）需支持冪等（如使用唯一事件ID去重，或通過時間戳+用戶ID+按鈕ID作為唯一鍵）。（4）查詢層-實時查詢（最近1天）：直接從Redis讀取，響應(yīng)時間≤10ms；-歷史查詢（超過1天）：從HBase/ClickHouse查詢，通過預(yù)聚合的分區(qū)表加速（如按天分區(qū)，按用戶ID、按鈕ID建立二級索引）；-時間段查詢：組合小時級統(tǒng)計結(jié)果（如查詢某天8-10點的數(shù)據(jù)，需查詢8、9、10點的統(tǒng)計值并求和）。（5）擴展性優(yōu)化-消息隊列分區(qū)數(shù)根據(jù)DAU和點擊量動態(tài)調(diào)整（如高峰期增加分區(qū)）；-流處理任務(wù)并行度與Kafka分區(qū)數(shù)匹配，避免瓶頸；-Redis使用集群模式（如RedisCluster），按用戶ID分片存儲；-HBase/ClickHouse使用列式存儲，針對查詢維度（用戶ID、按鈕ID、時間）建立索引。6.產(chǎn)品崗筆試題（10分）某短視頻APP計劃上線“智能剪輯助手”功能，幫助用戶快速生成高質(zhì)量短視頻。請設(shè)計該功能的需求文檔，包括：用戶場景、核心需求、功能優(yōu)先級排序（用KANO模型）、技術(shù)依賴及風(fēng)險點。答案及解析：（1）用戶場景-普通用戶：想分享生活但不會剪輯（如寶媽記錄寶寶成長，需快速合并片段、添加濾鏡）；-內(nèi)容創(chuàng)作者：批量生產(chǎn)內(nèi)容時，需自動化處理（如美食博主每天發(fā)布3條視頻，需自動去重、添加統(tǒng)一片頭）；-商家：推廣商品時，需快速生成多版本視頻（如服裝店需為同一件衣服生成豎屏/橫屏、不同濾鏡的版本）。（2）核心需求-自動片段篩選：根據(jù)畫面清晰度、人物表情（如笑容）、時長自動選擇優(yōu)質(zhì)片段；-智能轉(zhuǎn)場：根據(jù)內(nèi)容類型（如風(fēng)景→漸隱，對話→閃白）推薦轉(zhuǎn)場效果；-一鍵風(fēng)格化：內(nèi)置“電影感”“清新”“復(fù)古”等模板，自動匹配濾鏡、音樂、字幕；-批量處理：支持同時上傳100個片段，生成5個不同版本視頻；-自定義調(diào)整：允許用戶修改自動生成的結(jié)果（如替換音樂、調(diào)整轉(zhuǎn)場時長）。（3）功能優(yōu)先級（KANO模型）-基本型需求（必須滿足）：自動片段篩選（無此功能用戶無法使用）、一鍵風(fēng)格化（核心賣點）；-期望型需求（提升滿意度）：智能轉(zhuǎn)場（用戶希望更自然）、自定義調(diào)整（滿足個性化）；-興