2026年程序员面试题集及编程逻辑考察

2026年程序员面试题集及编程逻辑考察一、算法设计题（共3题，每题20分）1.（20分）题目：假设你正在开发一个社交网络平台，需要设计一个算法来检测用户之间的好友关系链。给定一个由用户ID和好友关系组成的邻接表，请实现一个函数，判断两个用户是否可以通过好友关系链直接或间接地互相关联。例如，用户A和用户C之间有共同好友B，则A和C可以通过好友关系链关联。输入：-好友关系列表：`edges=[["A","B"],["B","C"],["C","D"],["E","F"]]`-查询对：`["A","D"]`输出：-返回`True`（因为A可以通过B和C关联到D）或`False`。要求：-时间复杂度：O(N+E)，其中N是用户数量，E是好友关系数量。-空间复杂度：O(N)。答案与解析：答案：pythondefare_friends(node1,node2,edges):fromcollectionsimportdefaultdict,dequegraph=defaultdict(list)foru,vinedges:graph[u].append(v)graph[v].append(u)visited=set()queue=deque([node1])whilequeue:current=queue.popleft()ifcurrent==node2:returnTrueifcurrentnotinvisited:visited.add(current)queue.extend(graph[current])returnFalse示例调用edges=[["A","B"],["B","C"],["C","D"],["E","F"]]print(are_friends("A","D",edges))#输出：True解析：-使用广度优先搜索（BFS）遍历图，从起始节点开始逐层查找，若找到目标节点则返回`True`。-时间复杂度：O(N+E)，因为每个节点和边最多访问一次。-空间复杂度：O(N)，用于存储邻接表和队列。2.（20分）题目：假设你需要设计一个算法来优化数据库查询性能。给定一个包含重复数据的表格，其中每行代表一条记录，列包括`ID`（唯一标识）、`Timestamp`（时间戳）、`Value`（数值）。请实现一个函数，删除所有重复的记录，保留时间戳最晚的一条。输入：-表格数据：`[["1","2023-01-01","10"],["1","2023-01-02","15"],["2","2023-01-01","20"]]`输出：-删除重复后保留的数据：`[["1","2023-01-02","15"],["2","2023-01-01","20"]]`要求：-不能使用排序或临时表，需满足时间复杂度O(N)。答案与解析：答案：pythondefremove_duplicates(records):fromcollectionsimportdefaultdictid_dict=defaultdict(list)forrecordinrecords:id_dict[record[0]].append(record)result=[]forrecordinrecords:iflen(id_dict[record[0]])==1:result.append(record)else:id_dict[record[0]].sort(key=lambdax:x[1],reverse=True)result.append(id_dict[record[0]][0])returnresult示例调用records=[["1","2023-01-01","10"],["1","2023-01-02","15"],["2","2023-01-01","20"]]print(remove_duplicates(records))#输出：[["1","2023-01-02","15"],["2","2023-01-01","20"]]解析：-使用字典记录每个ID对应的所有记录，然后对每个ID的记录按时间戳降序排序，保留第一条（即最新一条）。-时间复杂度：O(NlogN)，其中N是记录数量，排序消耗主导时间。若需O(N)，可结合哈希表和单调栈优化，但需更复杂的实现。优化思路（O(N)）：pythondefremove_duplicates_optimized(records):fromcollectionsimportdefaultdictid_dict=defaultdict(lambda:{"timestamp":None,"value":None})forrecordinrecords:ifid_dict[record[0]]["timestamp"]isNoneorrecord[1]>id_dict[record[0]]["timestamp"]:id_dict[record[0]]={"timestamp":record[1],"value":record[2]}result=[list(v.values())fork,vinid_dict.items()]returnresult示例调用print(remove_duplicates_optimized(records))#输出：[["1","2023-01-02","15"],["2","2023-01-01","20"]]解析：-使用字典记录每个ID的最新记录，直接更新时间戳较晚的值。-时间复杂度：O(N)，空间复杂度：O(N)。3.（20分）题目：假设你需要设计一个算法来压缩一段文本，使用哈夫曼编码（HuffmanCoding）实现。给定一段文本，统计每个字符的频率，生成哈夫曼树，并输出每个字符的编码。输入：-文本：`"AAAAABBBCCC"`输出：-哈夫曼编码：`{'A':'0','B':'10','C':'110'}`要求：-必须使用优先队列（最小堆）实现哈夫曼树。答案与解析：答案：pythonimportheapqclassNode:def__init__(self,char,freq):self.char=charself.freq=freqself.left=Noneself.right=None实现比较操作，便于heapq使用def__lt__(self,other):returnself.freq<other.freqdefhuffman_encoding(text):fromcollectionsimportCounter统计字符频率freq=Counter(text)构建优先队列heap=[Node(char,count)forchar,countinfreq.items()]heapq.heapify(heap)whilelen(heap)>1:left=heapq.heappop(heap)right=heapq.heappop(heap)merged=Node(None,left.freq+right.freq)merged.left=leftmerged.right=rightheapq.heappush(heap,merged)root=heap[0]encoding={}defbuild_encoding(node,path=""):ifnodeisNone:returnifnode.char:encoding[node.char]=pathbuild_encoding(node.left,path+"0")build_encoding(node.right,path+"1")build_encoding(root)returnencoding示例调用text="AAAAABBBCCC"print(huffman_encoding(text))#输出：{'A':'0','B':'10','C':'110'}解析：-使用最小堆（优先队列）构建哈夫曼树，每次从堆中取出两个最小频率的节点合并，直到只剩一个节点作为根。-遍历哈夫曼树生成编码，左子树为`0`，右子树为`1`。-时间复杂度：O(NlogN)，其中N是字符数量。二、数据库设计题（共2题，每题25分）1.（25分）题目：假设你需要设计一个电商平台的订单表，支持高并发场景下的数据写入和查询。请设计表结构，并说明如何优化数据库性能。要求：-表结构需包含订单ID、用户ID、商品ID、数量、金额、下单时间等字段。-解释至少三种优化数据库性能的方法。答案与解析：答案：表结构：sqlCREATETABLEorders(order_idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,product_idBIGINTNOTNULL,quantityINTNOTNULLCHECK(quantity>0),amountDECIMAL(10,2)NOTNULL,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id),FOREIGNKEY(product_id)REFERENCESproducts(product_id));优化方法：1.索引优化：-对`user_id`和`product_id`建立复合索引，加速按用户或商品查询订单。-对`order_time`建立索引，支持按时间范围查询。2.分区表：-按时间（如按月）对订单表分区，将历史数据与实时数据分离，提高查询效率。3.读写分离：-使用主从复制，将写入操作在主库执行，查询操作在从库执行，分散负载。解析：-主键`order_id`唯一标识订单。-外键约束确保用户和商品存在。-索引和分区提升性能，读写分离提高并发能力。2.（25分）题目：假设你需要设计一个消息队列系统，支持消息的发布和订阅功能。请设计系统架构，并说明如何保证消息的可靠传输。要求：-说明至少两种消息确认机制。-解释如何处理消息重复消费的问题。答案与解析：答案：系统架构：1.生产者（Producer）：发送消息到队列。2.消息队列（Broker）：存储消息，分配给消费者。3.消费者（Consumer）：接收并处理消息。可靠传输机制：1.消息确认（ACK）：-消费者处理完消息后发送ACK，队列确认后删除消息。-若未ACK，队列重新投递给其他消费者。2.幂等性设计：-消息处理接口支持幂等操作，即多次执行结果一致。-通过唯一ID标记消息，避免重复处理。处理消息重复：-去重表：消费者记录已处理的消息ID，防止重复执行。-幂等键：消息中包含唯一键，消费者根据键去重。解析：-ACK机制确保消息不丢失。-幂等性设计防止重复处理。-去重表或幂等键解决重复消费问题。三、系统设计题（共2题，每题25分）1.（25分）题目：假设你需要设计一个高并发的短链接系统（如tinyURL），支持用户生成短链接并快速跳转到原链接。请说明系统架构，并解释如何保证系统的高可用性和扩展性。要求：-解释短链接生成算法。-说明至少两种高可用性方案。答案与解析：答案：系统架构：1.前端服务（APIGateway）：接收用户请求，分发到后端。2.短链接服务（Backend）：生成短链接，存储映射关系。3.分布式缓存（Redis/Memcached）：缓存短链接到原链接，加速查询。4.数据库：持久化短链接映射关系。短链接生成算法：-使用哈希函数（如SHA-256）将原链接哈希，取前6位作为短码。-若冲突，增加位数或随机重试。高可用性方案：1.负载均衡：使用Nginx或HAProxy分发请求到多个后端实例。2.异地多活：在不同地域部署服务，支持容灾切换。解析：-哈希算法确保短链接唯一。-负载均衡和异地多活提升可用性和扩展性。2.（25分）题目：假设你需要设计一个实时推荐系统，根据用户行为（如点击、购买）动态调整推荐结果。请说明系统架构，并解释如何优化推荐效率。要求：-说明推荐算法的核心思想。-解释至少两种优化方案。答案与解析：答案：系统架构：1.数据采集层：收集用户行为数