软件工程师面试考核点与参考答案

2026年软件工程师面试考核点与参考答案一、编程基础与数据结构（共5题，总分25分）1.题目（10分）：请实现一个函数，输入一个整数数组，返回该数组中所有子数组（连续）的最大和。要求时间复杂度为O(n)。参考答案：pythondefmax_subarray_sum(nums):ifnotnums:return0max_sum=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.题目（5分）：请解释什么是“平衡二叉树”，并给出判断一个二叉树是否为平衡二叉树的算法。参考答案：平衡二叉树是指任一节点的两棵子树的高度差不超过1。判断方法：pythondefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：通过递归计算左右子树高度，并判断高度差是否满足平衡条件。若子树不平衡，则整棵树不平衡。时间复杂度为O(n)，空间复杂度为O(h)（h为树高）。3.题目（5分）：请实现一个LRU（LeastRecentlyUsed）缓存，支持get和put操作。参考答案：使用双向链表+哈希表实现：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key):ifkeyinself.cache:node=self.cache[key]self._move_to_head(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:iflen(self.cache)==self.capacity:self._remove_tail()new_node=Node(key,value)self.cache[key]=new_nodeself._add_to_head(new_node)解析：get操作将节点移动到头部，put操作新建节点或更新节点并移动到头部，若超出容量则删除尾部节点。时间复杂度为O(1)。4.题目（3分）：请解释快速排序的核心思想，并说明其时间复杂度。参考答案：快速排序核心思想：选择一个“pivot”，将数组分为两部分，左部分小于pivot，右部分大于pivot，然后递归对左右部分排序。平均时间复杂度为O(nlogn)，最坏为O(n²)。5.题目（2分）：请解释哈希表的冲突解决方法有哪些？参考答案：开放寻址法（线性探测、二次探测）、链地址法、双重哈希法。链地址法在分布式缓存场景中更常用。二、算法与设计（共4题，总分20分）1.题目（5分）：请设计一个算法，找出无重复数字数组中第k个最大的元素。参考答案：使用快速选择算法（Quickselect）：pythondeffind_kth_largest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=leftpivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,len(nums)-k)解析：Quickselect是QuickSort的变种，通过随机选择pivot减少最坏情况概率，平均时间复杂度为O(n)。2.题目（5分）：请设计一个算法，实现“合并区间”功能。输入：[[1,3],[2,6],[8,10],[15,18]]，输出：[[1,6],[8,10],[15,18]]。参考答案：pythondefmerge_intervals(intervals):ifnotintervals:return[]intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:last[1]=max(last[1],current[1])else:merged.append(current)returnmerged解析：按区间起点排序，然后遍历合并重叠区间。时间复杂度为O(nlogn)。3.题目（5分）：请设计一个算法，实现“LRU缓存”的get和put操作（可参考第一题答案）。参考答案：见第一题LRUCache实现。4.题目（5分）：请设计一个算法，判断一个字符串是否是另一个字符串的子串（不区分大小写）。参考答案：KMP算法：pythondefkmp_search(text,pattern):defcompute_lps(pattern):lps=[0]len(pattern)length=0i=1whilei<len(pattern):ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlpstext=text.lower()pattern=pattern.lower()lps=compute_lps(pattern)i=j=0whilei<len(text):ifpattern[j]==text[i]:i+=1j+=1ifj==len(pattern):returnTrueelifi<len(text)andpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1returnFalse解析：KMP通过预处理pattern生成最长前缀后缀数组（lps），避免重复比较。时间复杂度为O(n)。三、系统设计（共3题，总分15分）1.题目（5分）：请设计一个简单的微博系统，支持用户发布、关注、查看时间线功能。参考答案：-数据库设计：-Users（id,username,email）-Tweets（id,user_id,content,timestamp）-Follows（follower_id,followee_id）-API设计：plaintextPOST/tweets:发布微博POST/follows:关注用户GET/timeline:获取时间线（按时间倒序，含关注用户和自己的微博）解析：时间线查询可通过联合查询Tweets和Follows实现，考虑分页和缓存优化。2.题目（5分）：请设计一个短链接生成系统（如tinyurl），支持用户输入长链接生成短链接，并跳转回原链接。参考答案：-哈希算法：Base62编码（a-z,A-Z,0-9）-数据存储：Redis（hash结构存储短链接→长链接映射）-生成逻辑：pythondefencode_base62(num):chars="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"encoded=""whilenum:num,remainder=divmod(num,62)encoded=chars[remainder]+encodedreturnencodedor"/"解析：使用62进制压缩ID，Redis缓存减少数据库查询。3.题目（5分）：请设计一个高并发计数器，支持分布式部署。参考答案：-方案1：RedisINCR命令-方案2：分布式锁+数据库自增-方案3：基于Raft协议的分布式计数器解析：RedisINCR是最高效方案，但需考虑Redis单点问题。Raft协议可保证强一致性但复杂。四、数据库与缓存（共3题，总分10分）1.题目（3分）：请解释数据库事务的ACID特性及其含义。参考答案：-Atomicity（原子性）：事务不可分割-Consistency（一致性）：事务结束时数据库状态一致-Isolation（隔离性）：并发事务互不干扰-Durability（持久性）：事务提交后结果永久保存2.题目（3分）：请解释缓存穿透、缓存击穿和缓存雪崩的解决方案。参考答案：-缓存穿透：布隆过滤器或空值缓存-缓存击穿：热点数据永不过期或设置高优先级-缓存雪崩：使用随机过期时间、分布式缓存3.题目（4分）：请解释SQL索引的类型及其适用场景。参考答案：-B-Tree索引：范围查询（如订单金额>1000）-Hash索引：精确查询（如用户ID=123）-GIN索引：全文检索（如文章内容）-BRIN索引：稀疏数据（如分页查询）五、系统与网络（共3题，总分10分）1.题目（3分）：请解释TCP三次握手和四次挥手的过程。参考答案：-握手：SYN→SYN+ACK→ACK-拒手：FIN→ACK→FIN→ACK2.题目（3分）：请解释HTTP/2与HTTP/1.1的主要区别。参考答案：-HTTP/2：多路复用、头部压缩、服务器推送-HTTP/1.1：长连接、管道化（但存在队头阻塞）3.题目（4分）：请解释负载均衡的常见算法及其适用场景。参考答案：-轮询：均匀分配（适用于无状态服务）-最