2026年金山软件工程师面试问题及答案

2026年金山软件工程师面试问题及答案一、编程能力测试（共5题，每题20分，总分100分）1.编程题（20分）题目：编写一个函数，实现将任意长度的字符串反转，但需保留字符串中所有数字的相对顺序。例如，输入`"a-bc-123-d"`，输出`"d-321-cba-a-b"`。要求：-不能使用现成的反转库函数。-时间复杂度不超过O(n)。-代码需支持多线程处理（Python语言）。答案：pythonimportthreadingdefreverse_string(s):letters=[]digits=[]forcharins:ifchar.isdigit():digits.append(char)else:letters.append(char)letters.reverse()result=[]digit_index=0forcharins:ifchar.isdigit():result.append(digits[digit_index])digit_index+=1else:result.append(char)return''.join(result)defmulti_thread_reverse(s):n=len(s)threads=[]results=['']ndefworker(i):ifs[i].isdigit():results[i]=reverse_string(s[i])else:results[i]=s[i]foriinrange(n):t=threading.Thread(target=worker,args=(i,))threads.append(t)t.start()fortinthreads:t.join()return''.join(results)示例input_str="a-bc-123-d"print(multi_thread_reverse(input_str))#输出："d-321-cba-a-b"解析：-首先将字符串中的字母和数字分别存储，字母部分直接反转，数字部分保持原顺序。-通过多线程处理每个字符的转换，提高处理效率（尽管PythonGIL限制了实际并行性，但逻辑上支持）。-时间复杂度为O(n)，空间复杂度为O(n)。2.编程题（20分）题目：实现一个LRU（最近最少使用）缓存，支持get和put操作。缓存容量为固定值`capacity`。-`get(key)`:返回key对应的值，如果不存在返回-1。-`put(key,value)`:插入或更新key值，如果容量已满，则删除最久未使用的项。要求：-使用双向链表和哈希表实现。-get和put操作的时间复杂度为O(1)。答案：pythonclassListNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.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.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_front(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_front(node)else:iflen(self.cache)==self.capacity:self._remove_least_recently_used()new_node=ListNode(key,value)self.cache[key]=new_nodeself._add_to_front(new_node)def_move_to_front(self,node):self._remove_node(node)self._add_to_front(node)def_add_to_front(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_remove_least_recently_used(self):tail_prev=self.tail.prevself._remove_node(tail_prev)delself.cache[tail_prev.key]示例lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#返回1lru.put(3,3)#去除键2print(lru.get(2))#返回-1解析：-使用双向链表维护访问顺序，哈希表存储key到节点的映射。-get操作将节点移动到链表头部，put操作同样将新节点插入头部，若容量满则删除尾部节点。-时间复杂度为O(1)，空间复杂度为O(capacity)。3.编程题（20分）题目：给定一个包含重复元素的数组，返回所有不重复的全排列。例如，输入`[1,1,2]`，输出`[[1,1,2],[1,2,1],[2,1,1]]`。要求：-不能使用现成的排列库函数。-排列需去重。答案：pythondefpermute_unique(nums):result=[]nums.sort()#排序以便去重used=[False]len(nums)path=[]defbacktrack():iflen(path)==len(nums):result.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack()path.pop()used[i]=Falsebacktrack()returnresult示例print(permute_unique([1,1,2]))#输出：[[1,1,2],[1,2,1],[2,1,1]]解析：-先对数组排序，以便通过相邻元素相同且前一个未被使用来跳过重复排列。-使用回溯法生成所有排列，通过`used`数组记录已使用元素。-时间复杂度为O(n!)，空间复杂度为O(n)。4.编程题（20分）题目：实现一个二叉树的深度优先遍历（前序、中序、后序），并分别用递归和迭代方式实现。要求：-迭代方式使用栈实现。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right递归遍历defpreorder_recursive(root):ifnotroot:return[]return[root.val]+preorder_recursive(root.left)+preorder_recursive(root.right)definorder_recursive(root):ifnotroot:return[]returninorder_recursive(root.left)+[root.val]+inorder_recursive(root.right)defpostorder_recursive(root):ifnotroot:return[]returnpostorder_recursive(root.left)+postorder_recursive(root.right)+[root.val]迭代遍历defpreorder_iterative(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresultdefinorder_iterative(root):stack,result,current=[],[],rootwhilestackorcurrent:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()result.append(current.val)current=current.rightreturnresultdefpostorder_iterative(root):ifnotroot:return[]stack,result=[(root,False)],[]whilestack:node,visited=stack.pop()ifnode:ifvisited:result.append(node.val)else:stack.append((node,True))stack.append((node.right,False))stack.append((node.left,False))returnresult示例root=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3))print("前序递归:",preorder_recursive(root))print("中序递归:",inorder_recursive(root))print("后序递归:",postorder_recursive(root))print("前序迭代:",preorder_iterative(root))print("中序迭代:",inorder_iterative(root))print("后序迭代:",postorder_iterative(root))解析：-递归方式直接通过函数调用实现。-迭代方式使用栈模拟递归调用栈，前序遍历先处理当前节点，中序遍历左节点压栈，后序遍历先右后左。-时间复杂度为O(n)，空间复杂度为O(n)。5.编程题（20分）题目：实现一个二分查找，但数组可能存在重复元素，返回第一个等于目标值的元素的下标。要求：-不能使用现成的二分查找库函数。答案：pythondefbinary_search_first_occurrence(nums,target):left,right=0,len(nums)-1result=-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:result=midright=mid-1#继续向左查找elifnums[mid]<target:left=mid+1else:right=mid-1returnresult示例print(binary_search_first_occurrence([1,2,2,3,4,4,4,5],4))#输出：4解析：-与标准二分查找类似，但找到目标值后继续向左移动`right`指针，直到找到第一个目标值。-时间复杂度为O(logn)，空间复杂度为O(1)。二、系统设计测试（共3题，每题30分，总分90分）1.系统设计题（30分）题目：设计一个短链接服务（如TinyURL），支持将长链接转换为短链接，并能够通过短链接解析回原始长链接。要求：-短链接需具有唯一性且长度尽可能短。-支持高并发访问。-需考虑数据一致性和容错性。答案：-系统架构：-前端：提供API接口（如`/shorten`和`/resolve`）。-中间层：使用Redis缓存热点短链接，避免频繁查询数据库。-后端：使用MySQL存储短链接和长链接映射关系。-分布式部署：使用Nginx负载均衡，水平扩展。-短链接生成：-使用哈希函数（如SHA-256）对长链接生成固定长度的唯一标识。-压缩标识（如Base62编码），将`0-9`、`a-z`、`A-Z`映射到短链接字符。-数据一致性：-使用Redis事务确保短链接生成和数据库插入的原子性。-分布式锁防止并发生成相同短链接。-容错性：-使用分布式数据库和缓存，避免单点故障。-定期备份数据库。解析：-短链接生成需保证唯一性和长度，哈希+Base62是常用方案。-高并发可通过Redis缓存和数据库读写分离优化。-分布式锁和事务保证数据一致性。2.系统设计题（30分）题目：设计一个实时消息推送系统（如微信推送），支持多平台（iOS、Android、Web）的消息发送和接收。要求：-支持离线消息存储和重传。-保证消息的可靠性和顺序性。-支持消息分片和重连机制。答案：-系统架构：-消息中心：负责接收、存储和转发消息。-客户端：通过WebSocket或MQTT与消息中心保持连接。-消息队列：使用Kafka或RabbitMQ存储离线消息。-消息存储：-使用关系型数据库存储消息元数据（发送者、接收者、时间等）。-使用Redis缓存热点消息。-离线消息：-客户端连接断开时，消息存储到Kafka中。-客户端重连后，从Kafka读取未发送的消息。-消息分片：-消息超过长度限制时，分片存储到数据库，客户端按顺序重组。-可靠性与顺序性：-使用消息ID和发送顺序保证消息顺序。-重试机制和超时处理防止消息丢失。解析：-实时性通过WebSocket或MQTT实现，离线消息依赖消息队列。-消息分片和重连机制是关键，需考虑客户端处理逻辑。3.系统设计题（30分）题目：设计一个分布式计数器服务，支持高并发计数和原子性。要求：-支持全局唯一计数。-分布式部署，可水平扩展。-高可用性和容错性。答案：-系统架构：-使用Redis的`INCR`命令实现原子计数。-使用Redis集群保证高可用和扩展性。-每个节点存储部分计数范围，避免热点问题。-原子计数：-`INCR`命令保证计数操作原子性。-使用Redis事务处理复杂计数逻辑。-高可用与容错：-Redis集群自动分片和故障转移。-使用哨兵（Sentinel）或集群模式监控节点状态。-水平扩展：-通过增加Redis集群节点扩展计数能力。-负载均衡器分发请求。解析：-Redis是常用方案，`INCR`命令简化实现。-集群和哨兵模式保证高可用。三、数据库测试（共2题，每题15分，总分30分）1.数据库题（15分）题目：设计一个简单的社交系统数据库表结构，包含用户、关注、动态三个表。要求：-用户表包含用户ID、昵称、注册时间。-关注表支持单向关注关系。-动态表包含动态ID、用户ID、内容、发布时间。答案：sql--用户表CREATETABLEusers(user_idINTPRIMARYKEYAUTO_INCREMENT,nicknameVARCHAR(50)NOTNULL,registration_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP);--关注表CREATETABLEfollows(follower_idINT,followee_idINT,follow_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,PRIMARYKEY(follower_id,followee_id),FOREIGNKEY(follower_id)REFERENCESusers(user_id),FOREIGNKEY(followee_id)REFERENCESusers(user_id));--动态表CREATETABLEposts(post_idINTPRIMARYKEYAUTO_INCREMENT,user_idINT,contentTEXTNOTNULL,post_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id));解析：-用户表使用自增ID和昵称字段。-关注表使用复合主键避免重复关注，外键关联用户表。-动态表使用自增ID、用户ID和内容字段。2.数据库题