华为研发团队面试题目及答案

2026年华为研发团队面试题目及答案一、编程能力测试（共5题，每题10分，总分50分）1.题目：编写一个函数，实现快速排序算法，并对以下列表进行排序：`[34,7,23,32,5,62]`。要求：-输出排序后的列表。-解释快速排序的核心思想。答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)arr=[34,7,23,32,5,62]sorted_arr=quick_sort(arr)print(sorted_arr)#输出：[5,7,23,32,34,62]解析：快速排序的核心思想是分治法。1.选择一个基准值（pivot），通常取中间值。2.将数组分为三部分：小于基准值的、等于基准值的、大于基准值的。3.递归对左右两部分进行排序，最终合并。优点：平均时间复杂度O(nlogn)，空间复杂度O(logn)。2.题目：实现一个LRU（最近最少使用）缓存，容量为3。输入以下键值对：-`put(1,100)`-`put(2,200)`-`get(1)`-`put(3,300)`（会覆盖键2）-`get(2)`答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)cache=LRUCache(3)cache.put(1,100)cache.put(2,200)print(cache.get(1))#输出：100cache.put(3,300)#删除键2print(cache.get(2))#输出：-1解析：LRU通过双向链表和哈希表实现：-哈希表记录键值对，O(1)访问。-双向链表记录访问顺序，头为最近使用，尾为最久未使用。当容量满时，删除链表尾部元素。3.题目：给定一个二叉树，编写代码判断其是否为完全二叉树。例如：1/\23/\45答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_complete_binary_tree(root:TreeNode)->bool:ifnotroot:returnTruequeue=deque([root])end=Falsewhilequeue:node=queue.popleft()ifnotnode:end=Trueelse:ifend:returnFalsequeue.append(node.left)queue.append(node.right)returnTrue构建示例二叉树root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(is_complete_binary_tree(root))#输出：True解析：完全二叉树的判断方法：1.层序遍历，用队列实现。2.遇到空节点后，后续节点必须全部为空。若提前遇到非空节点，则不满足完全二叉树。4.题目：实现一个无重复字符的最长子串函数，输入：`"abcabcbb"`。答案：pythondeflength_of_longest_substring(s:str)->int:char_set=set()left=0max_len=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_lenprint(length_of_longest_substring("abcabcbb"))#输出：3("abc")解析：滑动窗口法：-左右指针分别表示子串起点和终点。-遇到重复字符时，移动左指针并记录最大长度。时间复杂度O(n)，空间复杂度O(min(m,n))，m为字符集大小。5.题目：编写一个函数，找出数组中重复次数超过一半的元素。例如：`[2,2,1,1,1,2,2]`。答案：pythondefmajority_element(nums:list)->int:count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidateprint(majority_element([2,2,1,1,1,2,2]))#输出：2解析：Boyer-Moore多数投票算法：1.遇到数字与候选相同则+1，不同则-1。2.候选者一定是多数元素（超过一半）。时间复杂度O(n)，空间复杂度O(1)。二、算法与数据结构（共5题，每题10分，总分50分）1.题目：给定一个字符串，判断是否可以通过翻转子串使其为回文串。例如：`"abccba"`。答案：pythondefcan_be_palindrome(s:str)->bool:count=[0]26odd=0forcharins:count[ord(char)-ord('a')]+=1ifcount[ord(char)-ord('a')]%2:odd+=1else:odd-=1returnodd<=1print(can_be_palindrome("abccba"))#输出：True解析：回文串最多有一个字符出现奇数次。统计每个字符出现次数，若奇数个字符超过1，则无法通过翻转子串解决。2.题目：实现一个算法，找出无序数组中第三大的数。例如：`[1,2,-2147483648,3]`。答案：pythondefthird_max(nums:list)->int:first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirstprint(third_max([1,2,-2147483648,3]))#输出：1解析：维护三个变量记录前三大的数：1.遍历数组，更新三个变量。2.若当前数大于first，则依次更新。3.若不大于first，则判断是否大于second或third。3.题目：给定一个非负整数数组，返回其中和为特定值的最长子数组长度。例如：`[1,-2,3,5,-1,2]`，和为3。答案：pythondefmax_subarray_len(nums:list,k:int)->int:sum_index={0:-1}max_len=0current_sum=0fori,numinenumerate(nums):current_sum+=numif(current_sum-k)insum_index:max_len=max(max_len,i-sum_index[current_sum-k])ifcurrent_sumnotinsum_index:sum_index[current_sum]=ireturnmax_lenprint(max_subarray_len([1,-2,3,5,-1,2],3))#输出：4("3+5-1+2")解析：前缀和+哈希表：1.记录前缀和第一次出现的位置。2.若`current_sum-k`已存在，则计算子数组长度。3.时间复杂度O(n)，空间复杂度O(n)。4.题目：实现一个函数，统计二叉树中路径和为特定值的路径数量。例如：10/\5-3/\32和为8的路径有：`10+-3+3`。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpath_sum(root:TreeNode,target_sum:int)->int:defdfs(node,current_sum):ifnotnode:return0current_sum+=node.valtotal=1ifcurrent_sum==target_sumelse0total+=dfs(node.left,current_sum)total+=dfs(node.right,current_sum)returntotalreturndfs(root,0)构建示例二叉树root=TreeNode(10)root.left=TreeNode(5)root.right=TreeNode(-3)root.right.left=TreeNode(3)root.right.right=TreeNode(2)print(path_sum(root,8))#输出：2解析：深度优先搜索（DFS）：1.递归遍历每个节点，累加路径和。2.若路径和等于target_sum，则计数+1。3.时间复杂度O(n^2)，可优化为O(n)。5.题目：实现一个函数，找出数组中和为特定值的最短子数组长度。例如：`[2,3,1,2,4,3]`，和为7。答案：pythondefmin_subarray_len(nums:list,target:int)->int:min_len=float('inf')left=0current_sum=0forrightinrange(len(nums)):current_sum+=nums[right]whilecurrent_sum>=target:min_len=min(min_len,right-left+1)current_sum-=nums[left]left+=1returnmin_lenifmin_len!=float('inf')else0print(min_subarray_len([2,3,1,2,4,3],7))#输出：2("4+3")解析：滑动窗口法：1.左右指针分别表示子数组起点和终点。2.若和大于等于target，则尝试缩短窗口。3.时间复杂度O(n)，空间复杂度O(1)。三、系统设计（共3题，每题15分，总分45分）1.题目：设计一个URL短链接系统，要求：-输入长URL，返回短URL。-支持批量生成短链接。-支持按短URL反查长URL。答案：核心设计：1.使用62进制随机码（a-z,A-Z,0-9）生成短链接。2.数据存储：Redis（缓存）+MySQL（持久化）。3.生成算法：pythonimportbase64importhashlibdefencode_base62(num):chars="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"ifnum==0:returnchars[0]result=[]whilenum:result.append(chars[num%62])num//=62return''.join(reversed(result))解析：1.短链接生成：-使用哈希函数（如SHA256）+随机前缀防止冲突。-压缩为62进制减少长度。2.数据存储：-Redis缓存热点数据，MySQL持久化。-主键为短链接，索引长URL。3.反查：-查询Redis，若不存在则MySQL反查。2.题目：设计一个高并发的秒杀系统，要求：-每秒处理大量请求。-防止超卖和作弊。答案：核心设计：1.限流：-Nginx+Lua（前端限流）。-Redis分布式锁（后端限流）。2.防超卖：-使用Redis事务/Lua脚本原子扣减库存。-库存扣减与订单生成合并。3.防作弊：-请求去重（Redis+布隆过滤器）。-验证码+IP/设备限制。解析：1.限流方案：-前端：Nginx配置漏桶/令牌桶算法。-后端：Redis分布式锁（SETNX+EXPIRE）。2.库存扣减：luaifredis.call("DECR",KEYS[1])>=0thenreturn"success"elsereturn"fail"end3.防作弊：-布隆过滤器拦截重复请求。-限制同一IP/设备秒杀次数。3.题目：设计一个分布式消息队列（如Kafka），要求：-支持高吞吐量。-保证消息至少一次传递。-支持消息重试。答案：核心设计：1.生产者：-多线程发送消息，批量发送。-设置消息重试次数（如3次）。2.消费者：-按组分配消费任务。-消息确认机制（ACK）。3.存储：-Kafka分区+副本（至少3副本）。-ISR（In-SyncRep