阿里巴算法工程师面试题及答案解析

2026年阿里巴算法工程师面试题及答案解析一、编程题（共3题，每题15分，总分45分）题目1（15分）：实现一个函数，输入一个无重复元素的整数数组，返回所有可能的子集（不包含空集）。要求使用递归方法，并输出子集的数量。示例输入：`[1,2,3]`示例输出：`[[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`，子集数量为`7`。答案与解析：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示例调用print(subsets([1,2,3]))解析：1.使用递归的回溯算法，通过`index`控制当前遍历的位置，避免重复选择元素。2.每次选择一个元素后，递归调用`backtrack(i+1)`继续选择下一个元素，直到所有元素被遍历。3.子集的数量为`2^n`（包含空集），不包含空集时为`2^n-1`。题目2（15分）：给定一个包含重复数字的数组，返回所有不重复的全排列。要求不使用内置库，并说明时间复杂度。示例输入：`[1,1,2]`示例输出：`[[1,1,2],[1,2,1],[2,1,1]]`。答案与解析：pythondefpermuteUnique(nums):defbacktrack(path,used):iflen(path)==len(nums):result.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path,used)path.pop()used[i]=Falsenums.sort()result=[]used=[False]len(nums)backtrack([],used)returnresult示例调用print(permuteUnique([1,1,2]))解析：1.先对数组排序，通过`used`数组记录每个元素是否被使用。2.使用`used`和`nums[i]==nums[i-1]&&!used[i-1]`避免重复排列。3.时间复杂度为`O(n!n)`，因为全排列的时间复杂度为`O(n!)`，每次检查`used`和相邻元素需要`O(n)`。题目3（15分）：实现LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。要求不使用内置库，并说明时间复杂度。示例输入：-`put(1,1)`→缓存为`{1:1}`-`put(2,2)`→缓存为`{1:1,2:2}`-`get(1)`→返回`1`，缓存更新为`{2:2,1:1}`-`put(3,3)`→缓存为`{2:2,1:1,3:3}`（删除`2`）-`get(2)`→返回`-1`（未命中）答案与解析：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)示例调用lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#输出1lru.put(3,3)print(lru.get(2))#输出-1解析：1.使用哈希表`cache`记录键值对，`order`列表记录访问顺序。2.`get`操作时，将键移动到`order`末尾表示最近使用。3.`put`操作时，如果键已存在则更新值并移动到末尾；如果超出容量，删除`order`第一个元素对应的键。4.时间复杂度为`O(1)`，因为哈希表和列表操作均为常数时间。二、算法题（共4题，每题10分，总分40分）题目1（10分）：给定一个整数数组，返回和最大的连续子数组的和。要求不使用内置函数，并说明时间复杂度。示例输入：`[-2,1,-3,4,-1,2,1,-5,4]`示例输出：`6`（子数组`[4,-1,2,1]`）。答案与解析：pythondefmaxSubArray(nums):max_sum=nums[0]current_sum=nums[0]foriinrange(1,len(nums)):current_sum=max(nums[i],current_sum+nums[i])max_sum=max(max_sum,current_sum)returnmax_sum示例调用print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))解析：1.使用动态规划，`current_sum`记录当前子数组的最大和，`max_sum`记录全局最大和。2.每次选择`nums[i]`或`current_sum+nums[i]`，确保不产生负和。3.时间复杂度为`O(n)`，只需遍历一次数组。题目2（10分）：给定一个字符串，判断是否可以通过删除一些字符使其变为回文串。不使用内置函数，并说明时间复杂度。示例输入：`"abca"`示例输出：`True`（删除`b`后为`"aca"`）。答案与解析：pythondefvalidPalindrome(s:str)->bool:defis_palindrome(left,right):whileleft<right:ifs[left]!=s[right]:returnis_palindrome(left+1,right)oris_palindrome(left,right-1)left+=1right-=1returnTruereturnis_palindrome(0,len(s)-1)示例调用print(validPalindrome("abca"))解析：1.使用双指针法，每次比较`left`和`right`字符，如果不相等则尝试删除左边或右边的字符。2.递归判断删除后是否为回文串，时间复杂度为`O(n^2)`。题目3（10分）：给定两个无重复元素的数组`nums1`和`nums2`，返回它们的交集。不使用内置函数，并说明时间复杂度。示例输入：`nums1=[1,2,3,4]`,`nums2=[3,4,5,6]`示例输出：`[3,4]`。答案与解析：pythondefintersection(nums1,nums2):result=[]nums1.sort()nums2.sort()i,j=0,0whilei<len(nums1)andj<len(nums2):ifnums1[i]==nums2[j]:ifnotresultorresult[-1]!=nums1[i]:result.append(nums1[i])i+=1j+=1elifnums1[i]<nums2[j]:i+=1else:j+=1returnresult示例调用print(intersection([1,2,3,4],[3,4,5,6]))解析：1.先对两个数组排序，然后使用双指针法比较元素，相同的加入结果列表。2.时间复杂度为`O(nlogn+mlogm)`，因为排序需要`O(nlogn+mlogm)`。题目4（10分）：给定一个正整数`n`，判断是否为快乐数。快乐数的定义是：将该数分解为各位数字的平方和，重复此过程，最终得到`1`即为快乐数。不使用内置函数，并说明时间复杂度。示例输入：`19`示例输出：`True`（`1^2+9^2=82`,`8^2+2^2=68`,`6^2+8^2=100`,`1^2+0^2+0^2=1`）。答案与解析：pythondefisHappy(n:int)->bool:defget_next(number):total_sum=0whilenumber>0:digit=number%10total_sum+=digitdigitnumber=number//10returntotal_sumseen=set()whilen!=1andnnotinseen:seen.add(n)n=get_next(n)returnn==1示例调用print(isHappy(19))解析：1.使用哈希表`seen`记录已访问的数字，避免无限循环。2.每次计算`get_next`，直到`n==1`或出现重复数字。3.时间复杂度为`O(logn)`，因为每次计算数字位数最多`logn`。三、系统设计题（共2题，每题25分，总分50分）题目1（25分）：设计一个简单的URL短链接服务，要求：1.支持将长URL转换为短URL，并支持反向解析。2.短URL应全局唯一且易于生成。3.说明主要数据结构和算法，并讨论高并发下的优化方案。答案与解析：1.数据结构：-使用哈希表`long2short`存储长URL到短URL的映射。-短URL可以使用随机生成或自增ID（如`1_6f8a0c7`）。-使用Redis或MySQL存储映射关系，支持高并发读写。2.算法：-长URL到短URL：生成短码（如62位随机码），存入`long2short`。-短URL到长URL：通过哈希表快速查找。3.高并发优化：-使用分布式缓存（如RedisCluster）分片存储，避免单点瓶颈。-短码生成使用雪花算法或UUID保证唯一性。-读多写少的场景可使用Trie树优化反向解析。题目2（25分）：设计一个实时推荐系统，要求：1.输入用户行为（如点击、购买），输出个性化推荐商品。2.支持离线计算和实时推荐，说明主要算法。3.讨论如何处理数据冷启动和稀疏性问题。答案与解析：1.数据结构：-使用矩阵分解（如ALS）处理用户-商品交互矩阵。-实时推荐使用LRU缓存热门