2025年软件工程师初级面试指南及模拟题

2025年软件工程师初级面试指南及模拟题一、编程基础(5题，每题2分，共10分)题目1：字符串反转题目描述：编写一个函数，接收一个字符串作为参数，返回该字符串的反转版本。示例：输入：`"hello"`输出：`"olleh"`要求：-不使用内置的反转函数-时间复杂度O(n)pythondefreverse_string(s:str)->str:#你的代码pass题目2：判断回文数题目描述：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都相同的整数。示例：输入：`121`输出：`True`示例：输入：`-121`输出：`False`要求：-不能将整数转为字符串-时间复杂度O(logn)pythondefis_palindrome(x:int)->bool:#你的代码pass题目3：合并两个有序数组题目描述：给定两个有序数组`nums1`和`nums2`，合并它们为一个有序数组。示例：输入：`nums1=[1,2,3]`,`nums2=[2,5,6]`输出：`[1,2,2,3,5,6]`要求：-不能使用额外的数组空间-时间复杂度O(m+n)pythondefmerge_sorted_arrays(nums1:List[int],m:int,nums2:List[int],n:int)->None:#你的代码pass题目4：两数相加题目描述：给出两个非空的链表，表示两个非负的整数。它们每个节点都按照逆序的方式存储，每个节点包含一个数字。将这两个数相加，并以相同形式返回结果。示例：输入：`(2->4->3)+(5->6->4)`输出：`7->0->8`解释：342+465=807要求：-不能使用额外的存储空间-时间复杂度O(max(m,n))python#定义链表节点classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefadd_two_numbers(l1:ListNode,l2:ListNode)->ListNode:#你的代码pass题目5：有效括号题目描述：给定一个字符串，包含`'{'`、`'['`、`'('`、`')'`、`']'`、`'}'`，判断字符串是否有效。有效字符串需要满足：-左括号必须与相同类型的右括号匹配-左括号必须按正确的顺序闭合示例：输入：`"()"`输出：`True`示例：输入：`"()[]{}"`输出：`True`要求：-使用栈实现-时间复杂度O(n)pythondefisValid(s:str)->bool:#你的代码pass二、算法与数据结构(5题，每题3分，共15分)题目6：查找数组中的重复项题目描述：给定一个包含n个整数的数组，其中恰好有k个重复的元素，找出数组中重复的元素。示例：输入：`[4,3,2,7,8,2,3,1]`输出：`[2,3]`要求：-不使用额外的存储空间-时间复杂度O(n)pythondeffind_duplicates(nums:List[int])->List[int]:#你的代码pass题目7：合并区间题目描述：给定一个区间列表，合并所有重叠的区间。示例：输入：`[[1,3],[2,6],[8,10],[15,18]]`输出：`[[1,6],[8,10],[15,18]]`要求：-合并后区间不重复-时间复杂度O(nlogn)pythondefmerge_intervals(intervals:List[List[int]])->List[List[int]]:#你的代码pass题目8：最短无重复字符子串题目描述：给定一个字符串，找到最长的无重复字符的子串长度。示例：输入：`"abcabcbb"`输出：`3`解释：无重复字符的最长子串是"abc"要求：-使用滑动窗口-时间复杂度O(n)pythondeflength_of_longest_substring(s:str)->int:#你的代码pass题目9：二叉树遍历题目描述：实现二叉树的深度优先遍历（前序、中序、后序）和广度优先遍历。示例：给定二叉树：1/\23/\45要求：-返回遍历结果列表-时间复杂度O(n)python#定义二叉树节点classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorder_traversal(root:TreeNode)->List[int]:#你的代码passdefinorder_traversal(root:TreeNode)->List[int]:#你的代码passdefpostorder_traversal(root:TreeNode)->List[int]:#你的代码passdeflevel_order_traversal(root:TreeNode)->List[List[int]]:#你的代码pass题目10：LRU缓存机制题目描述：设计LRU（最近最少使用）缓存，支持get和put操作。要求：-get(key)返回key对应的值，如果不存在返回-1-put(key,value)插入或更新key值，如果缓存容量已满，则删除最久未使用的项示例：LRUCachecapacity=2put(1,1)put(2,2)get(1)//返回1put(3,3)//去除键2get(2)//返回-1put(4,4)//去除键1get(1)//返回-1get(3)//返回3get(4)//返回4要求：-使用哈希表和双向链表实现-时间复杂度O(1)pythonclassLRUCache:def__init__(self,capacity:int):#你的代码passdefget(self,key:int)->int:#你的代码passdefput(self,key:int,value:int)->None:#你的代码pass三、系统设计(2题，每题10分，共20分)题目11：设计URL短链接服务题目描述：设计一个URL短链接服务，实现长链接到短链接的转换，以及短链接到长链接的还原。要求：-短链接应具有唯一性且易于生成-支持高并发访问-提供基本的统计功能（如点击次数）关键点：-短链接生成算法-高并发处理方式-数据存储方案-统计功能实现题目12：设计简单消息队列题目描述：设计一个简单的消息队列系统，支持生产者-消费者模式。要求：-支持消息的发布和订阅-保证消息的顺序性-实现至少100并发连接的能力-提供基本的错误处理关键点：-消息存储方案-并发控制机制-消息持久化策略-高可用设计四、数据库(2题，每题8分，共16分)题目13：设计用户注册表题目描述：设计一个用户注册表，包含以下字段：-用户ID（主键）-用户名（唯一）-邮箱（唯一）-密码（加密存储）-注册时间-最后登录时间要求：-关系型数据库设计-索引设计-数据一致性和安全性考虑题目14：设计订单表与商品表关系题目描述：设计订单表和商品表的关系，一个订单可以包含多个商品，一个商品可以出现在多个订单中。要求：-关系型数据库设计-关联表设计-SQL查询示例（如查询某个用户的订单商品列表）五、系统设计(2题，每题10分，共20分)题目11：设计URL短链接服务题目描述：设计一个URL短链接服务，实现长链接到短链接的转换，以及短链接到长链接的还原。要求：-短链接应具有唯一性且易于生成-支持高并发访问-提供基本的统计功能（如点击次数）关键点：-短链接生成算法-高并发处理方式-数据存储方案-统计功能实现题目12：设计简单消息队列题目描述：设计一个简单的消息队列系统，支持生产者-消费者模式。要求：-支持消息的发布和订阅-保证消息的顺序性-实现至少100并发连接的能力-提供基本的错误处理关键点：-消息存储方案-并发控制机制-消息持久化策略-高可用设计答案部分编程基础答案题目1：字符串反转pythondefreverse_string(s:str)->str:returns[::-1]题目2：判断回文数pythondefis_palindrome(x:int)->bool:ifx<0or(x%10==0andx!=0):returnFalsereversed_half=0whilex>reversed_half:reversed_half=reversed_half*10+x%10x=x//10returnx==reversed_halforx==reversed_half//10题目3：合并两个有序数组pythondefmerge_sorted_arrays(nums1:List[int],m:int,nums2:List[int],n:int)->None:p1,p2,p=m-1,n-1,m+n-1whilep1>=0andp2>=0:nums1[p]=nums1[p1]ifnums1[p1]>nums2[p2]elsenums2[p2]p1-=1p2-=1p-=1nums1[:p2+1]=nums2[:p2+1]题目4：两数相加pythondefadd_two_numbers(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummycarry=0whilel1orl2orcarry:val1=l1.valifl1else0val2=l2.valifl2else0total=val1+val2+carrycarry=total//10current.next=ListNode(total%10)current=current.nextifl1:l1=l1.nextifl2:l2=l2.nextreturndummy.next题目5：有效括号pythondefisValid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack算法与数据结构答案题目6：查找数组中的重复项pythondeffind_duplicates(nums:List[int])->List[int]:seen=set()duplicates=set()fornuminnums:ifnuminseen:duplicates.add(num)else:seen.add(num)returnlist(duplicates)题目7：合并区间pythondefmerge_intervals(intervals:List[List[int]])->List[List[int]]:intervals.sort(key=lambdax:x[0])merged=[]forintervalinintervals:ifnotmergedormerged[-1][1]<interval[0]:merged.append(interval)else:merged[-1][1]=max(merged[-1][1],interval[1])returnmerged题目8：最短无重复字符子串pythondeflength_of_longest_substring(s:str)->int:char_map={}left=0max_length=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_length=max(max_length,right-left+1)returnmax_length题目9：二叉树遍历pythondefpreorder_traversal(root:TreeNode)->List[int]:ifnotroot:return[]return[root.val]+preorder_traversal(root.left)+preorder_traversal(root.right)definorder_traversal(root:TreeNode)->List[int]:ifnotroot:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)defpostorder_traversal(root:TreeNode)->List[int]:ifnotroot:return[]returnpostorder_traversal(root.left)+postorder_traversal(root.right)+[root.val]deflevel_order_traversal(root:TreeNode)->List[List[int]]:ifnotroot:return[]queue=[root]result=[]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult题目10：LRU缓存机制pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=ListNode(0),ListNode(0)self.head.next=self.tailself.tail.prev=self.headdef_add_node(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_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_pop_tail(self):res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valdefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.val=valueself._move_to_head(node)系统设计答案题目11：设计URL短链接服务短链接生成算法：使用Base62编码（a-z、A-Z、0-9），将长链接的哈希值转换为62进制字符串。高并发处理：-使用Redis存储短链接映射关系-使用分布式缓存避免单点瓶颈-负载均衡部署多个服务实例数据存储：-短链接使用自增ID或UUID生成-使用Trie树优化短链接查询统计功能：-使用Redis的INCR命令实现点击次数统计-每次访问时更新缓存中的统计字段题目12：设计简单消息队列消息存储：-使用RabbitMQ或Kafka实现消息持久化-保证消息的顺序性（分区策略）并发控制：-使用线程池处理生产者请求-使用信号量控制消费者数量消息持久化：-消息写入磁盘前先写入Redis缓存-使用事务保证消息写入一致性高可用设计：-集群部署消息代理-使用分布式锁避免重复消费数据库答案题目13：设计用户注册表sqlCREATETABLEusers(user_idBIGINTAUTO_INCREMENTPRIMARYKEY,usernameVARCHAR(50)UNIQUENOTNULL,emailVARCHAR(100)UNIQUENOTNULL,password_hashCHAR(64)NOTNULL,registration_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,last_login_timeTIMESTAMPDEFAULTNULLONUPDATECURRENT_TIMESTAMP,INDEXidx_username(username),INDEXidx_email(email));索引设计：-用户名和邮箱建立唯一索引-最近登录时间建立索引优化查询数据一致性和安全性：-使用数据库事务保证注册流程原子性-密码使用bcrypt算法加盐存储题目14：设计订单表与商品表关系sqlCREATETABLEorders(order_idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,total_amountDECIMAL(10,2)NOTNULL,INDEXidx_user_id(user_id));CREATETABLEorder_items(item_idBIGINTAUTO_INCREMENTPRIMARYKEY,order_idBIGINTNOTNULL,product_idBIGINTNOTNULL,quantityINTNOTNU