计算机程序员面试题集及答案详解

2026年计算机程序员面试题集及答案详解一、编程语言基础（5题，每题10分）1.题目（10分）：编写一个函数，实现将一个字符串中的所有空格替换为`%20`。假设字符串的长度足够容纳替换后的结果。答案与解析：pythondefreplace_spaces(s:str)->str:returns.replace("","%20")解析：使用Python内置的`replace`方法直接替换空格为`%20`是最简洁高效的方式。时间复杂度为O(n)，其中n为字符串长度。对于其他语言，如Java，可以使用双指针法优化空间复杂度。2.题目（10分）：给定一个数组，返回数组中的最大值和最小值，不使用内置函数。答案与解析：pythondeffind_max_min(arr:list)->tuple:ifnotarr:returnNonemax_val=min_val=arr[0]fornuminarr[1:]:ifnum>max_val:max_val=numelifnum<min_val:min_val=numreturnmax_val,min_val解析：遍历数组，初始化最大值和最小值为第一个元素，逐个比较更新。时间复杂度为O(n)，空间复杂度为O(1)。3.题目（10分）：实现一个单链表节点类，包含`val`和`next`属性，并实现反转链表的功能。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_linked_list(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：使用迭代法反转链表，时间复杂度为O(n)，空间复杂度为O(1)。4.题目（10分）：实现快速排序算法，不使用递归。答案与解析：pythondefquick_sort_iterative(arr:list)->list:stack=[(0,len(arr)-1)]whilestack:start,end=stack.pop()ifstart>=end:continuepivot=arr[end]i=start-1forjinrange(start,end):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[end]=arr[end],arr[i+1]stack.append((start,i))stack.append((i+2,end))returnarr解析：使用栈模拟递归，避免递归调用栈的开销。时间复杂度为O(nlogn)，空间复杂度为O(logn)。5.题目（10分）：实现一个二叉树节点类，包含`val`、`left`和`right`属性，并实现层序遍历。答案与解析：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevel_order_traversal(root:TreeNode)->list: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解析：使用队列实现BFS（广度优先搜索），按层遍历二叉树。时间复杂度为O(n)，空间复杂度为O(n)。二、算法与数据结构（5题，每题15分）1.题目（15分）：给定一个字符串，判断是否是有效的括号组合（如`"()[]{}"`）。答案与解析：pythondefis_valid_parentheses(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用栈，遇到右括号时与栈顶元素匹配，不匹配则无效。时间复杂度为O(n)，空间复杂度为O(n)。2.题目（15分）：实现二分查找算法，返回目标值的索引，如果不存在则返回-1。答案与解析：pythondefbinary_search(arr:list,target:int)->int:left,right=0,len(arr)-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid-1return-1解析：在有序数组中查找目标值，时间复杂度为O(logn)，空间复杂度为O(1)。3.题目（15分）：实现LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。答案与解析：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)解析：使用哈希表记录缓存，双端队列记录访问顺序。`get`操作将元素移到队尾，`put`操作先删除最久未使用元素。时间复杂度为O(1)。4.题目（15分）：给定一个无重复元素的数组，返回所有可能的子集。答案与解析：pythondefsubsets(nums:list)->list:result=[]subset=[]defbacktrack(index):result.append(subset.copy())foriinrange(index,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：回溯法生成所有子集，时间复杂度为O(2^n)，空间复杂度为O(n)。5.题目（15分）：实现拓扑排序，给定一个有向无环图（DAG）。答案与解析：pythonfromcollectionsimportdequedeftopological_sort(num_nodes:int,edges:list)->list:in_degree=[0]num_nodesadj_list=[[]for_inrange(num_nodes)]foru,vinedges:adj_list[u].append(v)in_degree[v]+=1queue=deque([iforiinrange(num_nodes)ifin_degree[i]==0])result=[]whilequeue:node=queue.popleft()result.append(node)forneighborinadj_list[node]:in_degree[neighbor]-=1ifin_degree[neighbor]==0:queue.append(neighbor)returnresultiflen(result)==num_nodeselse[]解析：Kahn算法，统计入度，将入度为0的节点加入队列，逐个处理。时间复杂度为O(V+E)，空间复杂度为O(V)。三、系统设计（3题，每题20分）1.题目（20分）：设计一个简单的微博系统，支持发布、关注、获取关注者动态。答案与解析：pythonclassWeiboSystem:def__init__(self):self.users={}#{user_id:User}classUser:def__init__(self,user_id):self.user_id=user_idself.followees=set()self.feeds=[]defpost(self,content:str):self.feeds.append(content)deffollow(self,other):self.followees.add(other)defget_feed(self):all_posts=[]foruserinself.followees:all_posts.extend(user.feeds)returnall_posts[::-1]#最新的在前面defcreate_user(self,user_id:int)->User:ifuser_idinself.users:returnself.users[user_id]user=self.User(user_id)self.users[user_id]=userreturnuser解析：使用类表示用户，包含关注列表和动态列表。发布动态时追加到`feeds`，获取动态时按关注顺序合并。2.题目（20分）：设计一个高并发短URL生成系统，要求高可用、高并发。答案与解析：pythonimporthashlibimportrandomimportstringclassShortURLSystem:def__init__(self):self.base_url="http://short.url/"self字符集=string.ascii_letters+string.digitsdefgenerate_short_id(self,original_url:str)->str:hash_obj=hashlib.md5(original_url.encode())hash_hex=hash_obj.hexdigest()short_id=''.join(random.choices(self字符集,k=6))returnshort_iddefget_full_url(self,short_id:str)->str:returnself.base_url+short_id解析：使用MD5哈希原始URL并截取部分字符生成短ID，确保唯一性。实际应用中可结合分布式ID生成器（如Snowflake）。3.题目（20分）：设计一个分布式缓存系统，支持多节点读写。答案与解析：pythonclassDistributedCache:def__init__(self,nodes:list):self.nodes=nodes#分布式节点列表defget(self,key:str)->str:node_id=hash(key)%len(self.nodes)returnself.nodes[node_id].get(key)defput(self,key:str,value:str)->None:node_id=hash(key)%len(self.nodes)self.nodes[node_id].put(key,value)解析：使用哈希函数将键映射到节点，每个节点独立存储数据。可结合一致性哈希优化节点分配。四、数据库与SQL（3题，每题20分）1.题目（20分）：SQL查询：给定表`orders`（`order_id`，`customer_id`，`order_date`），查询2023年每月的订单数量。答案与解析：sqlSELECTDATE_FORMAT(order_date,'%Y-%m')ASmonth,COUNT(order_id)ASorder_countFROMordersWHEREYEAR(order_date)=2023GROUPBYmonthORDERBYmonth;解析：使用`DATE_FORMAT`提取月份，`GROUPBY`按月分组统计。2.题目（20分）：SQL查询：表`employees`（`id`，`name`，`department`，`salary`），查询每个部门的平均工资，并按平均工资降序排列。答案与解析：sqlSELECTdepartment,AVG(salary)ASavg_salaryFROMemployeesGROUPBYdepartmentORDERBYavg_salaryDESC;解析：使用`AVG`聚合函数计算平均工资，`ORDERBY`降序排列。3.题目（20分）：SQL查询：表`students`（`id`，`name`，`score`），查询分数最高的前3名学生。答案与解析：sqlSELECTid,name,scoreFROMstudentsORDERBYscoreDESCLIMI