2025年華為公司軟件筆試試卷及答案一、數(shù)據(jù)結(jié)構(gòu)與算法（共5題）1.題目：給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組nums（n≥3），找出所有滿足i<j<k且nums[i]+nums[j]+nums[k]是7的倍數(shù)的三元組(i,j,k)。要求時(shí)間復(fù)雜度不超過O(n2)，空間復(fù)雜度O(n)。答案：關(guān)鍵思路：利用模7的余數(shù)特性，將問題轉(zhuǎn)化為余數(shù)組合問題。步驟：（1）預(yù)處理數(shù)組，統(tǒng)計(jì)每個(gè)元素對(duì)7取模后的余數(shù)，得到余數(shù)數(shù)組mods（mods[i]=nums[i]%7）。（2）使用哈希表或數(shù)組cnt[7]記錄各余數(shù)出現(xiàn)的次數(shù)（cnt[r]表示余數(shù)為r的元素個(gè)數(shù)）。（3）枚舉所有可能的余數(shù)組合(a,b,c)，滿足(a+b+c)%7=0，且對(duì)應(yīng)的元素索引滿足i<j<k。需注意同一余數(shù)可能被多次選取的情況。（4）對(duì)于每種有效組合，計(jì)算對(duì)應(yīng)的三元組數(shù)目：-若a=b=c=0：數(shù)目為C(cnt[0],3)（組合數(shù)）。-若a=b≠c且2a+c≡0mod7（a≠c）：數(shù)目為C(cnt[a],2)cnt[c]。-若a,b,c互不相同且a+b+c≡0mod7：數(shù)目為cnt[a]cnt[b]cnt[c]。（5）遍歷所有可能的余數(shù)組合，累加總數(shù)。時(shí)間復(fù)雜度分析：預(yù)處理O(n)，余數(shù)組合枚舉共77=49種情況（因c=(7-(a+b)%7)%7），故總時(shí)間O(n2)優(yōu)化為O(n+49)=O(n)（實(shí)際枚舉組合時(shí)需避免重復(fù)計(jì)算，如固定a≤b≤c）。2.題目：設(shè)計(jì)一個(gè)函數(shù)，輸入為二叉樹的根節(jié)點(diǎn)root和整數(shù)k，返回樹中路徑和等于k的路徑總數(shù)。路徑定義為任意節(jié)點(diǎn)到其某個(gè)子節(jié)點(diǎn)的序列（路徑必須至少包含一個(gè)節(jié)點(diǎn)）。要求空間復(fù)雜度O(h)（h為樹高）。答案：關(guān)鍵思路：利用前綴和+回溯法，記錄從根到當(dāng)前節(jié)點(diǎn)的路徑前綴和，通過哈希表統(tǒng)計(jì)前綴和出現(xiàn)次數(shù)。步驟：（1）維護(hù)一個(gè)全局哈希表prefixSum，記錄前綴和s出現(xiàn)的次數(shù)（初始時(shí)prefixSum[0]=1，處理根節(jié)點(diǎn)到自身的路徑）。（2）遞歸遍歷樹，當(dāng)前節(jié)點(diǎn)值為val，計(jì)算當(dāng)前路徑和currSum=父路徑和+val。（3）若prefixSum中存在currSum-k，則說明存在路徑和為k（路徑起點(diǎn)為前綴和為currSum-k的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)）。（4）將currSum加入prefixSum（回溯時(shí)需恢復(fù)，避免影響其他分支）。（5）遞歸處理左右子樹，累加左右子樹的路徑數(shù)。（6）回溯時(shí)將currSum從prefixSum中減1（或移除，若計(jì)數(shù)為0）。代碼（偽代碼）：intcount=0;HashMap<Integer,Integer>prefixSum=newHashMap<>();prefixSum.put(0,1);intdfs(TreeNodenode,intcurrSum,intk){if(node==null)return0;currSum+=node.val;count+=prefixSum.getOrDefault(currSum-k,0);prefixSum.put(currSum,prefixSum.getOrDefault(currSum,0)+1);intleft=dfs(node.left,currSum,k);intright=dfs(node.right,currSum,k);prefixSum.put(currSum,prefixSum.get(currSum)-1);//回溯if(prefixSum.get(currSum)==0)prefixSum.remove(currSum);returncount+left+right;}空間復(fù)雜度為O(h)，因遞歸棧深度為樹高h(yuǎn)，哈希表最多存儲(chǔ)h個(gè)不同前綴和。二、操作系統(tǒng)（共3題）3.題目：在分布式系統(tǒng)中，設(shè)計(jì)一個(gè)互斥鎖機(jī)制，要求滿足以下條件：（1）正確性（任意時(shí)刻僅一個(gè)進(jìn)程持有鎖）；（2）容錯(cuò)性（允許單個(gè)協(xié)調(diào)節(jié)點(diǎn)故障）；（3）高效性（網(wǎng)絡(luò)延遲對(duì)性能影響較?。?。請(qǐng)描述核心設(shè)計(jì)思路。答案：核心設(shè)計(jì)思路采用分布式鎖的改進(jìn)Raft協(xié)議結(jié)合租約（Lease）機(jī)制：（1）鎖管理集群：使用Raft協(xié)議選舉主協(xié)調(diào)節(jié)點(diǎn)，主節(jié)點(diǎn)負(fù)責(zé)分配鎖。當(dāng)主節(jié)點(diǎn)故障時(shí)，通過Raft重新選舉新主，保證集群可用性。（2）租約機(jī)制：鎖持有者獲得一個(gè)租約（如5秒），租約過期前需主動(dòng)續(xù)約。若租約過期未續(xù)約，鎖自動(dòng)釋放。租約避免了因客戶端崩潰無法釋放鎖的問題。（3）心跳檢測(cè)：主節(jié)點(diǎn)與從節(jié)點(diǎn)保持心跳（如每1秒），從節(jié)點(diǎn)監(jiān)控主節(jié)點(diǎn)狀態(tài)。若主節(jié)點(diǎn)心跳超時(shí)（如3秒），觸發(fā)Raft選舉新主。（4）鎖申請(qǐng)流程：客戶端向主節(jié)點(diǎn)發(fā)送鎖申請(qǐng)，主節(jié)點(diǎn)檢查鎖是否空閑。若空閑，分配鎖并記錄租約過期時(shí)間，同時(shí)通過Raft日志同步到從節(jié)點(diǎn)（保證持久化）。（5）容錯(cuò)處理：若主節(jié)點(diǎn)故障，新主節(jié)點(diǎn)通過Raft日志恢復(fù)鎖狀態(tài)（僅處理已提交的日志），避免鎖狀態(tài)丟失。（6）延遲優(yōu)化：客戶端優(yōu)先與本地最近的從節(jié)點(diǎn)通信，從節(jié)點(diǎn)將請(qǐng)求轉(zhuǎn)發(fā)至主節(jié)點(diǎn)，減少跨區(qū)域網(wǎng)絡(luò)延遲。4.題目：某系統(tǒng)采用請(qǐng)求分頁存儲(chǔ)管理，頁表項(xiàng)包含有效位、修改位、訪問位。假設(shè)物理內(nèi)存有4個(gè)頁框，采用改進(jìn)的Clock置換算法（掃描順序?yàn)?→1→2→3→0…）。當(dāng)前頁框狀態(tài)如下：頁框0：有效位1，修改位0，訪問位1頁框1：有效位1，修改位1，訪問位1頁框2：有效位1，修改位0，訪問位0頁框3：有效位1，修改位1，訪問位0若此時(shí)發(fā)生缺頁中斷，需要置換一個(gè)頁面。請(qǐng)寫出置換過程及最終被置換的頁框號(hào)。答案：改進(jìn)的Clock算法優(yōu)先級(jí)（從低到高）：(0,0)→(0,1)→(1,0)→(1,1)（(訪問位,修改位)）。掃描過程：（1）初始指針指向頁框0，狀態(tài)(1,0)→優(yōu)先級(jí)第三，不置換。（2）指針移到頁框1，狀態(tài)(1,1)→優(yōu)先級(jí)第四，不置換。（3）指針移到頁框2，狀態(tài)(0,0)→優(yōu)先級(jí)第一，符合置換條件。但需注意，首次掃描時(shí)訪問位會(huì)被重置：正確步驟應(yīng)為：第一次掃描：-頁框0：訪問位1→置0，指針移到1。-頁框1：訪問位1→置0，指針移到2。-頁框2：訪問位0→檢查修改位0→置換（優(yōu)先級(jí)最低）。因此，最終被置換的頁框是頁框2。三、計(jì)算機(jī)網(wǎng)絡(luò)（共3題）5.題目：HTTP/3相比HTTP/2有哪些核心改進(jìn)？針對(duì)移動(dòng)網(wǎng)絡(luò)場(chǎng)景，HTTP/3如何優(yōu)化性能？答案：HTTP/3的核心改進(jìn)：（1）基于QUIC協(xié)議：替代HTTP/2的TCP+TLS+HTTP/2分層結(jié)構(gòu)，QUIC將加密（TLS1.3）、連接管理、流復(fù)用集成到傳輸層，減少握手延遲。（2）解決隊(duì)頭阻塞：TCP連接中若一個(gè)包丟失，后續(xù)包需等待重傳（隊(duì)頭阻塞）；QUIC每個(gè)流獨(dú)立編號(hào)，丟包僅影響對(duì)應(yīng)流，其他流可繼續(xù)傳輸。（3）快速連接恢復(fù)：QUIC使用連接ID（非IP+端口）標(biāo)識(shí)連接，移動(dòng)設(shè)備切換網(wǎng)絡(luò)（如Wi-Fi→4G）時(shí)，IP變化但連接ID不變，無需重新握手。移動(dòng)網(wǎng)絡(luò)優(yōu)化：（1）減少握手延遲：QUIC首次握手僅需1RTT（TLS1.3），后續(xù)連接利用會(huì)話票據(jù)實(shí)現(xiàn)0RTT恢復(fù)，比TCP+TLS的2-3RTT更快。（2）抗丟包能力：QUIC支持前向糾錯(cuò)（FEC）和更精細(xì)的擁塞控制（如BBR算法），在高丟包率的移動(dòng)網(wǎng)絡(luò)中保持吞吐量。（3）多路徑支持（實(shí)驗(yàn)性）：QUIC支持同時(shí)使用Wi-Fi和蜂窩網(wǎng)絡(luò)傳輸數(shù)據(jù)，提高鏈路可靠性。6.題目：設(shè)計(jì)一個(gè)基于TCP的文件傳輸協(xié)議，要求支持?jǐn)帱c(diǎn)續(xù)傳。請(qǐng)描述關(guān)鍵字段設(shè)計(jì)及續(xù)傳流程。答案：關(guān)鍵字段設(shè)計(jì)：（1）文件元信息：文件名、總大小、塊大?。ㄈ?KB）、哈希值（如SHA-256，用于校驗(yàn)塊完整性）。（2）傳輸控制字段：-操作類型（上傳、下載、續(xù)傳請(qǐng)求）。-當(dāng)前已傳輸塊號(hào)（如塊號(hào)從0開始，已傳至塊n-1）。-塊偏移量（在文件中的起始字節(jié)位置）。-塊數(shù)據(jù)長(zhǎng)度。續(xù)傳流程：（1）客戶端首次傳輸：發(fā)送文件元信息，服務(wù)端創(chuàng)建文件并記錄總塊數(shù)?？蛻舳税磯K上傳，服務(wù)端接收后記錄已完成塊號(hào)。（2）中斷后續(xù)傳：客戶端發(fā)送續(xù)傳請(qǐng)求，包含文件名和本地已傳塊號(hào)（或最后成功上傳的塊號(hào)+1）。（3）服務(wù)端校驗(yàn)：檢查文件是否存在，對(duì)比已傳塊號(hào)（服務(wù)端可能已接收更多塊，需同步最新狀態(tài)）。（4）同步塊號(hào)：服務(wù)端返回當(dāng)前最大已接收塊號(hào)m，客戶端從塊m+1開始續(xù)傳。（5）塊校驗(yàn)：客戶端上傳塊時(shí)攜帶哈希值，服務(wù)端接收后計(jì)算哈希并比對(duì)，若不一致要求重傳該塊。四、程序設(shè)計(jì)（C++）7.題目：實(shí)現(xiàn)一個(gè)線程安全的環(huán)形緩沖區(qū)（CircularBuffer）類，要求：-模板類，支持任意數(shù)據(jù)類型T。-支持多生產(chǎn)者-多消費(fèi)者模型。-當(dāng)緩沖區(qū)滿時(shí)，生產(chǎn)者阻塞直到有空間；當(dāng)緩沖區(qū)空時(shí)，消費(fèi)者阻塞直到有數(shù)據(jù)。-使用RAII管理資源，避免資源泄漏。答案：核心設(shè)計(jì)：-使用互斥鎖（std::mutex）保證操作原子性。-使用條件變量（std::condition_variable）實(shí)現(xiàn)生產(chǎn)者/消費(fèi)者的等待-通知機(jī)制。-環(huán)形緩沖區(qū)用數(shù)組或vector實(shí)現(xiàn)，記錄讀指針（read_idx）、寫指針（write_idx）、有效元素?cái)?shù)（count）。代碼實(shí)現(xiàn)：template<typenameT>classCircularBuffer{public:explicitCircularBuffer(size_tcapacity):capacity_(capacity),buffer_(capacity),read_idx_(0),write_idx_(0),count_(0){}//禁止拷貝和移動(dòng)CircularBuffer(constCircularBuffer&)=delete;CircularBuffer&operator=(constCircularBuffer&)=delete;voidpush(constT&data){std::unique_lock<std::mutex>lock(mutex_);//等待緩沖區(qū)不滿not_full_.wait(lock,[this](){returncount_<capacity_;});buffer_[write_idx_]=data;write_idx_=(write_idx_+1)%capacity_;++count_;not_empty_.notify_one();//通知消費(fèi)者有數(shù)據(jù)}Tpop(){std::unique_lock<std::mutex>lock(mutex_);//等待緩沖區(qū)非空not_empty_.wait(lock,[this](){returncount_>0;});Tdata=buffer_[read_idx_];read_idx_=(read_idx_+1)%capacity_;--count_;not_full_.notify_one();//通知生產(chǎn)者有空間returndata;}private:constsize_tcapacity_;std::vector<T>buffer_;size_tread_idx_;size_twrite_idx_;size_tcount_;//有效元素?cái)?shù)（避免(write-read)取模的復(fù)雜計(jì)算）std::mutexmutex_;std::condition_variablenot_empty_;//消費(fèi)者等待條件std::condition_variablenot_full_;//生產(chǎn)者等待條件};關(guān)鍵點(diǎn)說明：-使用count_直接記錄有效元素?cái)?shù)，避免通過讀寫指針計(jì)算時(shí)的邊界條件問題（如write_idx_==read_idx_時(shí)可能滿或空）。-條件變量的等待謂詞確保在虛假喚醒時(shí)重新檢查條件。-RAII通過vector和標(biāo)準(zhǔn)庫(kù)鎖自動(dòng)管理資源，無需手動(dòng)釋放。五、數(shù)據(jù)庫(kù)（共2題）8.題目：某電商系統(tǒng)有訂單表orders（order_idINT,user_idINT,amountDECIMAL,create_timeDATETIME）和用戶表users（user_idINT,usernameVARCHAR(50)）。需查詢近30天內(nèi)消費(fèi)金額最高的前10名用戶（包括用戶名和總消費(fèi)金額），要求考慮索引優(yōu)化。答案：SQL語句：SELECTu.username,SUM(o.amount)AStotal_amountFROMusersuJOINordersoONu.user_id=o.user_idWHEREo.create_time>=DATE_SUB(NOW(),INTERVAL30DAY)GROUPBYu.user_idORDERBYtotal_amountDESCLIMIT10;索引優(yōu)化策略：（1）在orders表的create_time和user_id字段上創(chuàng)建復(fù)合索引（user_id,create_time,amount），形成覆蓋索引。該索引按user_id分組，create_time過濾近30天數(shù)據(jù)，amount用于求和，避免回表查詢。（2）users表的user_id為主鍵，已有索引，無需額外創(chuàng)建。優(yōu)化原理：-復(fù)合索引(user_id,create_time,amount)的順序符合WHERE條件（create_time過濾）、JOIN條件（user_id關(guān)聯(lián)）和GROUPBY（user_id分組）的需求，且