2026年高级软件工程师招聘面试题及答案

2026年高级软件工程师招聘面试题及答案一、编程实现题（共3题，每题20分）1.编程实现一个简单的LRU（最近最少使用）缓存机制（15分）+时间复杂度分析（5分）题目描述：设计一个LRU缓存机制，支持get和put操作。缓存容量为固定值`capacity`。当访问一个键时，如果键存在，返回其值，并将该键移动到缓存的最前面（表示最近使用过）；如果键不存在，返回-1。当插入一个新键值对时，如果缓存已满，需要删除最久未使用（LRU）的键值对，以腾出空间。要求：-使用Python或Java实现。-时间复杂度要求为O(1)的get和put操作。-可使用哈希表和双向链表结合的方式实现。参考答案（Python）：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node:'Node')->None:delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node:'Node')->None:node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head时间复杂度分析：-`get`操作：哈希表O(1)查找，双向链表O(1)删除和添加。-`put`操作：哈希表O(1)查找和删除，双向链表O(1)添加和删除。-整体满足LRU的时间复杂度要求。2.实现一个二叉树的最大深度（最大高度）计算函数（15分）+边界情况讨论（5分）题目描述：给定一个二叉树，计算其最大深度（即从根节点到最远叶子节点的最长路径上的节点数）。假设树的节点定义如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right要求：-使用递归或迭代方式实现。-处理空树、单节点树、完全不平衡树等边界情况。参考答案（Python递归）：pythondefmaxDepth(root:TreeNode)->int:ifnotroot:return0left_depth=maxDepth(root.left)right_depth=maxDepth(root.right)return1+max(left_depth,right_depth)边界情况讨论：1.空树：返回0，因为不存在节点。2.单节点树：返回1，因为深度为1。3.完全不平衡树（左深或右深）：递归计算左右子树的最大深度，最终加1。4.完全平衡树：同样递归计算左右子树，最终加1。3.编写一个函数，将32位无符号整数的二进制表示翻转（10分）+空间复杂度分析（10分）题目描述：给定一个32位无符号整数`n`，返回其二进制表示翻转后的整数。假设二进制表示用32位补码表示，翻转后超出32位的部分需要丢弃。示例：-输入：`n=43261596`，二进制表示为`000000000000000000000000100001110010110100000000000`，翻转后为`00000000000000000000000100011110100101110000000000000000`，即`964176192`。要求：-不能使用内置函数。-时间复杂度要求为O(1)。参考答案（Python）：pythondefreverse_bits(n:int)->int:result=0for_inrange(32):result=(result<<1)|(n&1)n>>=1returnresult&0xFFFFFFFF空间复杂度分析：-算法仅使用常数个额外变量（`result`、`n`和循环计数器），因此空间复杂度为O(1)。二、系统设计题（共2题，每题25分）4.设计一个短链接（TinyURL）系统（25分）题目描述：实现一个短链接系统，将长URL转换为短URL，并支持从短URL还原为长URL。假设系统需要支持以下功能：1.生成短URL：输入长URL，返回一个唯一的短URL（如`/abc123`）。2.还原长URL：输入短URL，返回对应的长URL。3.高并发处理：系统需支持高并发访问，响应时间在毫秒级。4.分布式扩展：支持水平扩展，便于应对流量增长。要求：-短URL生成规则：可使用随机字符串或哈希算法（如Base62编码）。-高可用和一致性：使用分布式缓存或数据库存储映射关系。-处理重复短URL生成的情况。参考答案：系统架构：1.短URL生成：-使用Base62编码（`a-z`、`A-Z`、`0-9`）将ID映射为6位短码（62^6=56.8亿种组合）。-生成ID可通过自增序列+哈希碰撞处理（如布隆过滤器）。-示例：长URL`/long-path`→ID`12345`→Base62编码`abc123`→短URL`/abc123`。2.短URL还原：-解析短URL中的6位码，通过Base62解码获取ID。-查询分布式缓存（如RedisCluster）或数据库获取长URL。3.高并发与分布式：-使用RedisCluster或分布式数据库（如Cassandra）存储映射关系，支持分片和负载均衡。-短URL生成时，使用分布式锁或CAS算法避免ID冲突。伪代码示例：pythondefencode_base62(num:int)->str:digits="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"ifnum==0:returndigits[0]result=[]whilenum>0:result.append(digits[num%62])num//=62return''.join(reversed(result))defdecode_base62(s:str)->int:digits="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"result=0forcharins:result=result62+digits.index(char)returnresultdefgenerate_tinyurl(long_url:str)->str:使用分布式ID生成器（如Snowflake算法）获取唯一IDid=get_next_id()short_code=encode_base62(id)store_mapping(id,long_url)#存储到RedisClusterreturnf"/{short_code}"defget_longurl(short_url:str)->str:short_code=short_url.split('/')[-1]id=decode_base62(short_code)returnretrieve_mapping(id)#从RedisCluster查询5.设计一个高并发的秒杀系统（25分）题目描述：设计一个秒杀系统，要求支持高并发访问（每秒上万QPS），并满足以下要求：1.库存扣减：限制商品库存数量，防止超卖。2.防止刷单：验证用户身份，限制每个用户购买次数。3.高可用性：系统需支持分布式部署，故障隔离。4.一致性：确保库存扣减和订单生成的原子性。要求：-描述系统架构、关键模块设计、数据存储方案及防作弊策略。参考答案：系统架构：1.流量分发层（Nginx/ALB）：负载均衡，防止单点过载。2.秒杀业务层（微服务）：-使用RedisCluster或分布式锁实现库存扣减的原子性。-用户验证（登录态或临时令牌）。3.订单服务：异步写入数据库，使用消息队列（如Kafka）解耦。4.数据存储：-库存：RedisCluster（高并发读写）+分布式锁。-订单：关系型数据库（如PostgreSQL）+事务保证一致性。关键模块设计：-库存预减：-用户请求时，先通过Redis扣减库存（使用SETNX或Lua脚本保证原子性）。-扣减成功后，生成订单；失败则返回库存不足。lua--RedisLua脚本示例ifredis.call('setnx',KEYS[1],ARGV[1])==1thenreturn1elseiftonumber(redis.call('get',KEYS[1]))>=tonumber(ARGV[1])thenredis.call('decrby',KEYS[1],ARGV[1])return1elsereturn0end-用户验证：-登录用户使用Token验证；未登录用户使用手机号+验证码。-使用Redis存储用户购买次数限制（如`user:buy:count`）。-订单异步处理：-使用Kafka或RabbitMQ传输订单数据到订单服务。-订单服务批量写入数据库，提高写入性能。防作弊策略：1.验证码：防止机器人快速请求。2.IP限制：限制同一IP短时间内的请求次数。3.分布式锁：避免超卖（如RedisRedlock算法）。三、算法与数据结构题（共2题，每题15分）6.给定一个字符串，判断是否可以通过重新排列字符，使其变为回文串（15分）题目描述：判断一个字符串是否可以重新排列成回文串。回文串是指正读和反读都相同的字符串。示例：-输入：`"aab"`，输出：`True`（可排列为`aba`）。-输入：`"carerac"`，输出：`True`（本身就是回文）。要求：-时间复杂度O(n)，空间复杂度O(1)。参考答案：pythondefcan_form_palindrome(s:str)->bool:counts=[0]256#假设字符集为ASCIIforcharins:counts[ord(char)]+=1odd_count=0forcountincounts:ifcount%2!=0:odd_count+=1ifodd_count>1:returnFalsereturnTrue解析：-回文串最多只有一个字符出现奇数次（如"aba"中'a'出现奇数次）。-遍历字符串统计字符频率，统计奇数频率的字符数量。7.实现一个LRU缓存的高效实现（双向链表+哈希表）（15分）题目描述：实现一个LRU缓存，要求：1.支持get和put操作，时间复杂度O(1)。2.使用双向链表和哈希表结合的方式实现。要求：-详细说明数据结构设计，并给出关键操作（get、put）的伪代码。参考答案：数据结构：-双向链表：-头节点`head`和尾节点`tail`（哑节点）。-节点包含`key`、`value`、`prev`、`next`。-哈希表：-键为`key`，值为链表节点（`{key:node}`）。伪代码：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._remove(node)self._add(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node:'Node')->None:delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node:'Node')->None:node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：-`get`操作：哈希表O(1)查找，双向链表O(1)删除和添加。-`put`操作：哈希表O(1)查找和删除，双向链表O(1)添加和删除。四、数据库与存储题（共1题，15分）8.设计一个微博点赞系统（15分）题目描述：设计一个微博点赞系统，支持以下功能：1.用户可以给微博点赞或取消点赞。2.实时统计微博的点赞数。3.支持按时间倒序查询微博及点赞记录。要求：-关系型数据库设计（如PostgreSQL），给出表结构设计及SQL示例。-非关系型数据库（如Redis）优化方案。参考答案：关系型数据库设计：1.微博表（weibo）：sqlCREATETA