2026年華為研發(fā)工程師面試寶典及答案一、編程基礎(chǔ)（5題，每題10分，共50分）1.題目：請(qǐng)編寫一個(gè)函數(shù)，實(shí)現(xiàn)快速排序算法，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。答案與解析：c++include<vector>include<iostream>voidquickSort(std::vector<int>&arr,intleft,intright){if(left>=right)return;intpivot=arr[left];inti=left,j=right;while(i<j){while(i<j&&arr[j]>=pivot)j--;if(i<j)arr[i++]=arr[j];while(i<j&&arr[i]<=pivot)i++;if(i<j)arr[j--]=arr[i];}arr[i]=pivot;quickSort(arr,left,i-1);quickSort(arr,i+1,right);}intmain(){std::vector<int>arr={3,1,4,1,5,9,2,6,5,3};quickSort(arr,0,arr.size()-1);for(intnum:arr)std::cout<<num<<"";return0;}解析：快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，最壞情況為O(n2)（當(dāng)每次選取的樞軸都是最小或最大元素時(shí)）?？臻g復(fù)雜度為O(logn)，主要由遞歸調(diào)用棧決定。2.題目：請(qǐng)實(shí)現(xiàn)一個(gè)鏈表反轉(zhuǎn)函數(shù)，并說明其邊界條件處理。答案與解析：c++structListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodereverseList(ListNodehead){ListNodeprev=nullptr;ListNodecurr=head;while(curr){ListNodenext=curr->next;curr->next=prev;prev=curr;curr=next;}returnprev;}解析：邊界條件：空鏈表或單節(jié)點(diǎn)鏈表無需處理。需注意在遍歷過程中正確更新`next`指針，避免鏈表斷裂。3.題目：請(qǐng)編寫一個(gè)函數(shù)，判斷一個(gè)字符串是否為回文串，不使用額外空間。答案與解析：c++boolisPalindrome(conststd::string&s){intleft=0,right=s.size()-1;while(left<right){if(s[left]!=s[right])returnfalse;left++;right--;}returntrue;}解析：雙指針法，從兩端向中間遍歷，忽略非字母數(shù)字字符。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。4.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找出數(shù)組中的重復(fù)元素（至少重復(fù)一次），要求空間復(fù)雜度O(1)。答案與解析：c++include<vector>include<iostream>voidfindDuplicates(conststd::vector<int>&arr,std::vector<int>&duplicates){for(intnum:arr){intindex=abs(num)-1;if(arr[index]<0)duplicates.push_back(abs(num));arr[index]=-arr[index];}//Restorearrayfor(inti=0;i<arr.size();i++)arr[i]=abs(arr[i]);}intmain(){std::vector<int>arr={4,3,2,7,8,2,3,1};std::vector<int>duplicates;findDuplicates(arr,duplicates);for(intnum:duplicates)std::cout<<num<<"";return0;}解析：利用數(shù)組索引標(biāo)記元素是否出現(xiàn)過，負(fù)數(shù)表示已存在。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。5.題目：請(qǐng)編寫一個(gè)函數(shù)，實(shí)現(xiàn)二分查找，并處理數(shù)組重復(fù)元素的情況（返回任意一個(gè)目標(biāo)值的索引）。答案與解析：c++intbinarySearch(conststd::vector<int>&arr,inttarget){intleft=0,right=arr.size()-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target)returnmid;if(arr[left]<=arr[mid]){//Leftsortedif(target>=arr[left]&&target<arr[mid])right=mid-1;elseleft=mid+1;}else{//Rightsortedif(target>arr[mid]&&target<=arr[right])left=mid+1;elseright=mid-1;}}return-1;}解析：針對(duì)重復(fù)元素，可返回任意一個(gè)匹配索引。時(shí)間復(fù)雜度O(logn)，但存在重復(fù)元素時(shí)可能退化為O(n)。二、數(shù)據(jù)結(jié)構(gòu)與算法（5題，每題10分，共50分）1.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)LRU（最近最少使用）緩存，支持get和put操作，并說明其實(shí)現(xiàn)思路。答案與解析：c++include<unordered_map>include<list>classLRUCache{private:intcapacity;std::list<int>cache;std::unordered_map<int,std::pair<int,std::list<int>::iterator>>map;public:LRUCache(intcap):capacity(cap){}intget(intkey){autoit=map.find(key);if(it==map.end())return-1;cache.erase(it->second.second);cache.push_front(key);it->second.second=cache.begin();returnit->second.first;}voidput(intkey,intvalue){autoit=map.find(key);if(it!=map.end()){cache.erase(it->second.second);cache.push_front(key);it->second.second=cache.begin();it->second.first=value;}else{if(cache.size()==capacity){intoldKey=cache.back();cache.pop_back();map.erase(oldKey);}cache.push_front(key);map[key]={value,cache.begin()};}}};解析：使用雙向鏈表和哈希表實(shí)現(xiàn)：鏈表維護(hù)最近使用順序，哈希表實(shí)現(xiàn)O(1)訪問。get時(shí)將元素移到頭部，put時(shí)若容量已滿則刪除最久未使用元素。2.題目：請(qǐng)編寫一個(gè)函數(shù)，實(shí)現(xiàn)K個(gè)一組翻轉(zhuǎn)鏈表，并說明邊界條件。答案與解析：c++structListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodereverseKGroup(ListNodehead,intk){if(!head||k==1)returnhead;ListNodedummy(0);dummy.next=head;ListNodeprevGroupEnd=&dummy;while(true){ListNodekth=getKthNode(prevGroupEnd,k);if(!kth)break;ListNodegroupStart=prevGroupEnd->next;ListNodenextGroupStart=kth->next;//ReversegroupListNodeprev=kth->next;ListNodecurr=groupStart;while(curr!=nextGroupStart){ListNodenext=curr->next;curr->next=prev;prev=curr;curr=next;}prevGroupEnd->next=kth;prevGroupEnd=groupStart;}returndummy.next;}ListNodegetKthNode(ListNodestart,intk){while(start&&k--)start=start->next;returnstart;}解析：邊界條件：k大于鏈表長度時(shí)返回原鏈表。每次翻轉(zhuǎn)k個(gè)節(jié)點(diǎn)，并更新指針。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。3.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，判斷二叉樹是否是平衡二叉樹（每個(gè)節(jié)點(diǎn)的左右子樹高度差不超過1）。答案與解析：c++structTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};boolisBalanced(TreeNoderoot){returncheckHeight(root)!=-1;}intcheckHeight(TreeNodenode){if(!node)return0;intleftHeight=checkHeight(node->left);if(leftHeight==-1)return-1;intrightHeight=checkHeight(node->right);if(rightHeight==-1||abs(leftHeight-rightHeight)>1)return-1;returnstd::max(leftHeight,rightHeight)+1;}解析：后序遍歷計(jì)算子樹高度，若發(fā)現(xiàn)不平衡則提前返回。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(h)，h為樹高。4.題目：請(qǐng)編寫一個(gè)函數(shù)，實(shí)現(xiàn)合并K個(gè)排序鏈表，要求時(shí)間復(fù)雜度O(nlogk)。答案與解析：c++include<queue>include<vector>structListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodemergeKLists(std::vector<ListNode>&lists){autocomp=[](ListNodea,ListNodeb){returna->val>b->val;};std::priority_queue<ListNode,std::vector<ListNode>,decltype(comp)>pq(comp);for(ListNodehead:lists){if(head)pq.push(head);}ListNodedummy(0);ListNodetail=&dummy;while(!pq.empty()){ListNodenode=pq.top();pq.pop();tail->next=node;tail=tail->next;if(node->next)pq.push(node->next);}returndummy.next;}解析：使用最小堆（優(yōu)先隊(duì)列）維護(hù)當(dāng)前最小節(jié)點(diǎn)，每次彈出最小節(jié)點(diǎn)并加入其下一節(jié)點(diǎn)。時(shí)間復(fù)雜度O(nlogk)，空間復(fù)雜度O(k)。5.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，找出所有出現(xiàn)次數(shù)超過一半的數(shù)字（至少出現(xiàn)n/2次）。答案與解析：c++include<vector>std::vector<int>majorityElement(std::vector<int>&nums){intcandidate1=0,count1=0;intcandidate2=1,count2=0;for(intnum:nums){if(num==candidate1)count1++;elseif(num==candidate2)count2++;elseif(count1==0){candidate1=num;count1=1;}elseif(count2==0){candidate2=num;count2=1;}else{count1--;count2--;}}std::vector<int>result;count1=count2=0;for(intnum:nums){if(num==candidate1)count1++;elseif(num==candidate2)count2++;}if(count1>nums.size()/2)result.push_back(candidate1);if(count2>nums.size()/2)result.push_back(candidate2);returnresult;}解析：Boyer-Moore多數(shù)投票算法：遍歷時(shí)維護(hù)兩個(gè)候選者及其計(jì)數(shù)。最終驗(yàn)證候選者出現(xiàn)次數(shù)。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。三、系統(tǒng)設(shè)計(jì)（3題，每題20分，共60分）1.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)高并發(fā)的短鏈接生成系統(tǒng)，要求支持高可用、高擴(kuò)展性，并說明主要技術(shù)選型。答案與解析：核心思想：1.分布式ID生成：使用TwitterSnowflake算法生成全局唯一ID。2.短鏈接映射：將ID映射為短鏈接（如62進(jìn)制編碼），存儲(chǔ)在Redis中。3.反向解析：通過反向DNS解析將短鏈接映射回原始URL。技術(shù)選型：-ID生成：Snowflake算法（時(shí)間戳+機(jī)器ID+序列號(hào)）。-存儲(chǔ)：Redis（緩存短鏈接映射）+MySQL（持久化映射關(guān)系）。-負(fù)載均衡：Nginx+HAProxy分發(fā)請(qǐng)求。-服務(wù)發(fā)現(xiàn)：Consul/Etcd動(dòng)態(tài)注冊(cè)服務(wù)。-分布式部署：Kubernetes集群擴(kuò)容。擴(kuò)容方案：-水平擴(kuò)展：增加Redis集群節(jié)點(diǎn)，水平切分MySQL分庫分表。-緩存穿透：設(shè)置短鏈接默認(rèn)緩存（如5分鐘），熱點(diǎn)數(shù)據(jù)持久化。2.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)微博系統(tǒng)，要求支持實(shí)時(shí)消息推送、用戶關(guān)注/取關(guān)、動(dòng)態(tài)發(fā)布等功能，并說明數(shù)據(jù)庫設(shè)計(jì)。答案與解析：核心模塊：1.用戶模塊：用戶信息（ID、昵稱、關(guān)注列表）。2.動(dòng)態(tài)模塊：動(dòng)態(tài)內(nèi)容（ID、用戶ID、內(nèi)容、時(shí)間戳、點(diǎn)贊數(shù)）。3.關(guān)系模塊：關(guān)注關(guān)系（用戶ID、關(guān)注對(duì)象ID）。數(shù)據(jù)庫設(shè)計(jì)：sql--用戶表CREATETABLEusers(user_idBIGINTPRIMARYKEY,nicknameVARCHAR(50),created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);--動(dòng)態(tài)表CREATETABLEposts(post_idBIGINTPRIMARYKEY,user_idBIGINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id));--關(guān)注關(guān)系表CREATETABLEfollows(follower_idBIGINT,followee_idBIGINT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,PRIMARYKEY(follower_id,followee_id),FOREIGNKEY(follower_id)REFERENCESusers(user_id),FOREIGNKEY(followee_id)REFERENCESusers(user_id));實(shí)時(shí)消息推送：-WebSocket：長連接實(shí)時(shí)推送動(dòng)態(tài)。-消息隊(duì)列：Kafka/RabbitMQ處理動(dòng)態(tài)發(fā)布。3.題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)分布式限流系統(tǒng)，要求支持并發(fā)控制、可配置限流規(guī)則，并說明實(shí)現(xiàn)方案。答案與解析：核心方案：1.限流策略：-令牌桶算法：按時(shí)間分配令牌，防止突發(fā)流量。-漏桶算法：勻速流出