软件开发工程师面试高频题及答案

2026年软件开发工程师面试高频题及答案一、编程基础与数据结构（5题，每题8分，共40分）1.题目：请实现一个函数，输入一个非负整数`n`，返回其二进制表示中包含的`1`的个数。例如：`n=9`（二进制`1001`），返回`2`。答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount解析：使用位运算高效统计`1`的个数。`n&1`判断最低位是否为`1`，`n>>=1`将数字右移一位。时间复杂度为O(logn)。2.题目：给定一个排序数组，实现二分查找，返回目标值`target`的索引。如果不存在，返回`-1`。答案：pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1解析：二分查找的核心是不断缩小查找范围。时间复杂度为O(logn)。注意`left<=right`避免死循环。3.题目：请实现一个函数，检查一个字符串是否是有效的括号组合，例如：`"()"`、`"()[]{}"`有效，`"(]"`无效。答案：pythondefisValid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：使用栈匹配括号。遍历字符串，遇到右括号时检查栈顶是否匹配。时间复杂度O(n)。4.题目：请实现快速排序算法，并分析其时间复杂度。答案：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²)（选择枢轴不当）。5.题目：实现一个函数，判断一个链表是否包含环。答案：pythondefhasCycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse解析：快慢指针法。慢指针每次移动一步，快指针每次移动两步，相遇则存在环。时间复杂度O(n)。二、算法与设计（5题，每题10分，共50分）6.题目：设计一个LRU（最近最少使用）缓存，支持`get`和`put`操作。答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.order=[]defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):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)解析：使用哈希表记录缓存，双向链表维护访问顺序。`get`时移动元素到尾部，`put`时先删除最久未使用项。7.题目：实现一个函数，将一个非递归的二叉树转换成深度为1的链表（右倾树）。答案：pythondefflatten(root):current=rootwhilecurrent:ifcurrent.left:predecessor=current.leftwhilepredecessor.right:predecessor=predecessor.rightpredecessor.right=current.rightcurrent.right=current.leftcurrent.left=Nonecurrent=current.right解析：利用右指针连接右子树和左子树的右most节点。时间复杂度O(n)。8.题目：设计一个算法，找出数组中第三大的数。如果数组不足三个数，返回最大数。答案：pythondefthirdMax(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst解析：维护三个变量记录前三大的数。遍历数组时更新变量。时间复杂度O(n)。9.题目：实现一个函数，判断一个单词是否是另一个字符串的子序列。例如：`s="abc"`，`t="ahbgdc"`，返回`True`。答案：pythondefisSubsequence(s,t):p,q=0,0whilep<len(s)andq<len(t):ifs[p]==t[q]:p+=1q+=1returnp==len(s)解析：双指针法。逐个匹配`s`和`t`，若`s`全部匹配则返回`True`。时间复杂度O(n)。10.题目：设计一个算法，统计一个字符串中所有唯一字符的异或结果。例如：`s="abcabc"`，唯一字符为`a`、`b`、`c`，异或结果为`a^b^c`。答案：pythondefunique_xor(s):unique_chars=set(s)result=0forcharinunique_chars:result^=ord(char)returnresult解析：异或满足交换律和结合律，因此可直接对唯一字符的ASCII码进行异或。时间复杂度O(n)。三、系统设计与数据库（5题，每题12分，共60分）11.题目：设计一个微博系统，要求支持实时发布、关注/取消关注、获取关注者动态。答案：-数据模型：-`User`：`id`、`name`、`follows`（关注列表）、`followers`（粉丝列表）-`Tweet`：`id`、`user_id`、`content`、`timestamp`-核心接口：-`publishTweet(user_id,content)`：发布微博-`follow(from_user_id,to_user_id)`：关注用户-`getFeed(user_id)`：获取关注者动态（分页+时间排序）-技术选型：-数据库：MySQL（关系型存储）+Redis（缓存关注列表）-消息队列：Kafka（实时推送）解析：关注关系用双向哈希表存储，动态用时间戳排序。高并发场景下需考虑消息队列和缓存优化。12.题目：设计一个短链接系统（如`tinyurl`），要求支持长链接转短链接、短链接解析。答案：-算法：-使用Base62编码（a-z,A-Z,0-9），如`1000`编码为`1L`-数据模型：-`ShortLink`：`id`（自增）、`long_url`、`short_code`、`timestamp`-接口：-`createShortLink(long_url)`：生成短链接-`getLongLink(short_code)`：解析短链接-技术选型：-磁盘+内存缓存（Redis）加速短链接查询解析：短链接需唯一且长度短。Base62转换减少位数，哈希表存储映射关系。13.题目：设计一个高并发的秒杀系统，要求支持限流、去重、订单生成。答案：-限流：-令牌桶算法（固定时间窗口内放行固定数量请求）-去重：-Redis记录用户请求时间戳（过期删除）-数据模型：-`Product`：`id`、`stock`-`Order`：`id`、`user_id`、`product_id`、`timestamp`-流程：-用户请求→检查库存→Redis去重→生成订单→库存扣减解析：秒杀核心是高并发控制。分布式锁（Redis）和数据库事务保证原子性。14.题目：设计一个新闻推荐系统，要求根据用户历史行为推荐新闻。答案：-数据模型：-`User`：`id`、`profile`（兴趣标签）-`Article`：`id`、`category`、`tags`-`Behavior`：`user_id`、`article_id`、`action`（点击、点赞）-推荐算法：-协同过滤（基于用户或物品）-算法：User-basedCF或Item-basedCF-技术选型：-Elasticsearch（索引新闻）-SparkMLlib（离线推荐）-Redis（实时推荐缓存）解析：推荐系统需结合离线与实时计算。冷启动问题可使用热门推荐。15.题目：设计一个分布式数