2026年IT技术面试宝典编程算法资料速算练习题

2026年IT技术面试宝典：编程算法资料速算练习题一、编程基础与数据结构（共5题，每题6分）1.题目：请编写一个函数，实现快速排序算法。输入一个无序的整数数组，输出排序后的数组。要求使用原地排序，不占用额外空间。2.题目：给定一个链表，请编写代码实现反转链表。输入链表的头节点，输出反转后的链表头节点。假设链表节点定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next3.题目：请实现一个哈希表（散列表），支持插入和查询操作。假设键值对为整数，使用链地址法解决哈希冲突。要求实现以下方法：-`put(key,value)`：插入键值对。-`get(key)`：查询键对应的值，如果不存在返回-1。-`hash(key)`：自定义哈希函数，要求均匀分布。4.题目：给定一个二叉树，请编写代码实现层序遍历（广度优先遍历）。输入树的根节点，输出按层序排列的节点值列表。假设二叉树节点定义如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right5.题目：请编写一个函数，实现二分查找算法。输入一个有序数组和一个目标值，返回目标值的索引。如果目标值不存在，返回-1。二、算法设计与复杂度分析（共4题，每题8分）1.题目：设计一个算法，找到无序数组中的第K个最大元素。要求时间复杂度为O(n)，空间复杂度为O(1)。2.题目：给定一个字符串，请判断它是否是一个有效的括号字符串。括号类型包括`()`、`[]`、`{}`，且必须按正确顺序匹配。例如：-输入：`"()"`，输出：`True`。-输入：`"()[]{}"`，输出：`True`。-输入：`"(]"`，输出：`False`。3.题目：设计一个算法，实现字符串的URL化。输入一个字符串，其中可能包含空格，将所有空格替换为`%20`。假设字符串的长度足够容纳替换后的结果。4.题目：给定一个包含n个整数的数组，判断数组中是否存在三个元素a、b、c，使得a+b+c=0。要求返回所有不重复的三元组。例如：-输入：`[-1,0,1,2]`，输出：`[[-1,0,1],[-1,-1,2]]`。三、动态规划与贪心算法（共5题，每题7分）1.题目：给定一个包含非负整数的数组，表示每个位置可以爬升的高度。假设每次可以爬1或2步，请计算达到数组末尾的最小步数。例如：-输入：`[2,3,1,1,4]`，输出：`2`。2.题目：给定一个正整数n，请编写代码实现斐波那契数列的第n项。要求使用动态规划优化时间复杂度至O(n)。3.题目：设计一个贪心算法，实现活动选择问题。输入一组活动，每个活动有开始时间和结束时间，选择尽可能多的不冲突活动。假设活动按结束时间排序。4.题目：给定一个字符串，请编写代码实现最长回文子串的查找。例如：-输入：`"babad"`，输出：`"bab"`或`"aba"`。5.题目：给定一个包含正整数的数组，请编写代码实现最长递增子序列的长度。例如：-输入：`[10,9,2,5,3,7,101,18]`，输出：`4`（子序列为`[2,5,7,101]`）。四、数据库与系统设计（共4题，每题9分）1.题目：设计一个简单的博客系统数据库表结构。要求包含以下功能：-用户表：用户ID、用户名、密码、邮箱。-文章表：文章ID、标题、内容、作者ID、发布时间。-评论表：评论ID、内容、文章ID、用户ID、发布时间。2.题目：设计一个LRU（最近最少使用）缓存系统的数据结构。要求支持以下操作：-`get(key)`：获取键对应的值，如果不存在返回-1。-`put(key,value)`：插入键值对，如果键已存在则更新值。缓存容量固定，超出容量时淘汰最久未使用的元素。3.题目：设计一个分布式数据库的读写分离方案。要求实现以下功能：-写操作路由到主数据库。-读操作可路由到主数据库或从数据库（负载均衡）。-主从数据库同步机制（延迟容忍）。4.题目：设计一个高并发的秒杀系统。要求支持以下功能：-用户下单时，需判断库存是否充足。-防止超卖和恶意刷单。-系统需支持高并发（例如每秒处理10000+请求）。五、综合应用与场景题（共3题，每题10分）1.题目：假设你正在开发一个外卖平台，请设计一个算法，根据用户的历史订单数据，推荐用户可能感兴趣的外卖商家。要求考虑以下因素：-用户历史订单频次高的商家优先推荐。-商家评分和距离也需纳入考虑。-使用协同过滤或基于内容的推荐算法。2.题目：设计一个分布式搜索引擎的索引更新机制。要求实现以下功能：-新网页数据接入时，需快速更新索引。-索引分片存储，支持水平扩展。-搜索时需保证低延迟和高吞吐量。3.题目：假设你正在开发一个实时监控系统，请设计一个算法，检测系统中的异常流量。要求考虑以下场景：-流量突增或突降可能表示攻击或故障。-使用滑动窗口或时间序列分析方法。-要求算法需低误报率，并能实时响应。答案与解析一、编程基础与数据结构1.快速排序pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：-选择中间值作为基准（pivot），将数组分为小于、等于、大于三部分。-递归对左右子数组排序，合并结果。-原地排序通过切片实现，不额外占用空间。2.反转链表pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：-使用三个指针`prev`、`current`、`next_node`遍历链表。-逐个反转节点指针，直到遍历结束。-时间复杂度O(n)，空间复杂度O(1)。3.哈希表pythonclassHashTable:def__init__(self,size=100):self.size=sizeself.table=[[]for_inrange(size)]defhash(self,key):returnkey%self.sizedefput(self,key,value):index=self.hash(key)forpairinself.table[index]:ifpair[0]==key:pair[1]=valuereturnself.table[index].append([key,value])defget(self,key):index=self.hash(key)forpairinself.table[index]:ifpair[0]==key:returnpair[1]return-1解析：-使用链地址法解决冲突，每个槽位存储链表。-哈希函数采用模运算，保证均匀分布。-插入时先查找是否已存在，更新或新增。4.层序遍历pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevel_order(root):ifnotroot:return[]queue=deque([root])result=[]whilequeue:node=queue.popleft()result.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnresult解析：-使用队列实现BFS，逐层遍历节点。-每次弹出节点，并将左右子节点加入队列。-时间复杂度O(n)，空间复杂度O(n)。5.二分查找pythondefbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid-1return-1解析：-初始化左右指针，逐次缩小搜索范围。-每次比较中间值，调整指针位置。-时间复杂度O(logn)，空间复杂度O(1)。二、算法设计与复杂度分析1.第K个最大元素pythondeffind_kth_largest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,len(nums)-k)解析：-使用快速选择算法，时间复杂度O(n)。-通过随机选择基准点，减少最坏情况概率。-避免额外空间占用。2.有效括号字符串pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：-使用栈匹配括号，左括号入栈，右括号匹配栈顶。-栈为空表示匹配成功，否则失败。-时间复杂度O(n)，空间复杂度O(n)。3.字符串URL化pythondefreplace_space(s):returns.replace('','%20')解析：-直接使用字符串替换函数，简单高效。-适用于语言内置函数支持的场景。4.三数之和pythondefthree_sum(nums):nums.sort()result=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnresult解析：-先排序，避免重复解。-双指针法，时间复杂度O(n²)。-跳过重复值，防止结果重复。三、动态规划与贪心算法1.爬楼梯pythondefclimbStairs(n):ifn==1:return1dp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：-动态规划求解，dp[i]表示到达第i阶的方法数。-递推关系：dp[i]=dp[i-1]+dp[i-2]。-时间复杂度O(n)，空间复杂度O(n)。2.斐波那契数列pythondeffib(n):ifn==0:return0dp=[0](n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：-同爬楼梯，使用动态规划存储中间结果。-优化空间至O(1)：仅记录前两个值。3.活动选择pythondefactivity_selection(start,finish):events=sorted(zip(start,finish))result=[]last_finish=0fors,finevents:ifs>=last_finish:result.append((s,f))last_finish=freturnresult解析：-按结束时间排序活动。-选择最早结束且不冲突的活动。-贪心策略：每次选择最晚开始的活动。4.最长回文子串pythondeflongest_palindrome(s):ifnots:return""start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpand_from_center(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：-双指针法扩展回文中心。-中心可以是单个字符或两个字符。-时间复杂度O(n²)，空间复杂度O(1)。5.最长递增子序列pythondeflength_of_LIS(nums):ifnotnums:return0dp=[1]len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)解析：-dp[i]表示以i结尾的最长递增子序列长度。-递推关系：dp[i]=max(dp[j]+1)，其中nums[j]<nums[i]。-时间复杂度O(n²)，可优化至O(nlogn)。四、数据库与系统设计1.博客系统数据库表结构sql--用户表CREATETABLEusers(user_idINTAUTO_INCREMENTPRIMARYKEY,usernameVARCHAR(50)UNIQUENOTNULL,passwordVARCHAR(255)NOTNULL,emailVARCHAR(100)UNIQUENOTNULL);--文章表CREATETABLEarticles(article_idINTAUTO_INCREMENTPRIMARYKEY,titleVARCHAR(255)NOTNULL,contentTEXTNOTNULL,author_idINT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(author_id)REFERENCESusers(user_id));--评论表CREATETABLEcomments(comment_idINTAUTO_INCREMENTPRIMARYKEY,contentTEXTNOTNULL,article_idINT,user_idINT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(article_id)REFERENCESarticles(article_id),FOREIGNKEY(user_id)REFERENCESusers(user_id));解析：-用户表存储用户信息，主键为用户ID。-文章表关联用户ID，表示作者。-评论表关联文章ID和用户ID，实现多对多关系。2.LRU缓存pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=deque()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.