2026年软件工程师面试专业问题集

2026年软件工程师面试专业问题集一、编程基础与数据结构（共5题，每题10分，总分50分）题目1（10分）题目：请实现一个函数，判断一个字符串是否是有效的括号组合。例如，输入"()[]{}",返回true；输入"(]",返回false；输入"([)]",返回false。答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping.values():stack.append(char)elifcharinmapping:ifnotstackorstack.pop()!=mapping[char]:returnFalseelse:returnFalsereturnnotstack解析：使用栈数据结构，遍历字符串中的每个字符。当遇到左括号时入栈，遇到右括号时检查栈顶元素是否匹配。如果匹配则出栈，否则返回false。最后栈为空则返回true，否则返回false。时间复杂度O(n)，空间复杂度O(n)。题目2（10分）题目：实现一个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=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用哈希表存储键值对，维护一个双向链表记录访问顺序。get操作时，如果存在则移动到链表尾部，否则返回-1。put操作时，如果存在则更新值并移动到链表尾部，如果不存在且已满则删除链表头部元素。时间复杂度O(1)。题目3（10分）题目：给定一个无重复元素的数组，找出所有可能的子集。答案：pythondefsubsets(nums):result=[]subset=[]defbacktrack(start):result.append(subset.copy())foriinrange(start,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：使用回溯算法。从第一个元素开始，每个元素都有两种选择：放入子集或不放入。递归遍历所有可能组合。时间复杂度O(2^n)，空间复杂度O(n)。题目4（10分）题目：实现快速排序算法。答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：选择基准元素，将数组分成小于、等于、大于三部分，然后递归排序左右两部分。平均时间复杂度O(nlogn)，最坏情况O(n^2)。题目5（10分）题目：实现二叉树的深度优先遍历（前序、中序、后序）。答案：python前序遍历defpreorder(root):ifnotroot:return[]result=[]stack=[root]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult中序遍历definorder(root):result=[]stack=[]current=rootwhilestackorcurrent:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()result.append(current.val)current=current.rightreturnresult后序遍历defpostorder(root):ifnotroot:return[]result=[]stack=[(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解析：前序遍历：根-左-右。中序遍历：左-根-右。后序遍历：左-右-根。使用栈实现非递归遍历。时间复杂度O(n)，空间复杂度O(h)。二、算法设计（共4题，每题15分，总分60分）题目1（15分）题目：设计一个算法，找出数组中重复次数超过数组长度一半的元素。答案：pythondefmajorityElement(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：Boyer-Moore投票算法。遍历数组，遇到候选元素则计数加1，否则减1。最终候选元素即为答案。时间复杂度O(n)，空间复杂度O(1)。题目2（15分）题目：设计一个算法，找出数组中和为特定值的最长子数组长度。答案：pythondeflongestSubarraySum(nums,target):sum_map={0:-1}max_length=0current_sum=0fori,numinenumerate(nums):current_sum+=numifcurrent_sum-targetinsum_map:max_length=max(max_length,i-sum_map[current_sum-target])ifcurrent_sumnotinsum_map:sum_map[current_sum]=ireturnmax_length解析：前缀和+哈希表。记录前缀和首次出现的位置，如果current_sum-target在哈希表中，则表示子数组和为target。更新最长长度。时间复杂度O(n)，空间复杂度O(n)。题目3（15分）题目：设计一个算法，实现LRU缓存的高效实现。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodenode.prev=self.headself.head.next=node解析：使用双向链表+哈希表实现。链表头部为最近使用，尾部为最久未使用。哈希表存储键到节点的映射。get操作将节点移到头部，put操作将新节点插入头部，如果超出容量则删除尾部节点。时间复杂度O(1)，空间复杂度O(n)。题目4（15分）题目：设计一个算法，将字符串中的所有大写字母转换为小写字母。答案：pythondeftoLowerCase(s:str)->str:returns.lower()解析：Python内置的lower()方法可以直接将所有大写字母转换为小写。时间复杂度O(n)，空间复杂度O(n)。三、系统设计（共2题，每题20分，总分40分）题目1（20分）题目：设计一个简单的微博系统，支持用户发布微博、关注/取消关注、获取关注者时间线等功能。答案：1.数据模型：-User：用户表（id,name,email）-Tweet：微博表（id,user_id,content,timestamp）-Follow：关注关系表（follower_id,followee_id）2.核心功能：-发布微博：插入一条新记录到Tweet表，关联用户id和时间戳。-关注/取消关注：插入或删除Follow表记录。-获取时间线：查询关注用户的最新N条微博，按时间降序排列。3.伪代码：sql--发布微博INSERTINTOTweet(user_id,content,timestamp)VALUES(?,?,NOW())--关注用户INSERTINTOFollow(follower_id,followee_id)VALUES(?,?)--取消关注DELETEFROMFollowWHEREfollower_id=?ANDfollowee_id=?--获取时间线SELECTT.id,T.content,T.timestamp,U.nameFROMTweetTJOINUserUONT.user_id=U.idJOINFollowFONT.user_id=F.followee_idWHEREF.follower_id=?ORDERBYT.timestampDESCLIMIT?4.优化考虑：-缓存：对用户时间线进行缓存，减少数据库查询。-分页：获取时间线时支持分页，避免单次查询数据过多。-索引：为user_id,followee_id,timestamp字段添加索引。解析：系统需包含用户、微博、关注关系三个核心表。发布微博时插入新记录，关注关系维护用户间的连接。获取时间线时联合查询用户表和关注关系表，获取关注用户的微博。优化可通过缓存和索引提高性能。题目2（20分）题目：设计一个短链接生成系统，输入长链接生成短链接，并能通过短链接跳转回原始长链接。答案：1.数据模型：-ShortLink：短链接表（id,original_url,short_code,created_at）2.核心功能：-生成短链接：将长链接转换为短码，存入数据库。-跳转：根据短码查询原始链接，返回重定向。3.实现方案：-短码生成：使用Base62编码（a-z,A-Z,0-9）将ID映射为6位短码。-查询优化：为short_code和id添加索引。4.伪代码：sql--生成短链接INSERTINTOShortLink(original_url,short_code)VALUES(