2026年软件开发工程师技术面试试题

2026年软件开发工程师技术面试试题一、编程题（共5题，每题20分，总分100分）1.题目：编写一个函数，实现快速排序算法。输入一个整数数组，返回排序后的数组。要求使用原地排序（不使用额外数组），并说明时间复杂度和空间复杂度。示例输入：`[3,1,4,1,5,9,2,6,5,3,5]`示例输出：`[1,1,2,3,3,4,5,5,5,6,9]`2.题目：实现一个无重复字符的最长子串查找函数。输入一个字符串，返回最长无重复字符的子串长度。示例输入：`"abcabcbb"`示例输出：`3`（最长无重复子串为"abc"）3.题目：设计一个简单的LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。缓存容量为固定值`capacity`。要求实现时间复杂度为O(1)的版本。示例输入：-`put(1,1)`-`put(2,2)`-`get(1)`→返回`1`-`put(3,3)`（使键1作废）-`get(2)`→返回`2`4.题目：编写一个函数，检查一个二叉树是否是二叉搜索树（BST）。假设节点定义如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right示例输入：pythonroot=TreeNode(2,TreeNode(1),TreeNode(3))示例输出：`True`5.题目：实现一个简单的Trie（前缀树），支持`insert`和`search`操作。示例输入：-`insert("apple")`-`search("apple")`→返回`True`-`search("app")`→返回`False`-`startsWith("app")`→返回`True`二、算法题（共5题，每题20分，总分100分）1.题目：给定一个非负整数数组，返回其中连续子数组的最大和。要求使用动态规划解决。示例输入：`[-2,1,-3,4,-1,2,1,-5,4]`示例输出：`6`（子数组[4,-1,2,1]）2.题目：实现一个函数，判断一个整数是否是素数。要求时间复杂度为O(√n)。示例输入：`17`示例输出：`True`3.题目：给定一个字符串`s`和一个字符集`words`，判断`s`是否可以由`words`中的单词串联而成。每个单词可以重复使用。示例输入：-`s="leetcode"`-`words=["leet","code"]`示例输出：`True`（"leetcode"="leet"+"code"）4.题目：实现一个函数，计算二叉树的所有节点之和。假设节点定义同编程题第4题。示例输入：pythonroot=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3))示例输出：`15`（1+2+3+4+5）5.题目：给定一个整数`n`，返回`n`的格雷码序列。格雷码是一个二进制数字序列，其中任意两个相邻数字的二进制表示只有一位不同。示例输入：`2`示例输出：`[0,1,3,2]`（格雷码为"00","01","11","10"）三、系统设计题（共3题，每题33分，总分99分）1.题目：设计一个简单的微博系统，支持用户发布、关注、获取时间线等基本功能。需要说明系统架构、数据存储方式（数据库选型及表结构）、关键接口设计（如发布微博、获取关注者时间线）。2.题目：设计一个短链接生成服务，要求：-支持将长链接转换为短链接，并可通过短链接跳转回原链接。-高并发场景下仍能稳定运行。-需要说明技术选型（如数据库、缓存）、短链接生成算法、系统架构。3.题目：设计一个实时聊天系统，支持一对一和群组聊天。需要说明系统架构（如WebSocket、消息队列）、数据存储方式（如聊天记录、用户关系）、关键功能实现（如消息推送、离线消息）。答案与解析编程题答案与解析1.快速排序代码：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²)（当pivot取到最小或最大值时）。-空间复杂度：O(logn)（递归栈空间）。2.最长无重复子串代码：pythondeflength_of_longest_substring(s):char_set=set()left=0max_len=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len解析：-使用滑动窗口思想，`left`和`right`分别表示窗口的左右边界。-时间复杂度：O(n)，每个字符最多访问两次。3.LRU缓存代码：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:self.cache.pop(self.order.pop(0))self.cache[key]=valueself.order.append(key)解析：-使用哈希表记录键值对，`order`列表记录访问顺序。-`get`操作时移动键到末尾，`put`操作时先删除最久未使用的键。4.检查BST代码：pythondefis_valid_BST(root:TreeNode)->bool:defhelper(node,low=float('-inf'),high=float('inf')):ifnotnode:returnTrueifnot(low<node.val<high):returnFalsereturnhelper(node.left,low,node.val)andhelper(node.right,node.val,high)returnhelper(root)解析：-BST中左子树所有节点<根节点<右子树所有节点。-递归验证每个节点是否在合法范围内。5.Trie实现代码：pythonclassTrieNode:def__init__(self):self.children={}self.is_end=FalseclassTrie:def__init__(self):self.root=TrieNode()definsert(self,word:str)->None:node=self.rootforcharinword:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.is_end=Truedefsearch(self,word:str)->bool:node=self._find(word)returnnodeisnotNoneandnode.is_enddefstartsWith(self,prefix:str)->bool:returnself._find(prefix)isnotNonedef_find(self,word:str):node=self.rootforcharinword:ifcharnotinnode.children:returnNonenode=node.children[char]returnnode解析：-Trie通过哈希表存储子节点，`is_end`标记单词结束。-`search`和`startsWith`分别检查完整单词和前缀。算法题答案与解析1.最大子数组和代码：pythondefmax_subarray(nums):max_sum=nums[0]current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum解析：-动态规划思想，`current_sum`记录当前最大和，`max_sum`记录全局最大和。-时间复杂度：O(n)，空间复杂度：O(1)。2.判断素数代码：pythondefis_prime(n):ifn<=1:returnFalseforiinrange(2,int(n0.5)+1):ifn%i==0:returnFalsereturnTrue解析：-只需检查到√n即可，因为若n有因子，必有一个≤√n。3.字符串分割代码：pythondefword_break(s,words):word_set=set(words)dp=[False](len(s)+1)dp[0]=Trueforiinrange(1,len(s)+1):forjinrange(i):ifdp[j]ands[j:i]inword_set:dp[i]=Truebreakreturndp[-1]解析：-动态规划，`dp[i]`表示前i个字符能否被分割。-时间复杂度：O(n²)，空间复杂度：O(n)。4.二叉树节点之和代码：pythondefsum_tree(root):ifnotroot:return0returnroot.val+sum_tree(root.left)+sum_tree(root.right)解析：-递归遍历所有节点并累加。-时间复杂度：O(n)，空间复杂度：O(h)（递归栈）。5.格雷码生成代码：pythondefgray_code(n):return[i^(i>>1)foriinrange(1<<n)]解析：-格雷码可通过`i^(i>>1)`生成，其中`i>>1`是i右移一位。-时间复杂度：O(2^n)，空间复杂度：O(2^n)。系统设计题答案与解析1.微博系统设计系统架构：-前端：Web/移动端（React/Vue+Flutter）-后端：API服务器（SpringBoot/Go+RESTfulAPI）-数据库：MySQL（用户信息、关系）、Redis（缓存、计数器）-消息队列：Kafka/RabbitMQ（发布/订阅）表结构：sql--用户表CREATETABLEusers(idBIGINTAUTO_INCREMENTPRIMARYKEY,usernameVARCHAR(50)UNIQUE,passwordVARCHAR(255),create_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP);--关注关系表CREATETABLEfollows(follower_idBIGINT,followee_idBIGINT,PRIMARYKEY(follower_id,followee_id),FOREIGNKEY(follower_id)REFERENCESusers(id),FOREIGNKEY(followee_id)REFERENCESusers(id));关键接口：-`POST/api/status`（发布微博）-`GET/api/status/timeline`（获取时间线）解析：-微博核心是关注关系