2026年华为研发工程师面试宝典及答案

2026年华为研发工程师面试宝典及答案一、编程基础（5题，每题10分，共50分）1.题目：请编写一个函数，实现快速排序算法，并分析其时间复杂度和空间复杂度。答案与解析：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;}解析：快速排序的平均时间复杂度为O(nlogn)，最坏情况为O(n²)（当每次选取的枢轴都是最小或最大元素时）。空间复杂度为O(logn)，主要由递归调用栈决定。2.题目：请实现一个链表反转函数，并说明其边界条件处理。答案与解析：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;}解析：边界条件：空链表或单节点链表无需处理。需注意在遍历过程中正确更新`next`指针，避免链表断裂。3.题目：请编写一个函数，判断一个字符串是否为回文串，不使用额外空间。答案与解析：c++boolisPalindrome(conststd::string&s){intleft=0,right=s.size()-1;while(left<right){if(s[left]!=s[right])returnfalse;left++;right--;}returntrue;}解析：双指针法，从两端向中间遍历，忽略非字母数字字符。时间复杂度O(n)，空间复杂度O(1)。4.题目：请实现一个函数，找出数组中的重复元素（至少重复一次），要求空间复杂度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;}解析：利用数组索引标记元素是否出现过，负数表示已存在。时间复杂度O(n)，空间复杂度O(1)。5.题目：请编写一个函数，实现二分查找，并处理数组重复元素的情况（返回任意一个目标值的索引）。答案与解析：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;}解析：针对重复元素，可返回任意一个匹配索引。时间复杂度O(logn)，但存在重复元素时可能退化为O(n)。二、数据结构与算法（5题，每题10分，共50分）1.题目：请设计一个LRU（最近最少使用）缓存，支持get和put操作，并说明其实现思路。答案与解析：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()};}}};解析：使用双向链表和哈希表实现：链表维护最近使用顺序，哈希表实现O(1)访问。get时将元素移到头部，put时若容量已满则删除最久未使用元素。2.题目：请编写一个函数，实现K个一组翻转链表，并说明边界条件。答案与解析：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大于链表长度时返回原链表。每次翻转k个节点，并更新指针。时间复杂度O(n)，空间复杂度O(1)。3.题目：请设计一个算法，判断二叉树是否是平衡二叉树（每个节点的左右子树高度差不超过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;}解析：后序遍历计算子树高度，若发现不平衡则提前返回。时间复杂度O(n)，空间复杂度O(h)，h为树高。4.题目：请编写一个函数，实现合并K个排序链表，要求时间复杂度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;}解析：使用最小堆（优先队列）维护当前最小节点，每次弹出最小节点并加入其下一节点。时间复杂度O(nlogk)，空间复杂度O(k)。5.题目：请设计一个算法，找出所有出现次数超过一半的数字（至少出现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多数投票算法：遍历时维护两个候选者及其计数。最终验证候选者出现次数。时间复杂度O(n)，空间复杂度O(1)。三、系统设计（3题，每题20分，共60分）1.题目：请设计一个高并发的短链接生成系统，要求支持高可用、高扩展性，并说明主要技术选型。答案与解析：核心思想：1.分布式ID生成：使用TwitterSnowflake算法生成全局唯一ID。2.短链接映射：将ID映射为短链接（如62进制编码），存储在Redis中。3.反向解析：通过反向DNS解析将短链接映射回原始URL。技术选型：-ID生成：Snowflake算法（时间戳+机器ID+序列号）。-存储：Redis（缓存短链接映射）+MySQL（持久化映射关系）。-负载均衡：Nginx+HAProxy分发请求。-服务发现：Consul/Etcd动态注册服务。-分布式部署：Kubernetes集群扩容。扩容方案：-水平扩展：增加Redis集群节点，水平切分MySQL分库分表。-缓存穿透：设置短链接默认缓存（如5分钟），热点数据持久化。2.题目：请设计一个微博系统，要求支持实时消息推送、用户关注/取关、动态发布等功能，并说明数据库设计。答案与解析：核心模块：1.用户模块：用户信息（ID、昵称、关注列表）。2.动态模块：动态内容（ID、用户ID、内容、时间戳、点赞数）。3.关系模块：关注关系（用户ID、关注对象ID）。数据库设计：sql--用户表CREATETABLEusers(user_idBIGINTPRIMARYKEY,nicknameVARCHAR(50),created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);--动态表CREATETABLEposts(post_idBIGINTPRIMARYKEY,user_idBIGINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id));--关注关系表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));实时消息推送：-WebSocket：长连接实时推送动态。-消息队列：Kafka/RabbitMQ处理动态发布。3.题目：请设计一个分布式限流系统，要求支持并发控制、可配置限流规则，并说明实现方案。答案与解析：核心方案：1.限流策略：-令牌桶算法：按时间分配令牌，防止突发流量。-漏桶算法：匀速流出