阿里巴程序员面试指南编程题目及答案详解

2026年阿里巴程序员面试指南：编程题目及答案详解一、算法设计（共3题，每题15分）1.题目：给定一个非负整数数组`nums`，返回其中范围在`[lower,upper]`之间的所有唯一整数对的数量。数组中的数字可能重复，但只计算不同的整数对。例如，`nums=[1,1,2,2,3]`，`lower=2`，`upper=3`，唯一整数对为`(2,2)`和`(2,3)`，返回数量为2。要求：-时间复杂度不超过`O(nlogn)`。-输出数量，无需具体输出对数。2.题目：实现一个`LRU缓存`（最近最少使用缓存）的`get`和`put`操作。`LRU缓存`支持以下操作：-`get(key)`：如果存在键`key`，返回其值，并将其设为最近最常使用；否则返回-1。-`put(key,value)`：如果`key`已存在，更新其值并设为最近最常使用；如果不存在，添加`key`并设为最近最常使用，如果缓存已满，则删除最近最少使用的项。要求：-使用哈希表和双向链表实现，时间复杂度为`O(1)`。-示例：pythonlru=LRUCache(2)lru.put(1,1)lru.put(2,2)lru.get(1)#返回1lru.put(3,3)#原本1应被删除，缓存变为{2:2,3:3}lru.get(2)#返回-1（未找到）3.题目：给定一个字符串`s`，找到其中最长的`平衡`子字符串。平衡子字符串指由两个不同字符交替组成的子串，如`"ABAB"`或`"AABB"`。返回最长平衡子字符串的长度。要求：-时间复杂度为`O(n)`。-示例：pythons="AABBABABB"#最长平衡子串为"AABBABAB"，长度为6二、系统设计（共2题，每题20分）1.题目：设计一个高并发的短链接系统。要求：-输入长URL，返回短URL（如`/abc123`）。-短URL需唯一且易于生成（如使用62进制编码）。-支持高并发访问和快速跳转回原URL。要求：-描述系统架构（数据库、缓存、负载均衡等）。-解释如何保证唯一性和高可用性。2.题目：设计一个实时消息推送系统（如微信、抖音的即时消息）。要求：-支持百万级用户，消息延迟不超过100ms。-实现用户订阅、消息推送和离线缓存功能。-描述关键组件（消息队列、数据库、推送服务等）及其作用。三、数据库（共2题，每题15分）1.题目：设计一个电商订单表`orders`，包含以下字段：-`order_id`（主键，自增），-`user_id`（用户ID，关联用户表），-`product_id`（商品ID，关联商品表），-`quantity`（数量），-`price`（单价），-`status`（订单状态，如"待支付"、"已发货"等），-`create_time`（创建时间）。要求：-说明字段类型选择（如`INT`、`VARCHAR`等）。-编写SQL查询：-查询总销售额按月分组。-查询未支付订单数按状态分组。2.题目：实现分页查询优化。假设有`users`表（`id`,`name`,`create_time`），编写SQL查询：sqlSELECTid,nameFROMusersORDERBYcreate_timeDESCLIMIT10OFFSET100;要求：-解释`LIMIT`和`OFFSET`的效率问题。-提出优化方案（如使用游标、缓存热门页等）。四、代码实现（共3题，每题10分）1.题目：实现一个`LruCache`的Python版本，支持`get`和`put`操作。2.题目：给定一个链表，反转其前`k`个节点。例如：python输入：1->2->3->4->5,k=2输出：2->1->4->3->53.题目：实现一个简单的LRU缓存，使用Python的`collections.OrderedDict`。答案与解析一、算法设计1.答案：思路：-排序数组，去重后使用双指针法统计满足`lower<=a+b<=upper`的对数。-时间复杂度：`O(nlogn)`（排序）+`O(n)`（双指针）。代码：pythondefcount_pairs(nums,lower,upper):nums=sorted(set(nums))n=len(nums)count=0left,right=0,0whileright<n:ifnums[left]+nums[right]<lower:right+=1elifnums[left]+nums[right]>upper:count+=n-rightleft+=1else:count+=n-rightleft+=1returncount//2解析：-排序去重后，双指针`left`和`right`分别从左向右移动。-当`nums[left]+nums[right]`在范围内时，所有`right`后面的数都满足条件，因此`count+=n-right`。2.答案：思路：-使用哈希表记录节点，双向链表维护最近使用顺序。-`get`时移动节点到链表头部，`put`时判断是否存在并更新位置。代码：pythonclassNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(),Node()self.head.next=self.tailself.tail.prev=self.headdef_remove(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._remove(node)self._add(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:node=self.tail.prevself._remove(node)delself.cache[node.key]解析：-`head`和`tail`是哨兵节点，简化插入和删除操作。-`get`时移动节点到头部，`put`时先删除旧节点（如果存在），再添加新节点。3.答案：思路：-使用状态机判断当前字符与前一个字符是否交替。-用哈希表记录每个状态的出现位置，计算最长交替子串。代码：pythondeflongest_balanced_substring(s:str)->int:state={}max_len=0prev,prev_len=None,0fori,cinenumerate(s):ifprevisNoneorc!=prev:state[(prev,c)]=iprev,prev_len=c,1else:prev_len+=1if(prev,c)instate:max_len=max(max_len,i-state[(prev,c)])else:state[(prev,c)]=iprev,prev_len=c,1returnmax_len解析：-状态`(prev,c)`表示前一个字符和当前字符的组合。-如果遇到重复状态，更新最大长度。二、系统设计1.答案：系统架构：1.URL编码模块：-使用62进制（`a-z`,`A-Z`,`0-9`）将长URL映射为短码（如`abc123`）。-例如：`1000`→`a`，`1000+1`→`b`，循环到`z`后继续`A-Z`。2.数据库：-使用哈希表存储`short_code`→`long_url`，支持快速查找。-使用自增ID生成短码，避免冲突。3.缓存：-高频短URL缓存到Redis，减少数据库访问。4.负载均衡：-多台节点处理请求，使用DNS轮询或Nginx均衡。唯一性和高可用性：-短码生成算法确保唯一性。-数据库主从复制+读写分离保证高可用。2.答案：系统架构：1.消息队列（Kafka/RabbitMQ）：-消息异步发送，支持削峰填谷。2.数据库（Redis/Memcached）：-缓存用户在线状态和离线消息。3.推送服务（WebSocket/Server-SentEvents）：-实时推送消息给客户端。4.离线缓存：-用户离线时保存消息，上线后补发。关键组件作用：-消息队列解耦服务，Redis缓存热点数据，推送服务实现实时通信。三、数据库1.答案：表设计：sqlCREATETABLEorders(order_idINTAUTO_INCREMENTPRIMARYKEY,user_idINTNOTNULL,product_idINTNOTNULL,quantityINTDEFAULT1,priceDECIMAL(10,2)NOTNULL,statusVARCHAR(20)DEFAULT'待支付',create_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,INDEXidx_status(status),INDEXidx_create_time(create_time));SQL查询：sql--总销售额按月分组SELECTDATE_FORMAT(create_time,'%Y-%m')ASmonth,SUM(quantityprice)AStotal_salesFROMordersWHEREstatus='已完成'GROUPBYmonthORDERBYmonth;--未支付订单数按状态分组SELECTstatus,COUNT()AScountFROMordersGROUPBYstatus;解析：-`DECIMAL`用于价格，避免浮点误差。-索引`status`和`create_time`加速查询。2.答案：优化方案：-使用`id`索引：sqlSELECTid,nameFROMusersORDERBYidDESCLIMIT10OFFSET100;这样MySQL可以利用索引跳过前100条。-缓存热点页：sql--使用Redis缓存分页结果SETusers_page_1JSON.stringify([result_list]);-避免大`OFFSET`：改用游标（但需注意事务和锁）。四、代码实现1.答案：pythonfromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.cache=OrderedDict()self.capacity=capacitydefget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:self.cache[key]=valueself.cache.move_to_end(key)iflen(self.cache)>self.capacity:self.cache.popitem(last=False)2.答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_k_group(head:ListNode,k:int)->ListNode:dummy=ListNode(0)dummy.next=headprev_group_end=dummywhileTrue:kth=get_kth_node(prev_group_end,k)ifnotkth:breakgroup_start=prev_group_end.nextnext_group_start=kth.nextprev,curr=kth.next,group_startwhilecurr!=next_group_start:tmp=curr.nextcurr.next=prevprev=currcurr