软件工程师面试题及高分技巧

2026年软件工程师面试题及高分技巧一、编程实现题（共5题，每题10分，总分50分）题目1（10分）：实现一个LRU缓存机制要求：-使用Python或Java实现LRU（LeastRecentlyUsed）缓存，支持get和put操作-get操作返回键对应的值，同时将该键标记为最近使用-put操作插入或更新键值对，如果缓存已满，则移除最久未使用的元素-不使用任何现成的缓存库，需要自己实现数据结构参考思路：可以使用双向链表结合哈希表实现。哈希表存储键到节点的映射，双向链表维护访问顺序，头节点为最近访问，尾节点为最久未访问。题目2（10分）：实现一个简单的文件压缩算法要求：-编写一个函数，接受两个参数：源文件路径和目标压缩文件路径-实现一个简单的字典压缩算法（如LZ77的简化版）-输出压缩后的文件大小与原始文件大小的比率-需要考虑文件读取、写入和内存使用效率参考思路：可以维护一个动态字典，记录最近出现过的字符串。读取源文件时，查找字典中是否存在当前字符串，如果存在则记录索引和后续字符，否则将新字符串加入字典。题目3（10分）：实现一个分布式锁服务要求：-使用Redis实现分布式锁，支持锁的获取和释放-锁需要支持超时机制，防止死锁-实现一个简单的分布式锁客户端，演示锁的使用-考虑多个客户端竞争同一锁的情况参考思路：可以使用Redis的SET命令加锁，使用EXPIRE设置超时。为了防止多个客户端获取到同一个锁，可以使用UUID作为唯一标识。释放锁时需要验证锁的持有者。题目4（10分）：实现一个简单的消息队列要求：-使用Python实现一个基于内存的消息队列，支持生产者和消费者-消息队列需要支持阻塞式获取消息-需要考虑线程安全，支持多线程环境-实现一个简单的生产者-消费者示例参考思路：可以使用条件变量实现阻塞队列。生产者生产消息时，如果队列已满则阻塞；消费者获取消息时，如果队列为空则阻塞。使用锁保证线程安全。题目5（10分）：实现一个简单的JWT生成和验证工具要求：-使用Python编写JWT的生成和验证函数-JWT需要包含用户ID和角色信息-需要支持签名验证-考虑时间戳和过期时间参考思路：JWT通常由三部分组成：Header、Payload和Signature。Header包含算法类型；Payload包含用户信息和过期时间等；Signature使用Header中的算法和密钥签名Payload。验证时需要检查签名和时间戳。二、系统设计题（共3题，每题20分，总分60分）题目6（20分）：设计一个高并发的短链接服务背景：需要设计一个类似tinyURL的短链接服务，支持高并发访问，要求响应速度快，链接持久有效。要求：-描述系统架构，包括主要组件-说明短链接生成算法-考虑分布式部署和负载均衡-分析可能的性能瓶颈和解决方案参考思路：系统可以分为API网关、短链接生成服务、存储服务和反向代理。短链接生成可以使用Base62编码。为了支持高并发，可以使用缓存层和分布式存储。需要考虑链路追踪和监控。题目7（20分）：设计一个实时消息推送系统背景：需要设计一个支持百万级用户的实时消息推送系统，支持订阅、发布和消息存储。要求：-描述系统架构，包括主要组件-说明消息传递机制-考虑消息的可靠性和去重-分析可能的扩展方案参考思路：系统可以分为消息中心、存储系统和客户端。消息中心负责消息的路由和分发。可以使用发布订阅模式，支持持久化队列。需要考虑消息的幂等性和重试机制。题目8（20分）：设计一个分布式任务调度系统背景：需要设计一个支持全局定时任务的分布式调度系统，支持任务分片、失败重试和资源隔离。要求：-描述系统架构，包括主要组件-说明任务调度算法-考虑任务失败处理和资源分配-分析可能的扩展方案参考思路：系统可以分为调度中心、执行器和监控组件。调度中心负责任务分配和状态跟踪。可以使用一致性哈希分配任务。需要考虑任务的优先级和依赖关系。三、算法与数据结构题（共4题，每题15分，总分60分）题目9（15分）：字符串匹配算法要求：-实现KMP字符串匹配算法-给定文本串和模式串，返回所有匹配的位置-分析算法的时间复杂度参考思路：KMP算法通过构建部分匹配表（PartialMatchTable）避免无效回溯。算法时间复杂度为O(n+m)。题目10（15分）：图算法要求：-实现Dijkstra最短路径算法-给定带权无向图和起点，返回到所有点的最短路径-考虑使用优先队列优化参考思路：可以使用贪心算法，每次选择距离起点最近的未访问节点。使用优先队列可以优化为O((E+V)logV)。题目11（15分）：动态规划要求：-实现最长递增子序列（LIS）算法-给定数组，返回长度最长的递增子序列-分析算法的时间复杂度参考思路：可以使用二分查找优化为O(nlogn)的解法。也可以使用O(n^2)的简单动态规划解法。题目12（15分）：数据结构设计要求：-设计一个支持动态调整大小的数组（类似ArrayList）-描述关键方法的实现逻辑-考虑扩容策略和内存优化参考思路：可以使用固定大小数组，当达到容量时进行倍数扩容。需要考虑扩容时的元素复制和缩容策略。答案与解析编程实现题答案与解析题目1：实现一个LRU缓存机制Python实现：pythonclassNode:def__init__(self,key=None,value=None):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):Alwaysaddthenewnoderightafterhead.node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):Removeanexistingnodefromthelinkedlist.prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):Movecertainnodeinbetweentothehead.self._remove_node(node)self._add_node(node)def_pop_tail(self):Popthecurrenttail.res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1Movetheaccessednodetothehead;self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:Popthetailtail=self._pop_tail()delself.cache[tail.key]else:Updatethevalue.node.value=valueself._move_to_head(node)解析：-使用双向链表维护访问顺序，头为最近访问，尾为最久未访问-哈希表实现O(1)时间复杂度的get和put操作-当缓存容量超出限制时，移除链表尾部节点-get操作时将访问节点移动到链表头部题目2：实现一个简单的文件压缩算法Python实现：pythondefsimple_compression(source_path,target_path):withopen(source_path,'rb')asf:data=f.read()dictionary={}dict_size=256foriinrange(256):dictionary[bytes([i])]=icompressed=[]current_code=0mask=1<<9#512max_code=mask-1current_bytes=[data[0]]foriinrange(1,len(data)):current_bytes.append(data[i])iftuple(current_bytes)indictionary:continueelse:compressed.append(current_code)iflen(dictionary)<max_code:dictionary[tuple(current_bytes)]=dict_sizedict_size+=1current_code=0current_bytes=[data[i]]ifcurrent_code!=0:compressed.append(current_code)withopen(target_path,'wb')asf:Writedictionarysizef.write(int.to_bytes(dict_size,4,'big'))Writecompresseddataforcodeincompressed:f.write(int.to_bytes(code,6,'big'))#Using6bytesforcodesreturnlen(compressed)6+4,len(data)解析：-实现了一个简化版的LZ77算法-建立动态字典，记录出现过的字符串序列-使用位掩码存储压缩代码-需要考虑字典大小限制和代码长度题目3：实现一个分布式锁服务Python实现（使用Redis）：pythonimportredisimportuuidimporttimeclassDistributedLock:def__init__(self,redis_host='localhost',redis_port=6379):self.redis=redis.Redis(host=redis_host,port=redis_port)defacquire(self,lock_id,timeout=10):unique_id=str(uuid.uuid4())end_time=time.time()+timeoutwhiletime.time()<end_time:ifself.redis.set(lock_id,unique_id,ex=timeout,nx=True):returnunique_idtime.sleep(0.001)returnNonedefrelease(self,lock_id,unique_id):withself.redis.pipeline()aspipe:whileTrue:try:pipe.watch(lock_id)ifpipe.get(lock_id)==unique_id.encode():pipe.multi()pipe.delete(lock_id)pipe.execute()returnTruepipe.unwatch()breakexceptredis.WatchError:passreturnFalse解析：-使用Redis的SET命令加锁，EXPIRE设置超时-使用UUID防止多个客户端获取同一个锁-释放锁时验证UUID确保是锁的持有者-考虑了Redis主从复制场景下的锁问题题目4：实现一个简单的消息队列Python实现（使用threading）：pythonimportthreadingimportcollectionsimporttimeclassMessageQueue:def__init__(self):self.queue=collections.deque()self.lock=threading.Lock()self.not_empty=threading.Condition(self.lock)self.not_full=threading.Condition(self.lock)defput(self,message):withself.not_full:whilelen(self.queue)>=100:#Assumemaxcapacityis100self.not_full.wait()self.queue.append(message)self.not_empty.notify()defget(self):withself.not_empty:whilenotself.queue:self.not_empty.wait()message=self.queue.popleft()self.not_full.notify()returnmessageExampleusagedefproducer(queue):foriinrange(1000):queue.put(f"message{i}")time.sleep(0.01)defconsumer(queue):whileTrue:message=queue.get()print(f"Received:{message}")time.sleep(0.05)if__name__=="__main__":queue=MessageQueue()p=threading.Thread(target=producer,args=(queue,))c=threading.Thread(target=consumer,args=(queue,))p.start()c.start()解析：-使用条件变量实现阻塞队列-生产者生产时如果队列满则阻塞-消费者获取时如果队列为空则阻塞-使用锁保证线程安全题目5：实现一个简单的JWT生成和验证工具Python实现（使用jwt库）：pythonimportjwtimportdatetimeclassJWTUtil:def__init__(self,secret_key='mysecret'):self.secret_key=secret_keydefgenerate(self,user_id,roles,expires_in=3600):payload={'sub':user_id,'roles':roles,'iat':datetime.datetime.utcnow(),'exp':datetime.datetime.utcnow()+datetime.timedelta(seconds=expires_in)}returnjwt.encode(payload,self.secret_key,algorithm='HS256')defverify(self,token):try:payload=jwt.decode(token,self.secret_key,algorithms=['HS256'])return{'user_id':payload['sub'],'roles':payload['roles']}exceptjwt.ExpiredSignatureError:returnNoneexceptjwt.InvalidTokenError:returnNoneExampleusagejwt_util=JWTUtil()token=jwt_util.generate(1,['user'])print(f"Generatedtoken:{token}")payload=jwt_util.verify(token)print(f"Verificationresult:{payload}")解析：-JWT包含Header、Payload和Signature三部分-Payload包含用户信息和过期时间等-使用HS256算法进行签名-验证时检查签名和过期时间系统设计题答案与解析题目6：设计一个高并发的短链接服务系统架构：1.API网关：接收所有请求，进行身份验证和限流2.短链接生成服务：负责生成短链接，支持分布式部署3.存储服务：存储原始链接和短链接映射，使用Redis或Memcached4.反向代理：缓存热点链接，加速访问短链接生成算法：-使用Base62编码（a-z,A-Z,0-9）-哈希算法：MD5或SHA256-取哈希值的前6位作为短链接部分分布式部署和负载均衡：-使用一致性哈希分配短链接生成任务-API网关使用Nginx或HAProxy进行负载均衡-存储服务使用Redis集群性能瓶颈和解决方案：-链接生成速度：使用缓存和预生成技术-数据库查询：使用Redis缓存热点链接-并发请求：使用限流和熔断机制题目7：设计一个实时消息推送系统系统架构：1.消息中心：接收发布请求，路由消息2.存储系统：持久化消息，支持回滚3.客户端：订阅消息，接收推送消息传递机制：-使用发布订阅模式-支持单播、群播和广播-使用WebSocket或MQTT协议可靠性和去重：-消息ID唯一-使用幂等性保证消息不重复处理-持久化未确认消息扩展方案：-水平扩展消息中心-使用分布式队列处理高并发-支持消息分片和异步处理题目8：设计一个分布式任务调度系统系统架构：1.调度中心：管理任务和执行器2.执行器：执行具体任务3.监控组件：跟踪任务状态和性能任务调度算法：-使用Cron表达式定义定时任务-支持依赖关系和分片执行-使用优先级队列处理任务任务失败处理和资源分配：-任务失败自动重试-使用资源标签进行隔离-使用限流防止资源耗尽扩展方案：-水平扩展调度中心-使用任务集群提高执行能力-支持任务热加载和动态调整算法与数据结构题答案与解析题目9：字符串匹配算法KMP算法实现：pythondefkmp_search(text,pattern):Buildprefixtableprefix=[0]len(pattern)j=0foriinrange(1,len(pattern)):whilej>0andpattern[i]!=pattern[j]:j=prefix[j-1]ifpattern[i]==pattern[j]:j+=1prefix[i]=jSearchpatternintextmatches=[]j=0foriinrange(len(text)):whilej>0andtext[i]!=pattern[j]:j=prefix[j-1]iftext[i]==pattern[j]:j+=1ifj==len(pattern):matches.append(i-(j-1))j=prefix[j-1]returnmatchesExampletext="ABABDABACDABABCABAB"pattern="ABABCABAB"print(kmp_search(text,pattern))#Output:[10]时间复杂度：-构建前缀表：O(m)-搜索文本：O(n)-总时间复杂度：O(n+m)解析：-KMP算法通过构建部分匹配表避免无效回溯-当不匹配时，根据前缀表确定下一个比较位置-适用于长文本中搜索多个模式的情况题目10：图算法Dijkstra算法实现：pythonimportheapqdefdijkstra(graph,start):distances={vertex:float('infinity')forvertexingraph}distances[start]=0priority_queue=[(0,start)]whilepriority_queue:current_distance,current_vertex=heapq.heappop(priority_queue)ifcurrent_distance>distances[current_vertex]:continueforneighbor,weightingraph[current_vertex].items():distance=current_distance+weightifdistance<distances[neighbor]:distances[neighbor]=distanceheapq.heappush(priority_queue,(distance,neighbor))returndistancesExamplegraph={'A':{'B':1,'C':4},'B':{'A':1,'C':2,'D':5},'C':{'A':4,'B':2,'D':1},'D':{'B':5,'C':1}}print(dijkstra(graph,'A'))#Output:{'A':0,'B':1,'C':3,'D':4}时间复杂度：-使用优先队列优化为O((E+V)logV)-E是边数，V是顶点数解析：-Dijkstra算法使用贪心策略，每次选择距离起点最近的未访问节点-使用优先队列（最小堆）优化选择过程-适用于求单源最短路径问题题目11：动态规划LIS算法实现：pythondeflength_of_LIS(nums):ifnotnums:return0tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)Examplenums=[10,9,2,5,3,7,101,18]print(length_of_LIS(nums))#Output:4时间复杂度：-使用二分查找优化为O(nlogn)解析：-LIS问题可以使用贪心+二分查找解决-维护一个tails数组，存储当前最长的递增子序列的末尾元素-对于每个元素，找到tails中第一个大于等于当前元素的位置-如果找不到则扩展LIS，否则替换现有元素题目12：数据结构设计动态数组实现：pythonclassDynamicArray:def__init__(self,initial_capacity=10):self._size=0self._capacity