2026年算法面试题及编程题集

2026年算法面试题及编程题集一、编程实现题（共5题，每题10分）题目1（10分）：实现LRU缓存机制题目描述：设计一个LRU（LeastRecentlyUsed）缓存机制，支持以下操作：1.`get(key)`：获取键`key`对应的值，如果键存在，则返回值并将该键值对移动到缓存的前端（表示最近使用过）；如果键不存在，返回-1。2.`put(key,value)`：插入或更新键值对。如果键已存在，则更新其值并移动到缓存前端；如果键不存在，则插入该键值对，如果缓存已满，则删除最久未使用的键值对（即缓存尾部的键值对）。要求：-使用哈希表和双向链表实现，时间复杂度为O(1)。-请给出代码实现和关键步骤解析。答案与解析：代码实现（Python）：pythonclassDLinkedNode: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=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):Alwaysaddthenewnoderightafterhead.node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):Removeanexistingnodefromthelinkedlist.prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):Movecertainnodeinbetweentothehead.self._remove_node(node)self._add_node(node)def_pop_tail(self):Popthecurrenttail.res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1Movetheaccessednodetothehead;self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:Popthetailtail=self._pop_tail()delself.cache[tail.key]else:Updatethevalue.node.value=valueself._move_to_head(node)解析：1.数据结构选择：-哈希表：用于快速查找键是否存在（O(1)时间复杂度）。-双向链表：用于维护缓存的使用顺序，头节点表示最近使用，尾节点表示最久未使用。2.核心操作：-`get(key)`：通过哈希表查找节点，若存在则移动到链表头部；若不存在返回-1。-`put(key,value)`：若键已存在，更新值并移动到头部；若键不存在，创建新节点并添加到头部，若超出容量则删除链表尾部节点（最久未使用）。3.边界处理：-空链表初始化时，头尾节点互相指向。-删除节点时，调整相邻节点的指针。题目2（10分）：实现二叉树的层序遍历题目描述：给定一个二叉树，返回其层序遍历（即按从上到下、从左到右的顺序遍历树的每一层）。示例：输入：`[3,9,20,null,null,15,7]`输出：`[[3],[9,20],[15,7]]`要求：-使用队列实现，时间复杂度为O(N)，空间复杂度为O(N)。-请给出代码实现和关键步骤解析。答案与解析：代码实现（Python）：pythonfromcollectionsimportdequefromtypingimportList,OptionalclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassSolution:deflevelOrder(self,root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult解析：1.数据结构选择：-队列：用于按层次遍历，先进先出。2.核心步骤：-初始化队列并添加根节点。-循环处理队列中的节点，每次处理当前层的所有节点，将其子节点加入队列。-每层遍历结束后，将当前层的节点值添加到结果列表中。3.边界处理：-根节点为空时，直接返回空列表。-每层遍历的节点数量可能不同，通过`level_size`控制。题目3（10分）：实现快速排序题目描述：给定一个数组`nums`，使用快速排序算法对其进行原地排序，返回排序后的数组。示例：输入：`[4,1,3,2,6,5,8,7]`输出：`[1,2,3,4,5,6,7,8]`要求：-使用Hoare分区法实现，时间复杂度为O(NlogN)，空间复杂度为O(logN)。-请给出代码实现和关键步骤解析。答案与解析：代码实现（Python）：pythondefquick_sort(nums:List[int],low:int,high:int)->List[int]:iflow<high:pivot_index=partition(nums,low,high)quick_sort(nums,low,pivot_index-1)quick_sort(nums,pivot_index+1,high)returnnumsdefpartition(nums:List[int],low:int,high:int)->int:pivot=nums[high]i=low-1forjinrange(low,high):ifnums[j]<=pivot:i+=1nums[i],nums[j]=nums[j],nums[i]nums[i+1],nums[high]=nums[high],nums[i+1]returni+1Exampleusage:nums=[4,1,3,2,6,5,8,7]print(quick_sort(nums,0,len(nums)-1))解析：1.核心思想：-选择一个基准值（pivot），将数组分为两部分：左部分所有元素≤pivot，右部分所有元素>pivot。-递归对左右两部分进行排序。2.Hoare分区法步骤：-初始化`i`为`low-1`，`j`从`low`到`high-1`。-若`nums[j]<=pivot`，则`i`右移，交换`nums[i]`和`nums[j]`。-最后将`pivot`与`i+1`位置的元素交换，返回`i+1`作为分界点。3.时间与空间复杂度：-平均时间复杂度O(NlogN)，最坏O(N²)（当基准值选择不均匀时）。-空间复杂度O(logN)（递归栈深度）。题目4（10分）：实现最长回文子串题目描述：给定一个字符串`s`，返回其最长回文子串的长度。示例：输入：`"babad"`输出：`3`（"bab"或"aba"）要求：-使用动态规划或中心扩展法实现，时间复杂度为O(N²)，空间复杂度为O(N)。-请给出代码实现和关键步骤解析。答案与解析：代码实现（中心扩展法）：pythondeflongest_palindrome(s:str)->int:ifnots:return0start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)#Oddlengthpalindromelen2=expand_from_center(s,i,i+1)#Evenlengthpalindromemax_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returnend-start+1defexpand_from_center(s:str,left:int,right:int)->int:whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1Exampleusage:s="babad"print(longest_palindrome(s))解析：1.核心思想：-回文串以某个中心扩展，分为奇数长度（如"aba"）和偶数长度（如"abba"）。-遍历每个字符作为中心，尝试向两边扩展。2.步骤：-初始化`start`和`end`记录最长回文子串的起始和结束位置。-对每个字符，分别以它本身和它与其后字符为中心扩展，取最大长度。-更新最长回文子串的起始和结束位置。3.时间与空间复杂度：-时间复杂度O(N²)，因为每个中心最多扩展2N次。-空间复杂度O(1)，仅用常数额外空间。题目5（10分）：实现二分查找题目描述：给定一个有序数组`nums`和一个目标值`target`，返回`target`在数组中的索引。如果不存在，返回`-1`。示例：输入：`nums=[1,2,3,4,5,6,7],target=3`输出：`2`要求：-使用二分查找算法实现，时间复杂度为O(logN)。-请给出代码实现和关键步骤解析。答案与解析：代码实现（Python）：pythondefbinary_search(nums:List[int],target:int)->int:left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1Exampleusage:nums=[1,2,3,4,5,6,7]target=3print(binary_search(nums,target))解析：1.核心思想：-在有序数组中，每次将查找范围缩小一半，直到找到目标值或范围为空。2.步骤：-初始化`left`为0，`right`为数组长度减1。-计算中间位置`mid`，比较`nums[mid]`与`target`：-相等：返回`mid`。-`nums[mid]<target`：在右半部分查找（`left=mid+1`）。-`nums[mid]>target`：在左半部分查找（`right=mid-1`）。-若未找到，返回`-1`。3.时间与空间复杂度：-时间复杂度O(logN)，每次查找范围减半。-空间复杂度O(1)，仅用常数额外空间。二、算法设计题（共3题，每题15分）题目6（15分）：设计LRU缓存的高效实现题目描述：设计一个LRU缓存机制，要求：1.支持高并发访问（至少支持1000个并发`get`或`put`操作）。2.优化内存占用，避免不必要的空间浪费。3.提供详细的实现思路和优化策略。要求：-阐述数据结构选择、并发控制、内存优化方法，并给出伪代码或关键实现。答案与解析：实现思路：1.数据结构选择：-哈希表+双向链表：-哈希表存储键到链表节点的映射，O(1)时间复杂度查找。-双向链表维护访问顺序，头节点为最近使用，尾节点为最久未使用。2.并发控制：-锁机制：-使用读写锁（Read-WriteLock），允许多个`get`操作并发执行，但`put`操作需要独占写锁。-Python中可用`threading.Lock`或`threading.RLock`实现。3.内存优化：-节点共享：-在`put`操作中，若键已存在，更新值并移动节点，避免重复创建节点。-若键不存在且缓存已满，删除链表尾节点时，同时从哈希表中删除对应键，避免内存泄漏。伪代码：pythonclassConcurrentLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headself.lock=threading.RLock()#Read-WriteLockdefget(self,key:int)->int:withself.lock:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:withself.lock:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:self._pop_tail()else:node.value=valueself._move_to_head(node)优化策略：-锁粒度细化：对于读多写少的场景，可考虑使用分段锁或无锁数据结构（如原子操作）。-内存池：预先分配节点内存，减少动态分配开销。题目7（15分）：设计一个高效的URL短缩服务题目描述：设计一个URL短缩服务（如TinyURL），要求：1.将长URL转换为短URL，短URL应唯一且尽量短。2.支持将短URL解析回原始长URL。3.优化高并发下的响应速度和存储效率。要求：-提供数据结构设计、URL生成与解析算法，并说明优化方案。答案与解析：数据结构设计：1.短URL生成：-使用62进制（a-z、A-Z、0-9）对ID进行编码，如`1→"a"`,`2→"b"`,...,`62→"z"`,`63→"A"`,...。-例如，ID=1234→"zZ"（62进制表示）。2.存储：-哈希表：存储短URL到长URL的映射，O(1)时间复杂度查询。-数据库：支持高并发写入和查询，如Redis或MySQL。3.唯一性保证：-使用自增ID或UUID，结合哈希函数确保短URL唯一。算法实现：1.生成短URL：-生成唯一ID（自增或UUID）。-将ID编码为62进制字符串。-存储短URL到长URL的映射。2.解析短URL：-将短URL解码为ID。-通过哈希表查询长URL。伪代码：pythonimportbase64importuuidclassURLShortener:def__init__(self):self.url_map={}self.base62="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"self.id_counter=1#Oruseuuid.uuid4()def_encode_id(self,num:int)->str:ifnum==0:returnself.base62[0]base=len(self.base62)res=[]whilenum>0:res.append(self.base62[num%base])num//=basereturn''.join(res[::-1])def_decode_id(self,short_url:str)->int:base=len(self.base62)num=0forcharinshort_url:num=numbase+self.base62.index(char)returnnumdefinsert(self,long_url:str)->str:short_id=self._encode_id(self.id_counter)self.url_map[short_id]=long_urlself.id_counter+=1returnf"/{short_id}"defget(self,short_url:str)->str:id_part=short_url.split('/')[-1]returnself.url_map.get(id_part,"URLnotfound")优化方案：-分布式存储：使用Redis集群或分布式数据库，支持高并发读写。-缓存机制：对热点短URL进行缓存，减少数据库查询。-异步处理：生成短URL时采用异步写入，提升响应速度。题目8（15分）：设计一个高效的股票交易系统题目描述：设计一个股票交易系统，支持以下功能：1.用户可以下单买入或卖出股票。2.系统实时计算当前可交易的股票数量。3.优化高并发下的交易处理效率和数据一致性。要求：-提供数据结构设计、交易逻辑实现，并说明优化策略。答案与解析：数据结构设计：1.库存管理：-使用哈希表存储股票ID到库存数量的映射。-使用读写锁控制并发访问。2.订单管理：-使用队列存储待执行的买入和卖出订单，按时间或优先级排序。-使用事务保证订单处理的原子性。交易逻辑实现：1.买入/卖出订单：-买入时检查库存是否足够，若不足则排队等待。-卖出时直接扣减库存，若库存不足则取消订单。2.实时库存计算：-通过发布-订阅模式，库存变动时实时通知客户端。伪代码：pythonfrom