2026年程序员面试编程题及答案集

2026年程序员面试编程题及答案集一、算法设计题（共3题，每题20分）1.题目（20分）：“滑动窗口最大值”问题给定一个数组`nums`和一个整数`k`，设计一个算法，找到数组中每个长度为`k`的子数组的最大值，并按顺序输出结果。示例：输入：`nums=[1,3,-1,-3,5,3,6,7]`,`k=3`输出：`[3,3,5,5,6,7]`要求：-不能使用排序，时间复杂度要求为`O(n)`。-写出代码并解释核心思路。2.题目（20分）：“字符串解码”问题给定一个字符串`s`，其中包含数字和字母，数字表示后续字母的重复次数，字母需要解码为字符串。例如：输入：`s="3[a]2[bc]"`输出：`"aaabcbc"`要求：-不能使用递归，时间复杂度要求为`O(n)`。-写出代码并解释核心思路。3.题目（20分）：“合并K个有序链表”问题给定`k`个链表，每个链表有序，要求合并成一个有序链表。示例：输入：`lists=[[1,4,5],[1,3,4],[2,6]]`输出：`[1,1,2,3,4,4,5,6]`要求：-不能使用内置排序，时间复杂度要求为`O(nlogk)`。-写出代码并解释核心思路。二、数据结构题（共3题，每题20分）1.题目（20分）：“设计LRU缓存”问题LRU（LeastRecentlyUsed）缓存，通过哈希表和双向链表实现，支持`get`和`put`操作。要求：-`get(key)`：返回键对应的值，如果不存在返回-1。-`put(key,value)`：如果键存在，更新值；如果不存在，添加键值对，如果缓存已满，删除最久未使用的键。-时间复杂度要求为`O(1)`。-写出代码并解释核心思路。2.题目（20分）：“二叉树遍历”问题给定一个二叉树，实现前序、中序、后序遍历的递归和非递归版本。示例：1/\23/\45-前序遍历：`[1,2,4,5,3]`-中序遍历：`[4,2,5,1,3]`-后序遍历：`[4,5,2,3,1]`要求：-写出代码并解释核心思路。3.题目（20分）：“格雷编码”问题格雷编码是一种二进制数的排列方式，相邻的两个二进制数只有一个比特不同。给定`n`，生成所有格雷编码。示例：输入：`n=2`输出：`[00,01,11,10]`（按顺序排列）要求：-写出代码并解释核心思路。三、系统设计题（共2题，每题30分）1.题目（30分）：“设计短链接服务”问题实现一个短链接服务，将长链接转换为短链接，并支持通过短链接解析回长链接。要求：-短链接长度不超过6位，支持自定义前缀（如`/`）。-高并发场景下，解析速度要快。-写出核心逻辑和数据库设计。2.题目（30分）：“设计微博系统”问题设计一个微博系统，支持用户发布、评论、关注、点赞等功能。要求：-数据库表设计，并说明选型理由（MySQL或NoSQL）。-说明核心模块的架构设计（如消息队列、缓存）。-提出至少3个高并发解决方案。四、编码实现题（共4题，每题15分）1.题目（15分）：“字符串去重”问题给定一个字符串，删除所有重复的字符，保留首次出现的顺序。示例：输入：`s="abbac"`输出：`"abc"`要求：-时间复杂度要求为`O(n)`，空间复杂度要求为`O(1)`（假设字符集固定）。-写出代码并解释核心思路。2.题目（15分）：“数字翻转”问题给定一个整数，反转其数字，如果反转后超过32位整数范围，返回0。示例：输入：`x=123`输出：`321`要求：-不能使用库函数，时间复杂度要求为`O(logx)`。-写出代码并解释核心思路。3.题目（15分）：“二叉搜索树验证”问题给定一个二叉树，判断其是否为有效的二叉搜索树。示例：2/\13输出：`true`要求：-不能使用递归，可以使用栈实现。-写出代码并解释核心思路。4.题目（15分）：“字符串匹配”问题实现KMP算法，找到字符串`text`中是否存在子串`pattern`，如果存在，返回起始索引。示例：输入：`text="abababab",pattern="abab"`输出：`0`要求：-写出代码并解释核心思路。答案与解析一、算法设计题1.滑动窗口最大值代码：pythondefmaxSlidingWindow(nums,k):fromcollectionsimportdequeresult=[]dq=deque()#存储索引，单调递减foriinrange(len(nums)):移除不在窗口内的元素ifdqanddq[0]<i-k+1:dq.popleft()移除小于当前元素的元素whiledqandnums[i]>nums[dq[-1]]:dq.pop()dq.append(i)窗口形成后，记录最大值ifi>=k-1:result.append(nums[dq[0]])returnresult解析：使用双端队列存储窗口的最大值的索引，保证队头始终是当前窗口的最大值。每次滑动窗口时，先移除不在窗口内的索引，然后从队尾移除所有小于当前元素的索引，最后将当前索引加入队列。时间复杂度为`O(n)`。2.字符串解码代码：pythondefdecodeString(s):stack=[]num=0current_str=""forcharins:ifchar.isdigit():num=num10+int(char)elifchar=='[':stack.append((current_str,num))current_str=""num=0elifchar==']':prev_str,prev_num=stack.pop()current_str=prev_str+current_strprev_numelse:current_str+=charreturncurrent_str解析：使用栈处理括号嵌套，遇到数字时累积，遇到`[`时保存当前字符串和数字，遇到`]`时将当前字符串重复并拼接回前一个字符串。时间复杂度为`O(n)`。3.合并K个有序链表代码：pythondefmergeKLists(lists):fromheapqimportheappop,heappushheap=[]fori,nodeinenumerate(lists):ifnode:heappush(heap,(node.val,i,node))dummy=ListNode(0)current=dummywhileheap:val,idx,node=heappop(heap)current.next=nodecurrent=current.nextifnode.next:heappush(heap,(node.next.val,idx,node.next))returndummy.next解析：使用最小堆维护当前所有链表头部，每次弹出最小节点并加入结果，然后将该节点的下一个节点加入堆。时间复杂度为`O(nlogk)`。二、数据结构题1.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.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.popleft()delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用哈希表存储键值对，双向链表维护访问顺序。`get`操作将键移到队尾，`put`操作先移除最久未使用的键（队头），然后添加新键值对。时间复杂度为`O(1)`。2.二叉树遍历前序遍历（非递归）：pythondefpreorderTraversal(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult解析：使用栈模拟递归，先访问节点，然后右左入栈。时间复杂度为`O(n)`。3.格雷编码代码：pythondefgrayCode(n):return[i^(i>>1)foriinrange(1<<n)]解析：格雷编码的生成公式为`i^(i>>1)`，其中`i`从`0`到`2^n-1`。时间复杂度为`O(n)`。三、系统设计题1.短链接服务核心逻辑：-使用哈希函数（如MD5）将长链接映射为短码，如`a-zA-Z0-9`。-存储短码与长链接的映射关系，使用Redis缓存热点数据。-短码冲突时，通过自增或随机重试解决。数据库设计：sqlCREATETABLEshort_links(short_codeVARCHAR(6)PRIMARYKEY,long_urlVARCHAR(1024),created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);2.微博系统数据库设计：sqlCREATETABLEusers(user_idINTPRIMARYKEY,usernameVARCHAR(50),passwordVARCHAR(255));CREATETABLEposts(post_idINTPRIMARYKEY,user_idINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id));CREATETABLEcomments(comment_idINTPRIMARYKEY,post_idINT,user_idINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(post_id)REFERENCESposts(post_id),FOREIGNKEY(user_id)REFERENCESusers(user_id));架构设计：-消息队列（Kafka）处理用户行为日志，用于推荐系统。-缓存（Redis）存储热点用户和文章。-负载均衡（Nginx）分摊请求压力。高并发方案：1.分区（Sharding）用户表和帖子表。2.异步写入数据库。3.限流（RateLimiting）防止恶意攻击。四、编码实现题1.字符串去重代码：pythondefremoveDuplicates(s:str)->str:stack=[]forcharins:ifstackandstack[-1]==char:stack.pop()else:stack.append(char)return''.join(stack)解析：使用栈处理字符串，遇到重复字符时弹出，否则入栈。时间复杂度为`O(n)`。2.数字翻转代码：pythondefreverse(x:int)->int:result=0INT_MAX,INT_MIN=231-1,-231whilex:digit=x%10x=x//10ifresult>INT_MAX//10or(result==INT_MAX//10anddigit>7):return0ifresult<INT_MIN//10or(result==INT_MIN//10anddigit<-8):return0result=result10+digitreturnresult解析：逐位翻转数字，同时检查溢出。时间复杂度为`O(logx)`。3.二叉搜索树验证代码：pythondefisValidBST(root):stack,prev=[],float('-inf')whilestackorroot:whileroot:stack.append(root)root=root.leftroot=stack.pop()ifroot.val<=prev:returnFalseprev=root.valroot