2026年程序设计面试题目与答案详解

2026年程序设计面试题目与答案详解一、编程实现题（共5题，每题20分）题目1（20分）：实现一个LRU（LeastRecentlyUsed）缓存机制要求：-使用Python或Java实现LRU缓存，支持get和put操作。-get(key)：返回key对应的value，并更新key为最近使用。-put(key,value)：如果key已存在，更新其value并更新key为最近使用；如果key不存在，添加key-value对，如果缓存已满，则删除最久未使用的key。-不允许使用内置的LRU缓存实现，需手动实现。答案：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_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)解析：-使用哈希表`cache`存储key-value对，实现O(1)的get和put操作。-使用列表`order`记录访问顺序，每次get或put时更新该列表。-删除最久未使用的key时，从`order`列表头部删除。题目2（20分）：实现一个二叉树的最大深度计算要求：-给定一个二叉树的根节点，计算其最大深度（即最长的从根节点到叶子节点的路径上的节点数）。-使用递归或迭代方法实现。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root:TreeNode)->int:ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))解析：-递归方法：如果节点为空，返回0；否则返回1加上左右子树的最大深度。-迭代方法可以使用栈或队列实现BFS或DFS，这里以递归为例。题目3（20分）：实现一个字符串的URL解码要求：-输入一个URL编码的字符串，输出解码后的字符串。-例如：输入`%20%3F%26%23`，输出`?&#`。答案：pythondefurlDecode(s:str)->str:res=[]i=0whilei<len(s):ifs[i]=='%':hex_str=s[i+1:i+3]res.append(chr(int(hex_str,16)))i+=3else:res.append(s[i])i+=1return''.join(res)解析：-遍历字符串，遇到`%`时，读取接下来的两个字符作为十六进制数，转换为字符并添加到结果中。-其他字符直接添加到结果中。题目4（20分）：实现一个数组的合并排序要求：-给定两个已排序的数组`nums1`和`nums2`，合并它们为一个新的已排序数组。-假设`nums1`有足够的空间容纳两个数组的合并结果。答案：pythondefmerge(nums1:List[int],m:int,nums2:List[int],n:int)->None:p1,p2,p=m-1,n-1,m+n-1whilep1>=0andp2>=0:ifnums1[p1]>nums2[p2]:nums1[p]=nums1[p1]p1-=1else:nums1[p]=nums2[p2]p2-=1p-=1nums1[:p2+1]=nums2[:p2+1]解析：-从后向前合并两个数组，使用三个指针`p1`、`p2`和`p`分别指向`nums1`、`nums2`和`nums1`的合并后末尾。-比较两个指针所指元素，将较大的元素放到`nums1`的合并后位置，并移动对应指针。-如果`nums2`还有剩余元素，直接复制到`nums1`的前面。题目5（20分）：实现一个数字的罗马数字转换要求：-输入一个整数，输出其对应的罗马数字。-例如：输入`3`，输出`III`；输入`4`，输出`IV`。答案：pythondefintToRoman(num:int)->str:val=[1000,900,500,400,100,90,50,40,10,9,5,4,1]syms=["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]res=[]foriinrange(len(val)):whilenum>=val[i]:res.append(syms[i])num-=val[i]return''.join(res)解析：-使用两个列表`val`和`syms`分别存储罗马数字的值和符号。-从大到小遍历`val`，将`num`减去当前值并添加对应符号到结果中，直到`num`为0。-最终结果为合并后的符号字符串。二、算法设计题（共3题，每题25分）题目1（25分）：实现一个滑动窗口的最大值要求：-给定一个数组和一个窗口大小`k`，返回每个窗口的最大值。-例如：输入`nums=[1,3,-1,-3,5,3,6,7]`，`k=3`，输出`[3,3,5,5,6,7]`。答案：pythonfromcollectionsimportdequedefmaxSlidingWindow(nums:List[int],k:int)->List[int]:res=[]dq=deque()foriinrange(len(nums)):whiledqandnums[i]>=nums[dq[-1]]:dq.pop()dq.append(i)ifi>=k-1:res.append(nums[dq[0]])ifdq[0]==i-k+1:dq.popleft()returnres解析：-使用双端队列`dq`存储窗口的最大值的索引，队列头部为当前窗口的最大值。-遍历数组，维护队列：-如果当前元素大于等于队列末尾元素，则弹出末尾元素。-将当前元素索引加入队列。-如果当前索引已经超出窗口范围，弹出队列头部元素。-每次窗口移动时，队列头部元素即为当前窗口的最大值。题目2（25分）：实现一个字符串的回文子串计数要求：-给定一个字符串，返回其所有回文子串的数量。-例如：输入`"abc"`，输出`3`（"a","b","c"）。答案：pythondefcountSubstrings(s:str)->int:n=len(s)count=0foriinrange(n):奇数长度回文l,r=i,iwhilel>=0andr<nands[l]==s[r]:count+=1l-=1r+=1偶数长度回文l,r=i,i+1whilel>=0andr<nands[l]==s[r]:count+=1l-=1r+=1returncount解析：-遍历每个字符，以该字符为中心扩展回文子串：-扩展奇数长度回文（中心为单个字符）。-扩展偶数长度回文（中心为两个字符）。-每次扩展时，如果左右字符相同，则计数增加，并继续扩展。-最终计数即为所有回文子串的数量。题目3（25分）：实现一个图的连通分量计数要求：-给定一个无向图，使用并查集或DFS/BFS方法计算其连通分量的数量。-例如：输入图表示为邻接列表`[[1,2],[0,2],[0,1,3],[2]]`，输出`2`。答案：pythondefcountComponents(n:int,edges:List[List[int]])->int:parent=[iforiinrange(n)]deffind(x):ifparent[x]!=x:parent[x]=find(parent[x])returnparent[x]defunion(x,y):fx,fy=find(x),find(y)iffx!=fy:parent[fx]=fyforx,yinedges:union(x,y)returnlen(set(find(x)forxinrange(n)))解析：-使用并查集方法：-初始化每个节点的父节点为自己。-遍历每条边，将两个节点的根节点合并。-最后统计不同根节点的数量即为连通分量的数量。三、系统设计题（共2题，每题25分）题目1（25分）：设计一个简单的URL短链接系统要求：-实现一个URL短链接系统，支持将长URL转换为短URL，并能将短URL解析回长URL。-需考虑高并发场景下的性能和可用性。答案：pythonimporthashlibimportrandomimportstringclassURLShortener:def__init__(self):self.url_map={}self.base_url="http://short.url/"def_generate_short_id(self):chars=string.ascii_letters+string.digitsshort_id=''.join(random.choice(chars)for_inrange(6))returnshort_iddefinsert(self,long_url:str)->str:whileTrue:short_id=self._generate_short_id()ifshort_idnotinself.url_map:self.url_map[short_id]=long_urlbreakreturnself.base_url+short_iddefget(self,short_url:str)->str:short_id=short_url.split('/')[-1]returnself.url_map.get(short_id,"InvalidshortURL")解析：-使用哈希表`url_map`存储短URL和长URL的映射。-生成短ID时，随机选择6位字符，确保唯一性。-插入时，如果短ID已存在，则重新生成；获取时，直接返回对应的长URL。-考虑高并发时，可以使用分布式缓存或数据库优化性能。题目2（25分）：设计一个简单的消息队列系统要求：-实现一个简单的消息队列系统，支持生产者发送消息和生产者消费消息。-需考虑消息的持久化、顺序性和可靠性。答案：pythonimportthreadingimportqueueclassMessageQueue:def__init__(self):self.queue=queue.Queue()self.lock=threading.Lock()self.msg_id=0defproduce(self,message:str):withself.lock:self.msg_id+=1self.queue.put((self.msg_id,message))defconsume(self)->str:withself.lock:ifnots