华为研发工程师面试题库及答案详解

2026年华为研发工程师面试题库及答案详解一、编程语言与数据结构（共5题，每题8分，总分40分）1.题目（8分）：请用C++实现一个函数，输入一个整数数组，返回其中所有“三数之和”等于0的不重复三元组。要求时间复杂度不超过O(n²)。答案：cppinclude<vector>include<algorithm>std::vector<std::vector<int>>threeSum(std::vector<int>&nums){std::vector<std::vector<int>>result;if(nums.size()<3)returnresult;std::sort(nums.begin(),nums.end());for(inti=0;i<nums.size()-2;++i){if(i>0&&nums[i]==nums[i-1])continue;//去重intleft=i+1,right=nums.size()-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==0){result.push_back({nums[i],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(sum<0)left++;elseright--;}}returnresult;}解析：首先对数组进行排序，然后固定第一个数，使用双指针法查找另外两个数。去重通过跳过重复元素实现，避免重复三元组。时间复杂度为O(n²)，空间复杂度为O(1)（不计结果存储）。2.题目（8分）：请用Java实现一个线程安全的LRU缓存，支持get和put操作，要求空间复杂度为O(n)。答案：javaimportjava.util.LinkedHashMap;importjava.util.Map;publicclassLRUCache<K,V>extendsLinkedHashMap<K,V>{privatefinalintcapacity;publicLRUCache(intcapacity){super(capacity,0.75f,true);this.capacity=capacity;}@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<K,V>eldest){returnsize()>capacity;}publicsynchronizedVget(Objectkey){returnsuper.get(key);}publicsynchronizedvoidput(Kkey,Vvalue){super.put(key,value);}}解析：使用`LinkedHashMap`实现LRU缓存，通过重写`removeEldestEntry`方法控制缓存大小。继承`LinkedHashMap`并设置accessOrder为true，使得最近访问的元素在链表头部。线程安全通过`synchronized`关键字实现。3.题目（8分）：请用Python实现一个函数，输入一个二叉树，返回其最大深度。二叉树节点定义如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right答案：pythondefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))解析：采用递归方法，每次计算左子树和右子树的最大深度，取较大值并加1。空节点深度为0。时间复杂度为O(n)，空间复杂度为O(h)（h为树高）。4.题目（8分）：请用Go实现一个函数，输入一个字符串，返回其最长回文子串的长度。答案：gofunclongestPalindrome(sstring)int{iflen(s)<2{returnlen(s)}start,end:=0,0fori:=0;i<len(s);i++{len1:=expandAroundCenter(s,i,i)len2:=expandAroundCenter(s,i,i+1)maxLen:=max(len1,len2)ifmaxLen>end-start{start=i-(maxLen-1)/2end=i+maxLen/2}}returnend-start+1}funcexpandAroundCenter(sstring,left,rightint)int{forleft>=0&&right<len(s)&&s[left]==s[right]{left--right++}returnright-left-1}解析：使用“中心扩展法”，对每个字符尝试扩展最长回文。分别处理奇数和偶数长度的回文。时间复杂度为O(n²)，空间复杂度为O(1)。5.题目（8分）：请用JavaScript实现一个函数，输入一个数组，返回其中出现次数最多的元素及其出现次数。如果有多个，返回第一个。答案：javascriptfunctionmajorityElement(nums){constcount=newMap();letmaxCount=0;letresult=null;for(constnumofnums){if(count.has(num)){count.set(num,count.get(num)+1);}else{count.set(num,1);}if(count.get(num)>maxCount){maxCount=count.get(num);result=[num,maxCount];}}returnresult;}解析：使用哈希表统计每个元素的出现次数，同时记录最大出现次数和对应元素。遍历一次数组，时间复杂度为O(n)，空间复杂度为O(n)。二、算法与设计（共5题，每题10分，总分50分）1.题目（10分）：请设计一个算法，输入一个字符串，判断其是否为有效的括号组合（如"()[]{}"）。答案：pythondefisValid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用栈结构，遍历字符串，遇到右括号时与栈顶左括号匹配。若不匹配或栈为空则无效。遍历结束后栈应为空。时间复杂度为O(n)，空间复杂度为O(n)。2.题目（10分）：请设计一个算法，输入一个正整数n，返回其二进制表示中1的个数。答案：javapublicinthammingWeight(intn){intcount=0;while(n!=0){count+=n&1;n>>=1;}returncount;}解析：通过位运算，每次判断最低位是否为1，并右移一位。统计1的个数。时间复杂度为O(logn)，空间复杂度为O(1)。3.题目（10分）：请设计一个算法，输入一个链表，返回其倒数第k个节点。答案：pythondefgetKthFromEnd(head,k):fast=slow=headfor_inrange(k):ifnotfast:returnNonefast=fast.nextwhilefast:fast=fast.nextslow=slow.nextreturnslow解析：使用双指针法，快指针先走k步，然后快慢指针同时移动，当快指针到末尾时慢指针即为倒数第k个节点。时间复杂度为O(n)，空间复杂度为O(1)。4.题目（10分）：请设计一个算法，输入一个无重复元素的数组，返回其所有子集的列表。答案：pythondefsubsets(nums):result=[]subset=[]defbacktrack(index):result.append(subset.copy())foriinrange(index,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：使用回溯法，遍历所有可能的子集。时间复杂度为O(2^n)，空间复杂度为O(n)。5.题目（10分）：请设计一个算法，输入一个字符串，返回其所有可能的排列组合。答案：javaimportjava.util.ArrayList;importjava.util.List;publicclassPermutations{publicList<String>permute(Strings){List<String>result=newArrayList<>();if(s==null)returnresult;char[]chars=s.toCharArray();backtrack(chars,0,result);returnresult;}privatevoidbacktrack(char[]chars,intindex,List<String>result){if(index==chars.length){result.add(String.valueOf(chars));return;}for(inti=index;i<chars.length;i++){swap(chars,index,i);backtrack(chars,index+1,result);swap(chars,index,i);}}privatevoidswap(char[]chars,inti,intj){chartemp=chars[i];chars[i]=chars[j];chars[j]=temp;}}解析：使用回溯法，每次固定一个字符，递归排列剩余字符。通过交换实现排列。时间复杂度为O(n!),空间复杂度为O(n)。三、系统设计（共3题，每题15分，总分45分）1.题目（15分）：请设计一个高并发的短链接系统，要求支持分布式部署和快速跳转。答案：1.短链接生成：使用哈希算法（如SHA-256）将长链接哈希为固定长度的短码（如6位base62编码）。2.分布式存储：使用Redis或Memcached存储短码与长链接的映射，设置过期时间。3.负载均衡：使用Nginx或HAProxy分发请求到多个后端节点。4.缓存策略：对热门短链接使用本地缓存（如LruCache）减少Redis访问。5.分布式锁：使用ZooKeeper或Redis实现短码生成时的锁，避免冲突。解析：核心在于高效映射和分布式存储。短码生成需保证唯一性和可读性，缓存和负载均衡提升性能。2.题目（15分）：请设计一个实时消息推送系统，要求支持百万级用户和毫秒级响应。答案：1.消息队列：使用Kafka或RabbitMQ处理高并发消息分发。2.发布订阅：用户订阅消息通道，服务端将消息推送到对应通道。3.推送策略：使用WebSocket或Server-SentEvents实现实时推送。4.缓存层：使用Redis存储用户在线状态，减少数据库查询。5.监控告警：使用Prometheus和Grafana监控系统负载和延迟。解析：关键在于高吞吐量的消息队列和低延迟的推送协议。缓存和监控保