2026年IT行业笔试算法仿真题解析

2026年IT行业笔试算法仿真题解析一、编程实现题（共3题，每题15分，总分45分）题目1（15分）：题目描述：给定一个由小写字母组成的字符串`s`和一个正整数`k`，要求将字符串`s`中所有长度为`k`的子串翻转。注意，翻转子串时，子串内部字符顺序反转，但子串位置不变。示例输入：s="abcdefg",k=2示例输出："cbadefg"示例解释：字符串`"abcdefg"`中，长度为`2`的子串有`"ab"`,`"bc"`,`"cd"`,`"de"`,`"ef"`,`"fg"`。翻转后，子串顺序不变，但每个子串内部字符顺序反转，结果为`"cbadefg"`。要求：-请实现一个函数`reverse_substrings(s:str,k:int)->str`，返回翻转后字符串。-不能使用额外的字符串构建方法，需原地修改。题目2（15分）：题目描述：给定一个由正整数组成的数组`nums`，和一个正整数`target`。要求找到数组中所有和为`target`的不重复的四元组，并返回这些四元组的列表。四元组的顺序不重要，但结果列表中不能有重复的四元组。示例输入：nums=[1,2,3,4,5,6],target=7示例输出：``[[1,2,4],[1,3,3]]示例解释：所有和为`7`的不重复四元组为`[1,2,4]`和`[1,3,3]`，其他组合如`[1,1,2,3]`因重复或顺序不同不包含在内。要求：-请实现一个函数`four_sum(nums:List[int],target:int)->List[List[int]]`，返回所有满足条件的四元组。-不能使用重复的四元组，结果需排序。题目3（15分）：题目描述：给定一个包含`n`个整数的数组`nums`，和一个正整数`k`。要求找到数组中所有长度为`k`的子数组的最大和，并返回该最大和。子数组顺序不重要，但需遍历所有可能的子数组。示例输入：nums=[1,3,-1,2,-1,2],k=3示例输出：6示例解释：所有长度为`3`的子数组为`[1,3,-1]`,`[3,-1,2]`,`[-1,2,-1]`,`[2,-1,2]`，其和分别为`3`,`4`,`-2`,`3`，最大和为`6`。要求：-请实现一个函数`max_subarray_sum(nums:List[int],k:int)->int`，返回最大子数组和。-不能使用暴力枚举，需优化时间复杂度。二、算法设计题（共2题，每题20分，总分40分）题目4（20分）：题目描述：假设你正在设计一个实时推荐系统，用户每次浏览商品时，系统需要根据用户的历史浏览记录和商品相似度，推荐`k`个最相关的商品。商品相似度可以通过一个预先计算的`nxn`矩阵`similarity`表示，其中`similarity[i][j]`表示商品`i`和商品`j`的相似度。要求：1.请设计一个算法，输入用户当前浏览的商品`current`和`k`，返回推荐的商品列表（按相似度从高到低排序）。2.假设用户历史浏览记录存储在一个集合`history`中，且`similarity`矩阵可以通过API调用获取。示例输入：current=5,k=3history={1,3,7},similarity=[[0,0.2,0,0.5,0,0.1,0],[0.2,0,0.3,0.4,0,0,0],[0,0.3,0,0.1,0.2,0,0],[0.5,0.4,0.1,0,0.3,0,0],[0,0,0,0.3,0,0.4,0],[0.1,0,0,0,0.4,0,0.5],[0,0,0,0,0,0.5,0]]示例输出：[4,6,2]示例解释：商品`5`与商品`4`的相似度为`0.3`，与商品`6`为`0.4`，与商品`2`为`0.3`，其他商品相似度更低，因此推荐`[4,6,2]`。要求：-算法需考虑历史记录的权重，即历史浏览商品与当前商品的相似度更高。-时间复杂度需尽可能优化。题目5（20分）：题目描述：假设你正在设计一个分布式数据库缓存系统，需要根据数据访问频率动态调整缓存策略。系统中有`n`个热点数据节点，每个节点有一个访问频率`freq`。当前缓存容量为`capacity`，要求每次访问时：1.若节点在缓存中，增加其频率并移动到缓存末尾（模拟LRU策略）；2.若节点不在缓存中，根据频率选择一个频率最低的节点替换。要求：1.请设计一个数据结构实现该缓存系统，支持`get(node_id:int)`和`set(node_id:int)`操作；2.需记录节点频率变化，并在`set`时选择合适的节点替换。示例输入：capacity=3,nodes={1:1,2:2,3:3}operations=["get",1,"set",4,5,"get",1,"set",6,6,"get",4]示例输出：None,None,1,None示例解释：-`get(1)`：节点`1`频率增加，移动到末尾，返回`1`；-`set(4,5)`：节点`4`加入缓存，替换频率最低的`3`；-`get(1)`：节点`1`在缓存中，返回`1`；-`set(6,6)`：节点`6`加入缓存，替换频率最低的`4`。要求：-数据结构需支持高效频率更新和替换操作。答案与解析一、编程实现题题目1答案：pythondefreverse_substrings(s:str,k:int)->str:s=list(s)n=len(s)foriinrange(0,n,k):end=min(i+k-1,n-1)whilei<end:s[i],s[end]=s[end],s[i]i+=1end-=1return''.join(s)解析：-将字符串转换为列表以便原地修改；-按步长`k`遍历字符串，翻转每个长度为`k`的子串；-使用双指针法翻转子串内部字符顺序。题目2答案：pythonfromtypingimportListdeffour_sum(nums:List[int],target:int)->List[List[int]]:nums.sort()n=len(nums)res=[]foriinrange(n-3):ifi>0andnums[i]==nums[i-1]:continueforjinrange(i+1,n-2):ifj>i+1andnums[j]==nums[j-1]:continueleft,right=j+1,n-1whileleft<right:total=nums[i]+nums[j]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[j],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：-先排序数组，便于去重和双指针操作；-固定前两个数，用双指针遍历剩余部分，寻找和为`target`的四元组；-去重需考虑：前两个数不能重复，双指针移动时跳过相同数字。题目3答案：pythonfromtypingimportListdefmax_subarray_sum(nums:List[int],k:int)->int:n=len(nums)ifn<k:return0滑动窗口计算初始子数组和window_sum=sum(nums[:k])max_sum=window_sumforiinrange(k,n):window_sum+=nums[i]-nums[i-k]max_sum=max(max_sum,window_sum)returnmax_sum解析：-使用滑动窗口计算所有长度为`k`的子数组和；-初始窗口和为前`k`个数的和，随后每次移动窗口时减去窗口首部数字，加上窗口尾部数字；-保留最大和即可。二、算法设计题题目4答案：pythonfromtypingimportList,SetclassRecommendationSystem:def__init__(self,similarity:List[List[float]],history:Set[int]):self.similarity=similarityself.history=historydefget_recommendations(self,current:int,k:int)->List[int]:scores={}fornodeinrange(len(self.similarity)):ifnodeinself.history:scores[node]=self.similarity[current][node]2#历史权重加倍else:scores[node]=self.similarity[current][node]按分数排序，取前k个top_k=sorted(scores.items(),key=lambdax:x[1],reverse=True)[:k]return[nodefornode,_intop_k]解析：-初始化时记录历史浏览记录；-计算当前商品与所有商品的相似度，历史商品权重加倍；-按分数排序，返回前`k`个推荐商品。题目5答案：pythonfromcollectionsimportdequeclassCacheSystem:def__init__(self,capacity:int):self.capacity=capacityself.cache={}#key:node_id,value:(freq,order)self.order=0#记录插入顺序defget(self,node_id:int)->int:ifnode_idinself.cache:freq,order=self.cache[node_id]self.cache[node_id]=(freq+1,order)returnnode_idreturn-1defset(self,node_id:int,freq:int)->None:ifnode_idinself.cache:self.cache[node_id]=(freq,self.order)else:iflen(self.cache)==self.capacity:找到频率最低的节点min_freq=min(self.cache.values(),key=lambdax:x[0])[0]