2026年计算机编程面试题及编程解决方案

2026年计算机编程面试题及编程解决方案一、编程实现题（共5题，每题20分，总分100分）题目1（15分）：实现一个函数，输入一个非空字符串，返回该字符串中所有唯一字符的列表。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：输入："leetcode"输出：["l","d"]题目2（25分）：设计一个LRU（LeastRecentlyUsed）缓存系统，支持以下操作：1.`get(key)`：获取键key对应的值，如果键不存在返回-1。2.`put(key,value)`：向缓存中插入键值对，如果键已存在则更新其值。当缓存容量达到限制时，删除最久未使用的键。要求：-使用双向链表和哈希表实现，确保`get`和`put`操作的时间复杂度为O(1)。-提供Python或Java实现。题目3（20分）：给定一个包含n个整数的数组，设计一个算法，找到数组中第三大的数。如果数组中少于三个不同的数，返回最大的数。示例：输入：[3,2,1,5,6,4]输出：2输入：[1,2]输出：2题目4（20分）：实现一个简单的文本编辑器，支持以下操作：1.`addText(text)`：在光标位置插入文本。2.`deleteText(k)`：删除光标左边的k个字符（如果k大于光标左边的字符数，则全部删除）。3.`cursorLeft(k)`：将光标向左移动k个位置（如果移动到开头，则停留在开头）。4.`cursorRight(k)`：将光标向右移动k个位置（如果移动到末尾，则停留在末尾）。要求：-使用栈或链表实现，确保所有操作的时间复杂度为O(1)。-提供Python实现。题目5（20分）：设计一个算法，判断一个无向图是否是二分图。二分图是指可以将图的节点分成两个集合，使得每条边的两个节点分别属于不同的集合。要求：-使用深度优先搜索（DFS）或广度优先搜索（BFS）实现。-提供Python或Java实现。二、算法设计题（共3题，每题30分，总分90分）题目6（30分）：设计一个算法，给定一个包含n个整数的数组和一个目标值target，找出数组中和为目标值的三元组数量。要求：-不考虑顺序，重复的三元组只计算一次。-时间复杂度尽可能低。示例：输入：nums=[1,5,-10,0,7,10],target=5输出：3（三元组为[-10,5,10],[0,5,0],[1,5,-10]）题目7（30分）：设计一个算法，给定一个字符串s和一个整数k，返回s中长度为k的所有子字符串的最小字典序。示例：输入：s="dbdbdd",k=3输出："bdb"题目8（30分）：设计一个算法，给定一个包含n个整数的数组，返回一个新数组，其中新数组的第i个元素是原数组中比第i个元素大的元素的数量。示例：输入：[5,2,6,1]输出：[2,1,1,0]（第一个元素5右边有2个比它大，第二个元素2右边有1个比它大，以此类推）三、系统设计题（共2题，每题35分，总分70分）题目9（35分）：设计一个简单的分布式缓存系统，支持以下功能：1.`get(key)`：从缓存中获取键key对应的值。2.`put(key,value)`：向缓存中插入或更新键值对。3.缓存数据在多个节点间同步（使用一致性哈希或类似机制）。4.支持基本的故障恢复（一个节点失效时，其他节点可以接管其部分数据）。要求：-描述系统架构、数据存储方式、一致性协议。-提供伪代码或高层次设计思路。题目10（35分）：设计一个简单的实时推荐系统，支持以下功能：1.用户每次浏览商品时，记录浏览行为。2.根据用户的浏览历史，实时推荐用户可能感兴趣的商品。3.推荐算法需要考虑：-用户最近浏览的商品优先。-商品之间的关联性（如购买同一商品的用户的浏览习惯）。-推荐结果的多样性（避免推荐过多同类商品）。要求：-描述系统架构、数据存储方式、推荐算法。-提供伪代码或高层次设计思路。答案与解析一、编程实现题题目1（15分）：解决方案：使用一个固定大小的哈希表记录字符出现的次数，然后遍历一次字符串，收集出现次数为1的字符。pythondefunique_chars(s:str)->list:counts=[0]256#假设ASCII字符集forcharins:counts[ord(char)]+=1return[chr(i)foriinrange(256)ifcounts[i]==1]解析：-时间复杂度：O(n)，n为字符串长度。-空间复杂度：O(1)，哈希表大小固定为256。题目2（25分）：解决方案：使用双向链表和哈希表实现。双向链表头节点为最近使用，尾节点为最久未使用。哈希表存储键到链表节点的映射。pythonclassListNode:def__init__(self,key=None,val=None):self.key=keyself.val=valself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode()self.tail=ListNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node:ListNode):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:ListNode):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:ListNode):self._remove_node(node)self._add_node(node)def_pop_tail(self)->ListNode: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.valdefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.val=valueself._move_to_head(node)解析：-`get`和`put`操作通过哈希表和链表的结合，确保时间复杂度为O(1)。-链表维护最近使用顺序，哈希表快速查找节点。题目3（20分）：解决方案：维护三个变量分别记录第一大、第二大、第三大的数，遍历数组时更新这三个变量。pythondefthird_largest(nums:list)->int:first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:third=secondsecond=firstfirst=numeliffirst>num>second:third=secondsecond=numelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst解析：-遍历一次数组，时间复杂度O(n)。-使用三个变量记录最大值，空间复杂度O(1)。题目4（20分）：解决方案：使用栈实现光标位置左侧的文本，另一个栈记录光标右侧的文本。通过操作两个栈实现插入、删除和光标移动。pythonclassTextEditor:def__init__(self):self.left=[]self.right=[]defaddText(self,text:str)->None:self.left.extend(list(text))defdeleteText(self,k:int)->None:delself.left[:min(k,len(self.left))]defcursorLeft(self,k:int)->None:for_inrange(min(k,len(self.left))):self.right.append(self.left.pop())defcursorRight(self,k:int)->None:for_inrange(min(k,len(self.right))):self.left.append(self.right.pop())defgetCurrentText(self)->str:return''.join(self.left)+''.join(reversed(self.right))解析：-栈实现插入和删除操作，时间复杂度O(1)。-光标移动通过栈操作实现，时间复杂度O(k)。题目5（20分）：解决方案：使用DFS或BFS遍历图，尝试将节点分成两个集合，检查每条边是否连接不同集合的节点。pythondefisBipartite(graph:list)->bool:color={}defdfs(node,c):color[node]=cforneighboringraph[node]:ifneighborincolor:ifcolor[neighbor]==color[node]:returnFalseelse:ifnotdfs(neighbor,1-c):returnFalsereturnTruefornodeinrange(len(graph)):ifnodenotincolor:ifnotdfs(node,0):returnFalsereturnTrue解析：-使用DFS遍历图，时间复杂度O(V+E)。-使用哈希表记录节点颜色，空间复杂度O(V)。二、算法设计题题目6（30分）：解决方案：先对数组排序，然后使用双指针法。pythondefthree_sum(nums:list,target:int)->int:nums.sort()n=len(nums)count=0foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:count+=1left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1eliftotal<target:left+=1else:right-=1returncount解析：-排序后时间复杂度O(nlogn)，双指针遍历为O(n^2)。-使用去重避免重复计数。题目7（30分）：解决方案：滑动窗口法，记录当前窗口的最小值。pythondefsmallest_window(s:str,k:int)->str:n=len(s)ifn<k:return""min_window=s[:k]foriinrange(n-k+1):window=s[i:i+k]ifwindow<min_window:min_window=windowreturnmin_window解析：-滑动窗口遍历字符串，时间复杂度O(n)。-每次比较窗口字符串，时间复杂度O(k)。题目8（30分）：解决方案：使用单调栈记录每个元素右边比它大的元素数量。pythondefcount_of_larger(nums:list)->list:n=len(nums)res=[0]nstack=[]foriinrange(n):whilestackandnums[stack[-1]]<nums[i]:res[stack.pop()]+=1stack.append(i)whilestack:res[stack.pop()]+=0returnres解析：-单调栈遍历数组，时间复杂度O(n)。-栈辅助计数，空间复杂度O(n)。三、系统设计题题目9（35分）：解决方案：-架构：-使用一致性哈希算法将数据均匀分布在多个节点上。-每个节点存储其负责的数据块。-使用Raft或Paxos协议保证数据一致性。-数据存储：-每个节点使用本地磁盘或SSD存储数据。-使用布隆过滤器快速判断数据是否在本地节点。-一致性协议：-`put`操作时，先向leader节点请求，leader节点通过Raft协议广播到所有节点。-`get`操作时，先查询本地节点，如果未命中则通过一致性哈希查找其他节点。plaintext伪代码：functionput(key,value):leader=find_leader(key)ifleader:leader.append(key,value)propagateRaft(leader,key,value)functionget(key):node=find_node(key)ifnode.contains(key):returnnode.get(key)else:return-1解析：-一致性哈希保证数据均匀分布，减少