程序设计面试题库及答案

2026年程序设计面试题库及答案一、编程实现题（每题15分，共3题）1.编写一个函数，实现快速排序算法（QuickSort）要求：-输入一个整数数组，返回排序后的数组。-不能使用现成的排序库函数（如Python的`sorted()`或Java的`Arrays.sort()`）。-请展示核心代码和测试用例。答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)测试用例test_arr=[3,6,8,10,1,2,1]print(quick_sort(test_arr))#输出:[1,1,2,3,6,8,10]解析：-快速排序采用分治法，核心思想是选择一个基准值（pivot），将数组分为三部分：小于基准值的、等于基准值的、大于基准值的。-递归地对左右两部分继续排序，最终合并。-时间复杂度：平均O(nlogn)，最坏O(n²)（当基准值选择不均匀时）。2.编写一个函数，实现二叉树的深度优先遍历（DFS）要求：-输入一个二叉树的根节点，返回前序遍历的结果列表。-不能使用现成的库函数（如Python的`collections.deque`）。-请展示核心代码和测试用例。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorder_dfs(root):ifnotroot:return[]result=[]stack=[root]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult测试用例root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(preorder_dfs(root))#输出:[1,2,4,5,3]解析：-前序遍历的顺序是：根节点->左子树->右子树。-使用栈实现DFS，先访问右子节点是因为栈是后进先出（LIFO），需要先处理右子树。-时间复杂度：O(n)，每个节点访问一次。3.编写一个函数，实现LRU（LeastRecentlyUsed）缓存机制要求：-使用Python实现，不能使用现成的`collections.OrderedDict`。-支持两个操作：`get(key)`和`put(key,value)`。-请展示核心代码和测试用例。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeynotinself.cache:return-1self.order.remove(key)self.order.append(key)returnself.cache[key]defput(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=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#返回1cache.put(3,3)#去除键2print(cache.get(2))#返回-1cache.put(4,4)#去除键1print(cache.get(1))#返回-1print(cache.get(3))#返回3print(cache.get(4))#返回4解析：-LRU缓存通过记录访问顺序，每次访问或插入时移动节点到尾部，最久未访问的节点在头部。-使用列表`self.order`记录顺序，字典`self.cache`存储键值对。-时间复杂度：`get`和`put`均为O(1)。二、算法设计题（每题20分，共2题）1.设计一个算法，判断一个无向图是否是二分图（BipartiteGraph）要求：-输入图的邻接表表示，返回布尔值及颜色分配（用0和1表示两种颜色）。-不能使用现成的库函数（如Python的`networkx`）。-请展示核心代码和测试用例。答案：pythondefis_bipartite(graph):color={}fornodeingraph:ifnodenotincolor:stack=[node]color[node]=0whilestack:current=stack.pop()forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=1-color[current]stack.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTrue,color测试用例graph1={0:[1,3],1:[0,2],2:[1,3],3:[0,2]}print(is_bipartite(graph1))#输出:(True,{0:0,1:1,2:1,3:0})graph2={0:[1,2],1:[0,3],2:[0],3:[1]}print(is_bipartite(graph2))#输出:(False,{0:0,1:1,2:0,3:1})解析：-二分图可以分成两个集合，其中任何两个相邻节点颜色不同。-使用DFS遍历图，用`color`字典记录颜色，初始节点设为0，相邻节点设为1。-如果发现相邻节点颜色相同，则不是二分图。-时间复杂度：O(n+m)，n为节点数，m为边数。2.设计一个算法，实现字符串的编辑距离（LevenshteinDistance）计算要求：-输入两个字符串`s1`和`s2`，返回最小编辑距离。-不能使用现成的库函数（如Python的`difflib.SequenceMatcher`）。-请展示核心代码和测试用例。答案：pythondeflevenshtein_distance(s1:str,s2:str)->int:m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]foriinrange(m+1):dp[i][0]=iforjinrange(n+1):dp[0][j]=jforiinrange(1,m+1):forjinrange(1,n+1):ifs1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1returndp[m][n]测试用例print(levenshtein_distance("kitten","sitting"))#输出:3print(levenshtein_distance("garden","garde"))#输出:1解析：-编辑距离是指将一个字符串转换为另一个字符串所需的最少单字符编辑（插入、删除、替换）。-使用动态规划，`dp[i][j]`表示`s1[:i]`到`s2[:j]`的编辑距离。-初始化边界条件：空字符串到任何字符串的编辑距离等于字符串长度。-时间复杂度：O(mn)，m和n分别为两个字符串的长度。三、系统设计题（每题25分，共1题）1.设计一个简单的短链接（TinyURL）生成系统要求：-输入一个长URL，返回一个短URL。-支持反向解析，输入短URL返回原始长URL。-请展示核心设计思路、数据结构及伪代码。答案：核心设计思路：1.使用随机生成或哈希算法将长URL映射为短URL。2.使用数据库或内存存储映射关系，确保唯一性和快速查询。3.短URL使用62进制（a-z,A-Z,0-9）表示，长度固定（如6位）。数据结构：-字典`url_map`：`{长URL:短URL}`-字典`reverse_map`：`{短URL:长URL}`伪代码：pythonimportbase64importhashlibclassTinyURL:def__init__(self):self.url_map={}self.reverse_map={}self.base_url="/"def_encode(self,num):chars="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"base=len(chars)encoded=""whilenum>0:encoded=chars[num%base]+encodednum//=basereturnencoded.zfill(6)#确保长度为6def_decode(self,short_url):hash_part=short_url[len(self.base_url):]returnint.from_bytes(base64.urlsafe_b64decode(hash_part),byteorder='big')definsert(self,long_url:str)->str:iflong_urlinself.url_map:returnself.url_map[long_url]hash_value=hashlib.sha256(long_url.encode()).hexdigest()num=int(hash_value,16)short_url=self.base_url+self._encode(num)self.url_map[long_url]=short_urlself.reverse_map[short_url]=long_urlreturnshort_urldefget(self,short_url:str)->str:returnself.reverse_map.get(short_url,"URLnotfound")测试用例tiny=