阿里巴面试题及答案详解

2026年阿里巴面试题及答案详解一、编程题（共3题，每题20分）1.数组中的重复数字（20分）题目：给定一个包含n个整数的数组，其中只有两个数字重复，其余数字均不重复。请找出这两个重复的数字。要求时间复杂度O(n)，空间复杂度O(1)。示例：输入：[3,4,2,3,6,1]输出：[3,4]答案：pythondeffind_duplicates(nums):duplicates=[]fornuminnums:index=abs(num)-1ifnums[index]<0:duplicates.append(abs(num))else:nums[index]=-nums[index]returnduplicates示例print(find_duplicates([3,4,2,3,6,1]))#输出：[3,4]解析：通过遍历数组，将每个数字的绝对值对应的索引位置的值取反。如果遇到已经取反的值，说明该数字重复。该方法利用了数组的空间，实现O(n)时间复杂度和O(1)空间复杂度。2.前序遍历和中序遍历重建二叉树（20分）题目：给定前序遍历和中序遍历的结果，重建二叉树。假设二叉树中没有重复的数字。示例：前序遍历：[3,9,20,15,7]中序遍历：[9,3,15,20,7]答案：pythondefbuild_tree(preorder,inorder):ifnotpreorder:returnNoneroot=TreeNode(preorder[0])mid=inorder.index(preorder[0])root.left=build_tree(preorder[1:mid+1],inorder[:mid])root.right=build_tree(preorder[mid+1:],inorder[mid+1:])returnroot示例preorder=[3,9,20,15,7]inorder=[9,3,15,20,7]root=build_tree(preorder,inorder)解析：前序遍历的第一个数字是根节点，中序遍历中根节点的位置将数组分成左右子树。递归构建左右子树即可。3.最长有效括号（20分）题目：给定一个字符串，包含'('和')'，找出最长的有效括号子串的长度。示例：输入："(()"输出：2答案：pythondeflongest_valid_parentheses(s):stack=[-1]max_len=0fori,charinenumerate(s):ifchar=='(':stack.append(i)else:stack.pop()ifnotstack:stack.append(i)else:max_len=max(max_len,i-stack[-1])returnmax_len示例print(longest_valid_parentheses("(()"))#输出：2解析：使用栈记录括号的索引，遇到'('入栈，')'时出栈。如果栈为空，则将当前索引压入栈；否则，计算最长有效括号长度。二、算法题（共4题，每题25分）1.字符串的排列（25分）题目：给定两个字符串s1和s2，判断s2是否是s1的排列。忽略大小写和空格。示例：s1="Listen"s2="Silent"输出：True答案：pythondefis_permutation(s1,s2):s1=s1.replace("","").lower()s2=s2.replace("","").lower()iflen(s1)!=len(s2):returnFalsecount={}forcharins1:count[char]=count.get(char,0)+1forcharins2:ifcharnotincount:returnFalsecount[char]-=1ifcount[char]<0:returnFalsereturnTrue示例print(is_permutation("Listen","Silent"))#输出：True解析：通过统计字符频率判断是否为排列。忽略大小写和空格，统计后比较频率是否一致。2.盛水最多的容器（25分）题目：给定一个整数数组height，其中height[i]表示第i个位置的高度。返回两个垂直线所能接最多的水。示例：height=[1,8,6,2,5,4,8,3,7]输出：49答案：pythondefmax_area(height):left,right=0,len(height)-1max_area=0whileleft<right:current_area=(right-left)min(height[left],height[right])max_area=max(max_area,current_area)ifheight[left]<height[right]:left+=1else:right-=1returnmax_area示例print(max_area([1,8,6,2,5,4,8,3,7]))#输出：49解析：双指针法，每次移动较矮的一侧，计算当前面积并更新最大面积。3.合并区间（25分）题目：给定一个区间列表，合并所有重叠的区间。示例：intervals=[[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]答案：pythondefmerge_intervals(intervals):ifnotintervals:return[]intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:merged[-1][1]=max(last[1],current[1])else:merged.append(current)returnmerged示例print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))#输出：[[1,6],[8,10],[15,18]]解析：先排序，然后遍历合并重叠的区间。如果当前区间的开始小于等于上一个区间的结束，则合并；否则，添加新区间。4.爬楼梯（25分）题目：假设你正在爬楼梯，每次可以爬1或2步，给定n阶楼梯，有多少种不同的爬法？示例：n=3输出：3答案：pythondefclimb_stairs(n):ifn==1:return1dp=[0](n+1)dp[1],dp[2]=1,2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例print(climb_stairs(3))#输出：3解析：动态规划，dp[i]=dp[i-1]+dp[i-2]，表示爬到第i阶的方法数。三、系统设计题（共2题，每题30分）1.设计一个短URL服务（30分）题目：设计一个短URL服务，要求：-输入长URL，返回短URL。-支持批量生成短URL。-支持将短URL解析回长URL。要求：-短URL长度尽可能短。-高并发场景下性能良好。答案：方案：1.编码方式：使用62进制（a-z,A-Z,0-9）对ID进行编码，如100->"3vA"。2.存储：使用Redis或MySQL存储短URL与长URL的映射。3.ID生成：使用自增ID或Snowflake算法生成唯一ID。4.批量生成：使用队列异步处理。5.解析：对短URL进行解码，查询映射表返回长URL。伪代码：pythondefencode_id(id):chars="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"base=len(chars)encoded=""whileid:encoded=chars[id%base]+encodedid//=basereturnencodedor"0"defdecode_id(encoded):chars="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"base=len(chars)decoded=0forcharinencoded:decoded=decodedbase+chars.index(char)returndecoded解析：-编码解码保证短URL唯一且长度短。-Redis支持高并发缓存映射关系。-Snowflake算法可保证ID唯一性和顺序性。2.设计一个高并发短链接系统（30分）题目：设计一个支持高并发的短链接系统，要求：-短链接生成快速且唯一。-支持分布式部署。-支持自定义短链接前缀。答案：方案：1.架构：-API网关：负责请求路由和负载均衡。-短链接服务：生成短链接并存储映射。-缓存层：Redis缓存热点短链接。-数据库：MySQL存储所有映射关系。2.ID生成：使用分布式ID生成器（如TwitterSnowflake）。3.自定义前缀：用户可指定前缀，通过哈希分配固定前缀段。4.分布式部署：使用Consul或Eureka进行服务发现。伪代码：pythondefgenerate_short_link(long_url,prefix=""):id=snowflake_generator.get_next_id()short_link=f"https://{prefix}{encode_id(id)}"redis.set(short_link,long_url)mysql.insert(short_link,long_url)returnshort_link解析：-Snowflake算法保证ID唯一性和分布式兼容性。-Redis缓存热点链接，降低数据库压力。-自定义前缀满足特殊场景需求。答案解析编程题：1.数组中的重复数字：-利用数组空间存储取反状态，避免额外空间。-时间复杂度O(n)，空间复杂度O(1)。2.重建二叉树：-前序遍历确定根节点，中序遍历分割左右子树。递归构建。3.最长有效括号：-栈记录未匹配的'('索引，计算最大长