华为公司招聘工程师面试题及答案详解

2026年华为公司招聘工程师面试题及答案详解一、编程题（3题，每题20分，共60分）1.题目（20分）：编写一个函数，实现将一个字符串中的所有大写字母转换为小写字母，所有小写字母转换为大写字母，其他字符保持不变。例如，输入`"HelloWorld!2026"`，输出`"hELLOwORLD!2026"`。要求不使用内置的`swapCase`方法，并考虑字符串可能包含特殊字符和数字。答案与解析：pythondefswap_case(s:str)->str:result=[]forcharins:if'a'<=char<='z':result.append(char.upper())elif'A'<=char<='Z':result.append(char.lower())else:result.append(char)return''.join(result)解析：-遍历字符串中的每个字符，判断其是否为小写字母（`'a'<=char<='z'`）或大写字母（`'A'<=char<='Z'`）。-小写字母通过`char.upper()`转换为大写，大写字母通过`char.lower()`转换为小写。-其他字符（如数字、标点符号）保持不变。-使用列表`result`收集转换后的字符，最后通过`join`方法合并为字符串。-时间复杂度：O(n)，n为字符串长度；空间复杂度：O(n)。2.题目（20分）：给定一个链表，删除链表中的倒数第n个节点，并返回新的链表头。例如，输入链表`[1,2,3,4,5]`，n=2，删除后链表为`[1,2,3,5]`。要求只遍历一次链表，不使用额外的空间。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefremove_nth_from_end(head:ListNode,n:int)->ListNode:dummy=ListNode(0)dummy.next=headfast=slow=dummy快指针先走n+1步for_inrange(n+1):fast=fast.next快慢指针同时移动，当快指针到达末尾时，慢指针指向待删除节点的前一个节点whilefast:fast=fast.nextslow=slow.next删除节点slow.next=slow.next.nextreturndummy.next解析：-使用双指针法，创建虚拟头节点`dummy`以处理头节点被删除的情况。-快指针`fast`先走`n+1`步，确保删除节点时慢指针`slow`指向待删除节点的前一个节点。-快慢指针同时移动，当快指针到达末尾时，慢指针指向待删除节点的前一个节点。-删除节点：`slow.next=slow.next.next`。-时间复杂度：O(n)；空间复杂度：O(1)。3.题目（20分）：设计一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。缓存容量为`capacity`，`get(key)`返回键对应的值，如果不存在返回-1；`put(key,value)`将键值对插入缓存，如果键已存在则更新值，如果超出容量则删除最久未使用的键。要求使用哈希表和双向链表实现。答案与解析：pythonclassListNode:def__init__(self,key=0,value=0,prev=None,next=None):self.key=keyself.value=valueself.prev=prevself.next=nextclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode()self.tail=ListNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:iflen(self.cache)==self.capacity:self._remove_tail()new_node=ListNode(key,value)self.cache[key]=new_nodeself._add_to_head(new_node)def_move_to_head(self,node:ListNode)->None:self._remove_node(node)self._add_to_head(node)def_remove_node(self,node:ListNode)->None:node.prev.next=node.nextnode.next.prev=node.prevdef_add_to_head(self,node:ListNode)->None:node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_tail(self)->None:tail=self.tail.prevself._remove_node(tail)delself.cache[tail.key]解析：-使用哈希表`cache`存储键和节点，双向链表`head`和`tail`维护最近使用顺序。-`get(key)`：若键存在，移动节点到链表头部并返回值；否则返回-1。-`put(key,value)`：-若键已存在，更新值并移动到链表头部。-若键不存在，若缓存已满，删除链表尾部节点（最久未使用），插入新节点到链表头部。-辅助方法：-`_move_to_head(node)`：将节点移动到链表头部。-`_remove_node(node)`：删除链表中的节点。-`_add_to_head(node)`：将节点插入链表头部。-`_remove_tail()`：删除链表尾部节点。-时间复杂度：O(1)；空间复杂度：O(capacity)。二、算法题（2题，每题25分，共50分）1.题目（25分）：给定一个无序数组`nums`和一个目标值`target`，找出数组中和为目标值的三元组个数。要求不重复计算相同的三元组。例如，输入`nums=[-1,0,1,2,-1,-4]`，`target=0`，输出`[(-1,-1,2),(-1,0,1)]`的数量为2。答案与解析：pythondefthree_sum(nums:list,target:int)->int:nums.sort()n=len(nums)count=0foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:count+=1left_val=nums[left]right_val=nums[right]whileleft<rightandnums[left]==left_val:left+=1whileleft<rightandnums[right]==right_val:right-=1eliftotal<target:left+=1else:right-=1returncount解析：-先对数组排序，方便使用双指针法。-遍历数组，对于每个`nums[i]`，使用双指针`left`和`right`在`i`后面寻找`nums[left]+nums[right]==target-nums[i]`。-若找到三元组，移动`left`和`right`指针跳过重复值，避免重复计算。-时间复杂度：O(n²)；空间复杂度：O(1)。2.题目（25分）：给定一个二叉树，判断其是否是平衡二叉树。平衡二叉树的定义是：对于任意节点，其左右子树的高度差不超过1。例如，输入`[3,9,20,None,None,15,7]`，输出`True`。答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:defcheck(node:TreeNode)->int:ifnotnode:return0left_height=check(node.left)right_height=check(node.right)ifleft_height==-1orright_height==-1orabs(left_height-right_height)>1:return-1returnmax(left_height,right_height)+1returncheck(root)!=-1解析：-使用递归函数`check(node)`计算节点的高度，若不平衡则返回-1。-对于每个节点，分别计算左子树和右子树的高度：-若左子树或右子树不平衡（高度为-1），或左右子树高度差超过1，则整棵树不平衡。-否则，节点高度为左右子树最大高度加1。-最终，若`check(root)`不为-1，则树平衡。-时间复杂度：O(n)；空间复杂度：O(h)，h为树的高度。三、系统设计题（1题，25分）1.题目（25分）：设计一个短链接服务，用户输入长链接，服务返回短链接，点击短链接后重定向到长链接。要求支持高并发、高可用，并具备一定的安全性。说明主要组件、数据结构、算法和部署方案。答案与解析：主要组件：1.API接口层（负载均衡）：接收用户的长链接请求，返回短链接。使用Nginx或HAProxy进行负载均衡。2.服务层（无状态）：处理请求，生成短链接，查询短链接对应的长链接。3.数据库：存储长链接和短链接的映射关系，使用Redis（高速缓存）或MySQL（持久化）。4.缓存层（可选）：使用Redis缓存热点短链接，减少数据库查询。5.反向代理/CDN：高并发时使用反向代理缓存静态资源，CDN进一步加速全球访问。数据结构：-短链接生成：使用Base62编码（a-z,A-Z,0-9），将ID转换为短字符串。例如，`123`转为`1y2`。-数据库表：-`id`（自增主键）-`long_url`（长链接）-`short_code`（短链接码）-`click_count`（点击次数）-`created_at`（创建时间）算法：1.生成短链接码：-生成唯一ID（如自增ID或Snowflake算法）。-ID转为Base62：`id%62`