软件开发工程师面试要点与题集

2026年软件开发工程师面试要点与题集一、编程基础与数据结构（共5题，每题10分，总分50分）1.题目：请实现一个函数，输入一个整数数组，返回该数组中所有唯一数字的和。例如，输入`[1,2,2,1,3]`，返回`6`（即`1+3`）。答案：pythondefunique_sum(nums):returnsum(set(nums))解析：-使用`set(nums)`去除重复元素，然后使用`sum()`计算和。时间复杂度O(n)，空间复杂度O(n)。2.题目：请实现一个算法，判断一个字符串是否是另一个字符串的子串。例如，输入`"hello"`和`"ll"`，返回`True`。答案：pythondefis_substring(s,sub):returnsubins解析：-利用Python字符串的`in`操作符判断子串是否存在。时间复杂度O(n)，空间复杂度O(1)。3.题目：请实现一个函数，输入一个字符串，返回该字符串的所有排列组合。例如，输入`"abc"`，返回`["abc","acb","bac","bca","cab","cba"]`。答案：pythondefpermute(s):iflen(s)==1:return[s]result=[]foriinrange(len(s)):char=s[i]remaining=s[:i]+s[i+1:]forpinpermute(remaining):result.append(char+p)returnresult解析：-递归解法：固定一个字符，递归排列剩余字符，然后组合。时间复杂度O(n!)，空间复杂度O(n!)。4.题目：请实现一个函数，输入一个链表，返回该链表的中间节点。例如，输入`[1,2,3,4,5]`，返回`3`（假设节点从1开始编号）。答案：pythondefmiddle_node(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextreturnslow解析：-快慢指针法：快指针每次走两步，慢指针每次走一步，当快指针到末尾时，慢指针在中间。时间复杂度O(n)，空间复杂度O(1)。5.题目：请实现一个函数，输入一个字符串，返回该字符串的所有子集。例如，输入`"abc"`，返回`["","a","b","c","ab","ac","bc","abc"]`。答案：pythondefsubsets(s):result=[[]]forcharins:result+=[curr+[char]forcurrinresult]returnresult解析：-迭代解法：每次添加一个字符，生成新的子集组合。时间复杂度O(2^n)，空间复杂度O(2^n)。二、算法与设计（共5题，每题15分，总分75分）1.题目：请设计一个LRU（最近最少使用）缓存，支持`get`和`put`操作。例如，容量为2，`put(1,1)`，`put(2,2)`，`get(1)`返回`1`，`put(3,3)`会删除键`2`。答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache=OrderedDict()defget(self,key):ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key,value):self.cache[key]=valueself.cache.move_to_end(key)iflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：-使用`OrderedDict`维护插入顺序，`get`时移动到末尾，`put`时覆盖并移动到末尾，超出容量时删除最久未使用的项。时间复杂度O(1)，空间复杂度O(capacity)。2.题目：请实现一个函数，输入一个整数，返回其二进制翻转后的值。例如，输入`5`（二进制`101`），返回`2`（二进制`010`）。答案：pythondefreverse_bits(n):result=0for_inrange(32):result=(result<<1)|(n&1)n>>=1returnresult&0xFFFFFFFF解析：-逐位翻转：从最低位开始，将结果左移一位并添加当前位，然后右移一位处理下一位。时间复杂度O(1)，空间复杂度O(1)。3.题目：请设计一个算法，判断一个无向图是否存在环。可以使用邻接表或邻接矩阵。答案：pythondefhas_cycle(n,edges):graph=defaultdict(list)foru,vinedges:graph[u].append(v)visited=[False]nrec_stack=[False]ndefdfs(node):visited[node]=Truerec_stack[node]=Trueforneighboringraph[node]:ifnotvisited[neighbor]:ifdfs(neighbor):returnTrueelifrec_stack[neighbor]:returnTruerec_stack[node]=FalsereturnFalseforiinrange(n):ifnotvisited[i]:ifdfs(i):returnTruereturnFalse解析：-深度优先搜索（DFS）检测环：使用`visited`记录已访问节点，`rec_stack`记录递归栈中的节点。若再次访问到递归栈中的节点，则存在环。时间复杂度O(V+E)，空间复杂度O(V)。4.题目：请设计一个算法，输入一个单词列表，返回所有可能的有效括号组合。例如，输入`n=3`，返回`["((()))","(()())","(())()","()(())","()()()"]`。答案：pythondefgenerate_parentheses(n):result=[]defbacktrack(s,left,right):iflen(s)==2n:result.append(s)returnifleft<n:backtrack(s+'(',left+1,right)ifright<left:backtrack(s+')',left,right+1)backtrack('',0,0)returnresult解析：-回溯法：每次选择添加`'('`或`')'`，但必须满足`left<=n`和`right<=left`。时间复杂度O(4^n/√n)，空间复杂度O(4^n/√n)。5.题目：请设计一个算法，输入一个整数数组，返回该数组的最长递增子序列（LIS）的长度。例如，输入`[10,9,2,5,3,7,101,18]`，返回`4`（即`[2,3,7,101]`）。答案：pythondeflength_of_lis(nums):tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midtails[right]=numreturnlen(tails)解析：-二分查找优化：维护一个`tails`数组，记录每个长度的最小结尾值。时间复杂度O(nlogn)，空间复杂度O(n)。三、系统设计（共3题，每题25分，总分75分）1.题目：请设计一个简单的微博系统，支持发布、关注、获取时间线等基本功能。假设用户和微博数据量在百万级别。答案：-数据存储：-用户：`users`表（`id`,`name`,`follows`）-微博：`tweets`表（`id`,`user_id`,`content`,`timestamp`）-关注关系：`follows`表（`follower_id`,`followee_id`）-发布：-写入`tweets`表，使用`timestamp`排序。-获取时间线：-查询`tweets`表，按`timestamp`降序，且`user_id`在`follows`表中。-缓存热点用户的时间线。-扩展性：-使用分布式数据库（如MySQLCluster或PostgreSQL）。-使用消息队列（如Kafka）处理高并发写入。-使用Redis缓存热点数据。解析：-关系型数据库存储核心数据，支持高并发写入和查询。关注关系用关联表存储，时间线查询时联合`follows`表。缓存热点数据减少数据库压力。分布式数据库和消息队列提升扩展性。2.题目：请设计一个短链接系统，支持将长链接转换为短链接，并能够通过短链接访问原始链接。答案：-数据存储：-`links`表（`id`,`long_url`,`short_code`,`timestamp`）-生成短链接：-使用哈希算法（如MD5或Base62编码）将长链接映射为短码。-确保短码唯一性，可使用自增ID或随机码。-访问短链接：-根据短码查询`links`表，返回`long_url`。-缓存热点短链接。-高可用性：-使用分布式缓存（如Redis）存储短链接映射。-使用负载均衡分发请求。解析：-哈希算法或自增ID生成短码，关联表存储映射关系。分布式缓存提升查询性能。负载均衡处理高并发请求。3.题目：请设计一个简单的在线投票系统，支持投票和查看投票结果，假设每次投票后结果需实时更新。答案：-数据存储：-`votes`表（`id`,`user_id`,`option_id`,`timestamp`）-`options`表（`id`,`question`,`count`）-投票逻辑：-用户投票时，插入`votes`表，并更新`options`