2026年华为研发部面试题集及答案解析

2026年华为研发部面试题集及答案解析一、编程能力测试（共5题，每题20分）1.题目（20分）：请实现一个函数，输入一个正整数n，返回其二进制表示中1的个数。要求不使用内置函数，时间复杂度不超过O(1)。答案解析：cppintcountOnes(intn){intcount=0;while(n){count+=n&1;n>>=1;}returncount;}解析：通过位运算判断每一位是否为1，右移并统计。时间复杂度为O(logn)，可优化至O(1)通过BrianKernighan算法。2.题目（20分）：给定一个无重复元素的数组nums和一个目标值target，返回所有相加和为target的四个数的组合。要求时间复杂度不超过O(n²)。答案解析：cppvector<vector<int>>fourSum(vector<int>&nums,inttarget){vector<vector<int>>res;sort(nums.begin(),nums.end());for(inti=0;i<nums.size()-3;i++){if(i>0&&nums[i]==nums[i-1])continue;for(intj=i+1;j<nums.size()-2;j++){if(j>i+1&&nums[j]==nums[j-1])continue;intleft=j+1,right=nums.size()-1;while(left<right){longlongtotal=(longlong)nums[i]+nums[j]+nums[left]+nums[right];if(total==target){res.push_back({nums[i],nums[j],nums[left],nums[right]});while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}elseif(total<target){left++;}else{right--;}}}}returnres;}解析：排序后双指针遍历，避免重复解。时间复杂度O(n²)。3.题目（20分）：请实现一个LRU（LeastRecentlyUsed）缓存，支持get和put操作，容量为capacity。要求时间复杂度为O(1)。答案解析：cppclassLRUCache{private:unordered_map<int,list<pair<int,int>>::iterator>cache;list<pair<int,int>>lru;intcapacity;public:LRUCache(intcapacity_):capacity(capacity_){}intget(intkey){autoit=cache.find(key);if(it==cache.end())return-1;lru.splice(lru.begin(),lru,it->second);returnit->second->second;}voidput(intkey,intvalue){autoit=cache.find(key);if(it!=cache.end()){lru.splice(lru.begin(),lru,it->second);it->second->second=value;}else{if(cache.size()==capacity){cache.erase(lru.back().first);lru.pop_back();}lru.emplace_front(key,value);cache[key]=lru.begin();}}};解析：哈希表+双向链表实现，get时移动至头部，put时淘汰最久未使用。4.题目（20分）：请实现一个函数，将字符串中的所有大写字母转换为小写字母，不使用内置函数。答案解析：cppstringtoLowerCase(strings){for(char&c:s){if(c>='A'&&c<='Z'){c+='a'-'A';}}returns;}解析：ASCII码转换，大写与小写差32。5.题目（20分）：给定一个二叉树，判断其是否为平衡二叉树（左右子树高度差不超过1）。答案解析：cppintgetHeight(TreeNodenode){if(!node)return0;intleft=getHeight(node->left);intright=getHeight(node->right);if(left==-1||right==-1||abs(left-right)>1)return-1;returnmax(left,right)+1;}boolisBalanced(TreeNoderoot){returngetHeight(root)!=-1;}解析：后序遍历，遇到不平衡返回-1。二、算法设计（共3题，每题30分）1.题目（30分）：设计一个算法，在大量数据中找出出现次数最多的前K个元素。要求时间复杂度不超过O(nlogK)。答案解析：cppvector<int>topKFrequent(vector<int>&nums,intk){unordered_map<int,int>freq;for(intnum:nums)freq[num]++;//使用小顶堆维护前K个高频元素priority_queue<pair<int,int>,vector<pair<int,int>>,std::function<bool(pair<int,int>,pair<int,int>)>>minHeap([&](pair<int,int>a,pair<int,int>b){returna.second>b.second;});for(auto&[num,count]:freq){if(minHeap.size()<k){minHeap.emplace(num,count);}elseif(count>minHeap.top().second){minHeap.pop();minHeap.emplace(num,count);}}vector<int>res;while(!minHeap.empty()){res.push_back(minHeap.top().first);minHeap.pop();}returnres;}解析：哈希表统计频率，小顶堆维护前K高频，时间复杂度O(nlogK)。2.题目（30分）：设计一个算法，将一个字符串重新排列，使其没有两个相邻的字符相同。如果无法排列，返回空字符串。答案解析：cppstringreorganizeString(strings){unordered_map<char,int>freq;for(charc:s)freq[c]++;//按频率排序vector<pair<char,int>>items(freq.begin(),freq.end());sort(items.begin(),items.end(),[&](constpair<char,int>&a,constpair<char,int>&b){returna.second>b.second;});stringres;intn=s.size();if(items[0].second>(n+1)/2)return"";//双指针法插入intpos=0;for(auto&[c,count]:items){for(inti=0;i<count;i++){if(pos>=n)pos=1;res+=c;pos+=2;}}returnres;}解析：频率优先插入，确保最高频字符间隔分布。3.题目（30分）：设计一个算法，给定一个包含n个节点的无向图，找出所有强连通分量（SCC）。要求时间复杂度不超过O(n²)。答案解析：cppvector<vector<int>>findSCC(vector<vector<int>>&edges){intn=0;for(constauto&edge:edges)n=max(n,edge[0]);n++;vector<vector<int>>adj(n,vector<int>());vector<vector<int>>revAdj(n,vector<int>());for(constauto&edge:edges){adj[edge[0]].push_back(edge[1]);revAdj[edge[1]].push_back(edge[0]);}//Kosaraju算法vector<int>order;vector<bool>visited(n,false);function<void(int)>dfs=[&](intv){visited[v]=true;for(intu:adj[v])if(!visited[u])dfs(u);order.push_back(v);};for(inti=0;i<n;i++)if(!visited[i])dfs(i);vector<int>component(n,-1);intcnt=0;vector<bool>revVisited(n,false);function<void(int)>revDfs=[&](intv){component[v]=cnt;revVisited[v]=true;for(intu:revAdj[v])if(!revVisited[u])revDfs(u);};for(inti=n-1;i>=0;i--){if(!revVisited[order[i]]){revDfs(order[i]);cnt++;}}vector<vector<int>>res(cnt,vector<int>());for(inti=0;i<n;i++)res[component[i]].push_back(i);returnres;}解析：Kosaraju算法两次DFS，时间复杂度O(n²)。三、系统设计（共2题，每题40分）1.题目（40分）：设计一个高并发短链接系统。要求：-支持秒级生成和解析短链接。-每秒可处理百万级请求。-支持自定义域名和统计功能。答案解析：1.架构设计：-存储层：使用Redis集群存储短链接映射（短码→长码），持久化到HBase。-分布式ID生成器：基于TwitterSnowflake算法生成短码（如8位字母数字组合）。-负载均衡：Nginx+LVS分发请求，API网关（Kong）处理认证和限流。-缓存层：CDN缓存热点短链接，Tengine动态解析。2.核心模块：-生成服务：cppstringgenerateShortLink(){longid=Snowflake::nextId();stringshortCode=toBase62(id);while(redis.exists(shortCode))id++;redis.set(shortCode,originalUrl);returndomain+"/"+shortCode;}-解析服务：cppstringparseShortLink(stringshortCode){stringlongCode=redis.get(shortCode);if(!longCode)return"404";redis.hincrby("stats",shortCode,1);returnlongCode;}3.性能优化：-Redis设置高可用和主从复制。-异步写入HBase避免阻塞。-Base62编码减少长度（a-zA-Z0-9共62个字符）。2.题目（40分）：设计一个分布式消息队列（类似Kafka），支持高吞吐、低延迟和消息持久化。要求：-每秒处理百万条消息。-支持至少5分钟的消息重试。-保证消息顺序性。答案解析：1.架构设计：-生产者：多线程异步发送，批量写入（如1KB缓冲区）。-消费者：拉取模式（poll），支持消费组。-存储：Raft协议保证分区数据一致性，LevelDB存储消息。2.核心模块：-分区管理：cppvoidappendMessage(intpar