2026年软件开发面试编程试题

2026年软件开发面试编程试题一、编程实现题（共3题，每题15分，总分45分）题目1（15分）：实现一个简单的LRU缓存机制题目描述：请设计一个LRU（LeastRecentlyUsed）缓存机制。LRU缓存机制会根据使用频率对缓存项进行淘汰，当缓存容量满时，最久未被使用的数据将被移除。你需要实现LRU缓存的基本功能，包括：1.初始化缓存，指定其容量。2.`get(key)`：获取键对应的值，如果键存在，返回值并更新该键为最近使用；如果键不存在，返回-1。3.`put(key,value)`：插入或更新键值对。如果键已存在，更新其值并标记为最近使用；如果键不存在且缓存已满，移除最久未使用的键，然后插入新键值对。要求：-使用链表和哈希表结合的方式实现，时间复杂度为O(1)。-请提供代码实现，并简要说明设计思路。答案与解析：pythonclassListNode:def__init__(self,key=0,value=0,prev=None,next=None):self.key=keyself.value=valueself.prev=prevself.next=nextclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}#key:ListNodeself.head=ListNode()#dummyheadself.tail=ListNode()#dummytailself.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node:ListNode):"""Addnoderightafterhead."""node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:ListNode):"""Removeanexistingnodefromthelinkedlist."""prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:ListNode):"""Movecertainnodeinbetweentothehead."""self._remove_node(node)self._add_node(node)def_pop_tail(self)->ListNode:"""Popthecurrenttail."""res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnode:node.value=valueself._move_to_head(node)else:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]解析：1.数据结构选择：-使用双向链表维护最近使用顺序（头为最近使用，尾为最久未使用）。-使用哈希表（字典）实现O(1)的查找效率。2.核心操作：-`get(key)`：若存在，移动节点到头部并返回值；若不存在，返回-1。-`put(key,value)`：若存在，更新值并移动到头部；若不存在，新建节点并插入头部，若超出容量则移除尾部节点。3.优化细节：-使用虚拟头尾节点简化边界操作。-通过`prev`和`next`指针实现快速插入和删除。题目2（15分）：实现一个有效的括号匹配器题目描述：请设计一个有效的括号匹配器，用于检查字符串中的括号（包括`()`、`[]`、`{}`）是否正确匹配。字符串中可能包含其他字符，但仅考虑括号的有效性。你需要实现一个函数，输入一个字符串，返回布尔值表示是否有效。示例：-输入：`"()"`→输出：`True`-输入：`"()[]{}"`→输出：`True`-输入：`"(]"`→输出：`False`-输入：`"([)]"`→输出：`False`要求：-使用栈（Stack）实现，确保时间复杂度为O(n)。-请提供代码实现，并说明处理逻辑。答案与解析：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：1.核心思路：-使用栈存储未匹配的左括号，遇到右括号时检查栈顶是否为对应左括号。-如果匹配则弹出栈顶，否则无效。2.处理细节：-使用哈希表`mapping`快速查找对应括号。-初始化栈顶为`#`（非括号字符）避免空栈错误。-最终栈为空则表示完全匹配。题目3（15分）：实现一个字符串压缩算法题目描述：请实现一个字符串压缩算法，将输入字符串中的连续相同字符合并，并记录字符及其出现次数。例如：-输入：`"aabcccccaaa"`→输出：`"a2b1c5a3"`-输入：`"abcd"`→输出：`"a1b1c1d1"`要求：-压缩后的字符串长度应不大于原字符串长度时才输出压缩结果。-请提供代码实现，并说明算法效率。答案与解析：pythondefcompressString(s:str)->str:ifnots:return""compressed=[]count=1foriinrange(1,len(s)):ifs[i]==s[i-1]:count+=1else:compressed.append(s[i-1]+str(count))count=1compressed.append(s[-1]+str(count))return''.join(compressed)iflen(compressed)<len(s)elses解析：1.核心思路：-遍历字符串，统计连续相同字符的次数，记录为`"字符+次数"`。-压缩后长度小于原字符串时返回压缩结果，否则返回原字符串。2.效率分析：-时间复杂度：O(n)，只需遍历一次字符串。-空间复杂度：O(n)，用于存储压缩结果。二、算法设计题（共2题，每题20分，总分40分）题目4（20分）：实现一个二叉树的层序遍历题目描述：请实现二叉树的层序遍历（Breadth-FirstSearch,BFS），按从上到下、从左到右的顺序返回节点的值。示例：-输入：`[3,9,20,null,null,15,7]`（对应二叉树）-输出：`[[3],[9,20],[15,7]]`要求：-使用队列实现，确保时间复杂度为O(n)。-请提供代码实现，并说明设计思路。答案与解析：pythonfromcollectionsimportdequefromtypingimportList,OptionalclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevelOrder(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.核心思路：-使用队列实现BFS，逐层遍历节点。-每次处理当前层的所有节点，将其子节点加入队列。2.优化细节：-通过`level_size`控制当前层节点数量。-最终按层返回节点值列表。题目5（20分）：实现一个快速排序算法题目描述：请实现快速排序（QuickSort）算法，对输入的整数数组进行原地排序。快速排序的核心思想是分治法：1.选择一个基准值（pivot），通常为第一个或最后一个元素。2.将数组分为两部分，左部分所有元素小于等于基准值，右部分所有元素大于基准值。3.递归对左右两部分进行排序。示例：-输入：`[3,6,8,10,1,2,1]`-输出：`[1,1,2,3,6,8,10]`要求：-使用原地排序（不额外分配数组空间）。-请提供代码实现，并说明算法特点。答案与解析：pythondefquickSort(arr:List[int],low:int,high:int)->None:iflow<high:pivot_index=partition(arr,low,high)quickSort(arr,low,pivot_index-1)quickSort(arr,pivot_index+1,high)defpartition(arr:List[int],low:int,high:int)->int:pivot=arr[high]i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]returni+1调用示例quickSort(arr,0,len(arr)-1)解析：1.核心思路：-选择`high`作为基准值（pivot），通过`partition`函数调整位置。-`partition`函数将小于等于基准值的元素移到左侧，大于基准值的移到右侧。2.算法特点：-平均时间复杂度：O(nlogn)，最坏O(n²)。-原地排序，空间复杂度O(logn)。-非稳定排序。三、编码挑战题（共1题，25分）题目6（25分）：实现一个滑动窗口最大值题目描述：请设计一个滑动窗口最大值（SlidingWindowMaximum）的解决方案。给定一个整数数组和一个窗口大小`k`，返回一个包含每个窗口（窗口大小为`k`）内最大值的数组。示例：-输入：`nums=[1,3,-1,-3,5,3,6,7]`,`k=3`-输出：`[3,3,5,5,6,7]`要求：-使用单调队列（Deque）实现，确保时间复杂度为O(n)。-请提供代码实现，并说明设计思路。答案与解析：pythonfromcollectionsimportdequedefmaxSlidingWindow(nums:List[int],k:int)->List[int]:ifnotnumsork==0:return[]result=[]dq=deque()#storeindicesforiinrange(len(nums)):removeelementsnotincurrentwindowifdqanddq[0]<i-k+1:dq.popleft()removeelementssmallerthancurrentnumwhiledqandnums[dq[-1]]<nums[i]:dq.pop()dq.append(