2026年软件工程师面试编程能力测试题

2026年软件工程师面试编程能力测试题一、算法与数据结构（共5题，每题10分，总分50分）1.（10分）题目：给定一个非空整数数组`nums`，其中元素范围在`[1,n]`（`n`为数组长度），数组中存在重复元素。请找出数组中第一个重复的元素，并返回其索引。如果没有重复元素，返回`-1`。示例：-输入：`nums=[2,3,1,0,2,5]`，输出：`2`（第一个重复的元素是`2`，索引为`2`）-输入：`nums=[1,2,3,4,5]`，输出：`-1`（无重复元素）要求：-时间复杂度：O(n)-空间复杂度：O(n)答案与解析：答案：pythondeffind_first_duplicate(nums):seen=set()forindex,numinenumerate(nums):ifnuminseen:returnindexseen.add(num)return-1解析：使用哈希集合`seen`记录已遍历的元素。遍历数组时，若当前元素已存在于`seen`中，则返回其索引；否则将其加入`seen`。这样确保了时间复杂度为O(n)，空间复杂度也为O(n)。2.（10分）题目：设计一个LRU（LeastRecentlyUsed）缓存，支持以下操作：-`get(key)`:获取键`key`对应的值，若键不存在返回`-1`。获取后，将该键值对移动到缓存最前面（最常用）。-`put(key,value)`:插入或更新键值对。如果缓存已满，则移除最久未使用的键值对，再插入新的键值对。要求：-时间复杂度：O(1)-空间复杂度：O(capacity)答案与解析：答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：使用`OrderedDict`实现LRU缓存。`get`操作时，若键存在则将其移动到最前面；`put`操作时，若键已存在则更新值并移动到最前面，否则直接插入。当缓存超过`capacity`时，移除最久未使用的元素（`popitem(last=False)`）。这样确保了所有操作的时间复杂度为O(1)。3.（10分）题目：给定一个字符串`s`，其中包含字母、数字、符号等字符。请统计并返回字符串中每种字符的出现次数。结果可以按字符顺序返回。示例：-输入：`s="Hello,World!123"`，输出：`{'H':1,'e':1,'l':3,'o':2,',':1,'':2,'W':1,'r':1,'d':1,'!':1,'1':1,'2':1,'3':1}`要求：-时间复杂度：O(n)-空间复杂度：O(1)（假设字符集固定）答案与解析：答案：pythondefcount_characters(s:str)->dict:count={}forcharins:ifcharincount:count[char]+=1else:count[char]=1returncount解析：遍历字符串，使用字典`count`记录每个字符的出现次数。由于字符集固定（如ASCII字符集），空间复杂度可视为O(1)。时间复杂度为O(n)，其中n为字符串长度。4.（10分）题目：给定一个二叉树，判断其是否为完全二叉树。完全二叉树的定义：除最后一层外，每一层节点都满，且最后一层节点从左到右连续排列。示例：-输入：`[1,2,3,4,5,6]`（二叉树），输出：`True`-输入：`[1,2,3,4,None,6]`，输出：`False`（右子节点缺失）要求：-时间复杂度：O(n)-空间复杂度：O(n)（使用队列）答案与解析：答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_complete_binary_tree(root:TreeNode)->bool:ifnotroot:returnTruequeue=deque([root])flag=False#标记是否遇到过Nonewhilequeue:node=queue.popleft()ifnode:ifflag:returnFalse#如果之前遇到过None，当前节点不能为非空queue.append(node.left)queue.append(node.right)else:flag=True#遇到None，后续节点必须全为NonereturnTrue解析：使用队列层序遍历二叉树。遍历过程中，若遇到`None`，则设置`flag`为`True`，后续节点必须全为`None`。若在`flag`为`True`后遇到非空节点，则返回`False`。这样确保了完全二叉树的特性。5.（10分）题目：给定一个正整数`n`，生成所有可能的`n`皇后问题的解。皇后问题是指在8×8棋盘上放置n个皇后，使得任何两个皇后不在同一行、同一列或同一对角线上。示例：-输入：`n=4`，输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]要求：-时间复杂度：O(n!)-空间复杂度：O(n)答案与解析：答案：pythondefsolve_n_queens(n:int)->List[List[str]]:defbacktrack(row,diagonals,anti_diagonals,cols,state):ifrow==n:board=["".join(row)forrowinstate]result.append(board)returnforcolinrange(n):diag=row-colanti_diag=row+colifcolincolsordiagindiagonalsoranti_diaginanti_diagonals:continuecols.add(col)diagonals.add(diag)anti_diagonals.add(anti_diag)state[row][col]='Q'backtrack(row+1,diagonals,anti_diagonals,cols,state)cols.remove(col)diagonals.remove(diag)anti_diagonals.remove(anti_diag)state[row][col]='.'result=[]state=[["."for_inrange(n)]for_inrange(n)]backtrack(0,set(),set(),set(),state)returnresult解析：使用回溯法解决N皇后问题。定义三个集合分别记录列、主对角线、副对角线的占用情况。递归遍历每一行，尝试在该行的每一列放置皇后，若不冲突则继续递归下一行。若冲突则跳过当前列。最终将所有合法解加入`result`。二、数据库与SQL（共3题，每题10分，总分30分）1.（10分）题目：假设有一个名为`employees`的表，结构如下：sqlCREATETABLEemployees(idINTPRIMARYKEY,nameVARCHAR(50),departmentVARCHAR(50),salaryDECIMAL(10,2));请编写SQL查询，返回每个部门的平均工资（`salary`），且只显示平均工资高于公司平均工资的部门。要求：-使用子查询或窗口函数均可。答案与解析：答案：sqlSELECTdepartment,AVG(salary)ASavg_salaryFROMemployeesGROUPBYdepartmentHAVINGAVG(salary)>(SELECTAVG(salary)FROMemployees);解析：外层查询计算每个部门的平均工资，内层查询计算公司总平均工资。`HAVING`子句过滤出平均工资高于公司平均工资的部门。2.（10分）题目：假设有一个名为`orders`的表，结构如下：sqlCREATETABLEorders(idINTPRIMARYKEY,customer_idINT,order_dateDATE,total_amountDECIMAL(10,2));请编写SQL查询，返回每个客户的订单数量，且只显示订单数量超过10的客户的客户ID和订单数量。要求：-使用分组和过滤。答案与解析：答案：sqlSELECTcustomer_id,COUNT()ASorder_countFROMordersGROUPBYcustomer_idHAVINGCOUNT()>10;解析：`GROUPBY`子句按`customer_id`分组，`COUNT()`统计每个客户的订单数量，`HAVING`子句过滤出订单数量超过10的客户。3.（10分）题目：假设有两个表：-`orders`表（订单表）：`id`（订单ID），`customer_id`（客户ID），`order_date`（订单日期）-`order_items`表（订单项表）：`order_id`（订单ID），`product_id`（产品ID），`quantity`（数量）请编写SQL查询，返回每个客户的总订单金额（`order_items`表中的`quantity`乘以单价，假设单价存储在`order_items`表中），并按总金额降序排列。要求：-使用连接和聚合函数。答案与解析：答案：sqlSELECTo.customer_id,SUM(oi.quantityoi.unit_price)AStotal_amountFROMordersoJOINorder_itemsoiONo.id=oi.order_idGROUPBYo.customer_idORDERBYtotal_amountDESC;解析：使用`JOIN`将`orders`和`order_items`表连接，通过`GROUPBY`按`customer_id`分组，计算每个客户的总订单金额（`SUM(oi.quantityoi.unit_price)`），最后按总金额降序排列。三、系统设计（共2题，每题10分，总分20分）1.（10分）题目：设计一个简单的短链接服务。用户输入长链接，服务返回一个短链接，点击短链接后自动跳转到原始长链接。要求：-短链接应易于记忆且唯一。-支持高并发访问。-提供基本的统计功能（如点击次数）。答案与解析：答案：1.数据存储：-使用数据库表存储：`id`（自增主键），`long_url`（长链接），`short_code`（短链接码），`click_count`（点击次数）。-短链接码生成：使用随机或哈希算法生成（如`a-z`和`0-9`的6位字符）。2.服务流程：-生成短链接码，检查是否唯一，若重复则重新生成。-存储长链接、短链接码和初始点击次数。-返回短链接（如`/{short_code}`）。3.高并发处理：-使用缓存（如Redis）缓存热门短链接，减少数据库查询。-数据库读写分离，主库负责写入，从库负责查询。4.统计功能：-每次点击短链接时，更新`click_count`。解析：核心是短链接码的生成和存储。使用随机码或哈希算法确保唯一性，高并发下通过缓存和数据库优化提升性能。统计功能通过数据库表记录点击次数实现。2.（10分）题目：设计一个简单的消息队列服务（如Kafka或RabbitMQ的简化版）。用户可以发布消息，消费者可以订阅并消费消息。要求：-支持至少一个生产者和多个消费者。-消息必须按发送顺序消费。-支持至少一次交付（即消息可能重复，但至少交付一次）。答案与解析：答案：1.数据存储：-使用消息队列存储消息，如RabbitMQ或Kafka。-消息表：`id`（消息ID），`topic`（主题），`message`（消息内容），`timestamp`（时间戳）。2.生产者（Producer）：-用户发布消息到指定主题。-消息写入数据库或消息队列，并返回确认。3.消费者（Consumer）：-消费者订阅主题，按顺序拉取消息。-消息消费后，记录状态（如`is_consumed`）。-若消费失败，重新入队或记录重试次数。4.至少一次交付：-生产者确认消息写入成功。-消费者消费失败时，消息重新入队。解析：核心是消息的存储和顺序保证。使用数据库或消息队列实现消息存储，消费者按顺序拉取消息。至少一次交付通过生产者确认和消费者重试实现。四、网络编程与分布式系统（共2题，每题10分，总分20分）1.（10分）题目：设计一个简单的分布式缓存系统。节点间通过RPC（远程过程调用）通信，支持以下操作：-`get(key)`:获取键值对-`set(key,value)`:设置键值对要求：-支持节点故障自动恢复。-缓存数据在节点间同步。答案与解析：答案：1.架构设计：-使用一致性哈希算法分配节点，确保键值对均匀分布。-每个节点维护本地缓存，通过RPC同步数据。2.RPC通信：-生产者节点通过RPC调用其他节点的`get`或`set`方法。-使用gRPC或RESTAPI实现RPC。3.故障恢复：-使用心跳检测节点状态，若节点超时则重新分配其键值对到其他节点。-使用多副本机制，确保数据不丢失。解析：核心是节点分配和RPC通信。一致性哈希保证键值对均匀分布，RPC实现节点间同步，心跳检测和副本机制保证高可用性。2.（10分）题目：设计一个简单的分布式计数器服务。多个客户端可以并发地增加计数器，服务需要保证计数器值的准确性。要求：-支持高并发访问。-计数器值准确，无重复或丢失。答案与解析：答案：1.数据存储：-使用Redis或分布式数据库存储计数器值。-使用Redis的`INCR`命令实现原子增加。2.高并发处理：-客户端通过RPC调用服务器的`increment`方法。-服务器使用锁或原子操作保证计数器准确性。3.分布式锁：-使用分布式锁（如Redis锁）确保同一时间只有一个客户端修改计数器。解析：核心是原子操作和锁机制。Redis的`INCR`命令保证原子性，分布式锁防止并发冲突。高并发下通过Redis优化性能。五、编程语言与编码实践（共2题，每题10分，总分20分）1.（10分）题目：给定一个字符串`s`，请编写代码将其反转，但不能使用内置的