软件开发工程师面试中编程测试指南

2026年软件开发工程师面试中编程测试指南一、算法设计题（共3题，每题15分，总分45分）题目1（15分）：字符串转换整数（atoi）问题描述：实现一个atoi函数，将字符串转换为整数。具体要求如下：1.去除字符串前后的空白字符2.忽略开头正负号（如果存在）3.遇到非数字字符时停止转换4.如果转换后的数字超出32位整数范围（-2^31~2^31-1），则返回相应的边界值5.如果字符串为空或不符合转换规则，返回0示例：-输入："-42"输出：-42-输入："4193withwords"输出：4193-输入："wordsand987"输出：0-输入："-91283472332"输出：-2147483648要求：-时间复杂度：O(n)-空间复杂度：O(1)题目2（15分）：三数之和问题描述：给定一个包含n个整数的数组nums，判断数组中是否存在三个元素a,b,c，使得a+b+c=0。找出所有满足条件且不重复的三元组。示例：-输入：[-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]-输入：[]输出：[]-输入：[0]输出：[]要求：-时间复杂度：O(n^2)-空间复杂度：O(1)题目3（15分）：最长有效括号问题描述：给定一个只包含'('和')'的字符串，找出最长的有效（正确括号）子串的长度。示例：-输入："()()"输出：2-输入："(()"输出：2-输入："()(())"输出：6要求：-时间复杂度：O(n)-空间复杂度：O(n)二、数据结构实现题（共2题，每题20分，总分40分）题目4（20分）：自定义LRU缓存问题描述：实现LRU（LeastRecentlyUsed）缓存机制。LRU缓存会按照使用频率来淘汰最久未使用的项目。要求：-支持get和put操作-get(key)-如果键存在，返回对应的值，并将其标记为最近使用；如果不存在，返回-1-put(key,value)-如果键存在，更新其值并标记为最近使用；如果不存在，添加键值对，如果缓存已满，则删除最久未使用的项目示例：-初始化LRUCache容量为2-put(1,1)//缓存是{1=1}-put(2,2)//缓存是{1=1,2=2}-get(1)//返回1-put(3,3)//去除键2，缓存是{1=1,3=3}-get(2)//返回-1(未找到)-put(4,4)//去除键1，缓存是{4=4,3=3}提示：-可以使用哈希表和双向链表结合实现题目5（20分）：二叉树深度优先遍历框架问题描述：实现一个二叉树的深度优先遍历框架。你需要提供前序、中序和后序遍历的递归实现。要求：-定义二叉树节点结构-实现三个遍历函数-可以选择返回遍历结果列表或执行特定操作示例：-给定二叉树：1/\23/\45-前序遍历结果：[1,2,4,5,3]-中序遍历结果：[4,2,5,1,3]-后序遍历结果：[4,5,2,3,1]三、系统设计题（共1题，30分）题目6（30分）：设计简单微博系统问题描述：设计一个简单的微博系统，需要支持以下核心功能：1.用户注册和登录2.发布微博（限制长度，如140字符）3.关注/取消关注用户4.获取关注用户的微博流5.点赞/取消点赞微博要求：-描述系统架构（可使用文字描述或简单草图）-说明核心数据结构设计-描述关键接口设计-考虑高并发场景下的解决方案（如限流、降级等）-说明数据一致性保障措施答案与解析答案1：字符串转换整数（atoi）pythonclassSolution:defmyAtoi(self,s:str)->int:ifnots:return0去除前后空白s=s.strip()ifnots:return0初始化sign=1i=0处理正负号ifs[0]=='-':sign=-1i+=1elifs[0]=='+':i+=1result=0INT_MAX=231-1INT_MIN=-231whilei<len(s)ands[i].isdigit():digit=int(s[i])溢出判断ifresult>(INT_MAX-digit)//10:returnINT_MINifsign==-1elseINT_MAXresult=result10+digiti+=1returnsignresult解析：1.首先去除字符串前后的空白字符2.检查第一个字符是否为正负号，并相应调整3.使用while循环遍历字符串，直到遇到非数字字符4.在每次迭代中，检查是否会发生溢出：-如果result>(INT_MAX-digit)//10，说明再乘10加当前数字会溢出5.返回最终结果，考虑符号答案2：三数之和pythonclassSolution:defthreeSum(self,nums:List[int])->List[List[int]]:nums.sort()n=len(nums)res=[]foriinrange(n-2):跳过重复元素ifi>0andnums[i]==nums[i-1]:continue双指针left,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:res.append([nums[i],nums[left],nums[right]])跳过重复元素whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnres解析：1.首先对数组进行排序，便于后续处理2.使用固定指针i遍历数组，对于每个i，使用左右指针寻找两个数使三数之和为03.使用双指针方法，如果和为0，记录结果并移动指针跳过重复元素4.如果和小于0，左指针右移；如果和大于0，右指针左移5.时间复杂度为O(n^2)，空间复杂度为O(1)答案3：最长有效括号pythonclassSolution:deflongestValidParentheses(self,s:str)->int:max_len=0stack=[-1]#初始化栈底fori,charinenumerate(s):ifchar=='(':stack.append(i)else:stack.pop()#弹出最近的'('ifnotstack:stack.append(i)#重置栈底else:当前有效长度current_len=i-stack[-1]max_len=max(max_len,current_len)returnmax_len解析：1.使用栈来跟踪'('的位置，初始化栈底为-12.遍历字符串，对于'('，压入栈3.对于')'，弹出栈顶元素：-如果栈为空，将当前索引压入栈-如果栈不为空，计算当前有效长度并更新最大值4.时间复杂度为O(n)，空间复杂度为O(n)答案4：自定义LRU缓存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)#去除最久未使用解析：1.使用Python的OrderedDict实现LRU缓存2.get操作时，将访问的键移动到末尾表示最近使用3.put操作时：-如果键已存在，移动到末尾并更新值-如果键不存在，添加新键值对-如果超出容量，弹出最早的键值对4.OrderedDict保持元素插入顺序，move_to_end操作将元素移动到末尾答案5：二叉树深度优先遍历框架pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassSolution:defpreorderTraversal(self,root:TreeNode)->List[int]:res=[]defdfs(node):ifnotnode:returnres.append(node.val)#前序：访问节点dfs(node.left)dfs(node.right)dfs(root)returnresdefinorderTraversal(self,root:TreeNode)->List[int]:res=[]defdfs(node):ifnotnode:returndfs(node.left)res.append(node.val)#中序：左节点-访问-右节点dfs(node.right)dfs(root)returnresdefpostorderTraversal(self,root:TreeNode)->List[int]:res=[]defdfs(node):ifnotnode:returndfs(node.left)dfs(node.right)res.append(node.val)#后序：左节点-右节点-访问dfs(root)returnres解析：1.定义二叉树节点结构2.实现三种遍历的递归框架：-前序：访问节点->遍历左子树->遍历右子树-中序：遍历左子树->访问节点->遍历右子树-后序：遍历左子树->遍历右子树->访问节点3.使用递归实现深度优先遍历答案6：设计简单微博系统系统架构：+-++-++-+|用户服务||微博服务||存储服务|+-++-++-+|-用户注册||-发布微博||-用户数据||-用户登录||-获取微博流||-微博数据||-验证码生成||-关注/取消关注||-点赞数据|+-+|-获取关注用户|+-+|-点赞/取消点赞|+-+核心数据结构设计：python用户表User={'id':int,'username':str,'password_hash':str,'email':str,'followees':Set[int],#关注的用户'followers':Set[int],#关注者'created_at':datetime}微博表Tweet={'id':int,'user_id':int,'content':str,'created_at':datetime,'likes':Set[int],#点赞用户'replies':List[int]#回复微博ID}点赞表Like={'user_id':int,'tweet_id':int}关键接口设计：python用户服务defregister(username:str,password:str,email:str)->bool:检查用户名是否存在生成密码哈希存储用户信息passdeflogin(username:str,password:str)->bool:校验用户名和密码pass微博服务defpost_tweet(user_id:int,content:str)->bool:校验用户存储微博passdefget_timeline(user_id:int)->List[T