工程师面试题目与解决方案

2026年工程师面试题目与解决方案一、编程语言与数据结构（10题，每题10分，共100分）1.题目：请实现一个函数，输入一个非负整数，返回它的二进制表达式中1的个数。例如，输入`123`，输出`6`（因为`123`的二进制表示为`1111011`，有6个1）。答案与解析：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount解析：-使用位运算`n&1`获取最低位是否为1，然后右移一位，重复直到`n`为0。-时间复杂度O(logn)，空间复杂度O(1)。2.题目：给定一个链表，判断链表是否存在环。如果存在，返回环的入口节点；否则返回`None`。答案与解析：pythonclassListNode:def__init__(self,x):self.val=xself.next=Nonedefdetect_cycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：-使用快慢指针，相遇则存在环，继续移动直到找到入口节点。-时间复杂度O(n)，空间复杂度O(1)。3.题目：请实现一个无重复字符的最长子串，返回其长度。例如，输入`s="abcabcbb"`，输出`3`（因为"abc"是最长的无重复字符子串）。答案与解析：pythondeflength_of_longest_substring(s):char_map={}left=max_len=0forright,charinenumerate(s):ifcharinchar_mapandchar_map[char]>=left:left=char_map[char]+1char_map[char]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：-使用滑动窗口，`char_map`记录字符上一次出现的位置，避免重复。-时间复杂度O(n)，空间复杂度O(min(m,n))，m为字符集大小。4.题目：给定一个二维数组`matrix`，返回所有“之”字形路径的总和。例如：[[1,2,3],[4,5,6],[7,8,9]]输出`1+2+4+7`或`3+2+5+8`等。答案与解析：pythondefz_shape_path(matrix):ifnotmatrixornotmatrix[0]:return0rows,cols=len(matrix),len(matrix[0])result=0foriinrange(rows):forjinrange(cols):ifi+j<rows:result+=matrix[i][j]returnresult解析：-只考虑从左上到右下的对角线（即`i+j`相同的元素）。-时间复杂度O(mn)，空间复杂度O(1)。5.题目：请实现一个LRU（最近最少使用）缓存，支持`get`和`put`操作。例如：pythonLRUCachecache=newLRUCache(2)cache.put(1,1)//缓存是{1=1}cache.put(2,2)//缓存是{1=1,2=2}cache.get(1)//返回1cache.put(3,3)//去除键2，缓存是{1=1,3=3}cache.get(2)//返回-1(未找到)答案与解析：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:node=self._pop_tail()delself.cache[node.key]def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev,next=node.prev,node.nextprev.next=nextnext.prev=prevdef_pop_tail(self):node=self.tail.prevself._remove_node(node)returnnode解析：-使用双向链表和哈希表实现，链表头为最近使用，尾为最久未使用。-`get`操作将节点移动到头部，`put`操作先检查是否已存在，然后调整链表和哈希表。6.题目：请实现一个函数，将一个非递归的链表反转。例如，输入`1->2->3->4->5`，输出`5->4->3->2->1`。答案与解析：pythondefreverse_linked_list(head):prev,current=None,headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：-逐个节点反转指针方向，时间复杂度O(n)，空间复杂度O(1)。7.题目：给定一个数组`nums`，返回所有可能的子集（无重复元素）。例如，输入`[1,2,3]`，输出`[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`。答案与解析：pythondefsubsets(nums):res=[]nums.sort()defbacktrack(start,path):res.append(path.copy())foriinrange(start,len(nums)):path.append(nums[i])backtrack(i+1,path)path.pop()backtrack(0,[])returnres解析：-使用回溯法，递归生成所有子集。-时间复杂度O(2^n)，空间复杂度O(n)。8.题目：请实现一个函数，判断一个字符串是否是回文串，忽略大小写和非字母数字字符。例如，输入`"Aman,aplan,acanal:Panama"`，输出`True`。答案与解析：pythondefis_palindrome(s:str)->bool:left,right=0,len(s)-1whileleft<right:whileleft<rightandnots[left].isalnum():left+=1whileleft<rightandnots[right].isalnum():right-=1ifs[left].lower()!=s[right].lower():returnFalseleft,right=left+1,right-1returnTrue解析：-双指针从两端向中间移动，跳过非字母数字字符，比较是否对称。9.题目：请实现一个函数，将一个字符串转换成整数（atoi）。例如，输入`"-42"`，输出`-42`。答案与解析：pythondefmy_atoi(s:str)->int:s=s.strip()ifnots:return0sign=1i=0ifs[0]=='-':sign=-1i=1elifs[0]=='+':i=1result=0whilei<len(s)ands[i].isdigit():result=result10+int(s[i])ifsign==1andresult>231-1:return231-1ifsign==-1and-result<-231:return-231i+=1returnsignresult解析：-处理空格、符号，然后逐位累加，注意溢出限制。-时间复杂度O(n)，空间复杂度O(1)。10.题目：请实现一个函数，判断一个二叉树是否是平衡二叉树（左右子树高度差不超过1）。答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_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题，每题20分，共60分）1.题目：设计一个短链接系统（如`tinyurl`），要求：-输入长链接，生成短链接；-输入短链接，返回长链接；-支持高并发访问。答案与解析：-核心思路：1.使用哈希函数（如Base62）将长链接映射为短链接（如`/abc123`）；2.使用数据库（如Redis）存储短链接与长链接的映射；3.使用分布式ID生成器（如Snowflake）确保唯一性。-实现步骤：-生成短链接：-对长链接进行MD5哈希，取前6位作为ID；-避免冲突，可使用随机重试或增加位数；-存储到Redis，`key=short_link,value=long_link`。-解析短链接：-从Redis获取长链接，返回给用户。-高并发处理：-使用Redis集群或分片；-前端使用CDN缓存热点短链接。2.题目：设计一个微博系统，要求：-支持用户发布、关注、点赞、评论；-支持分页加载（如首页动态）；-支持搜索功能。答案与解析：-核心思路：1.数据存储：-用户：`User`表（`id,username,follow_list`）；-动态：`Post`表（`id,user_id,content,time`）；-关注关系：`Follow`表（`follower_id,followee_id`）；-点赞：`Like`表（`user_id,post_id`）；-评论：`Comment`表（`id,post_id,user_id,content`）。2.首页动态：-用户关注的人的动态+自己的动态；-使用Redis缓存热门用户动态。3.搜索：-使用Elasticsearch索引动态内容，支持分词搜索。3.题目：设计一个高并发的秒杀系统，要求：-支持高并发请求；-防止超卖；-保证幂等性。答案与解析：-核心思路：1.库存控制：-使用Redis计数器（`SETNX`或`DECR`）；-超卖时，通过补偿机制恢复库存。2.防止重复请求：-使用分布式锁（如RedisLock）；-用户下单时，检查库存并扣减。3.幂等性：-使用订单ID缓存已处理的请求；-每次请求先检查缓存。三、数据库与分布式（3题，每题20分，共60分）1.题目：解释MySQL中的事务隔离级别，并说明为什么不能选择“可重复读”？答案与解析：-隔离级别：1.读未提交（ReadUncommitted）：-可能读到其他事务未提交的数据（脏读）；2.读已提交（ReadCommitted）：-防止脏读，但可能读到不可重复读（如快照读）；3.可重复读（RepeatableRead）：-防止脏读和不可重复读，但可能读到幻读；4.串行化（Serializable）：-完全隔离，但性能最低。-为什么不能选择“可重复读”？-在高并发场景下，会导致大量锁竞争，性能极差；-可通过MVCC（多版本并发控制）优化。2.题目：设计一个分布式缓存架构，要求：-支持高可用；-支持数据一致性；-支持分片。答案与解析：-核心思路：1.高可用：-使用Redis集群或Memcached+Keepalived；-主从复制或哨兵模式。2.数据一致性：-使用发布订阅（如RedisPub/Sub）通知更新；-结合本地缓存+远程缓存策略。3.分片：-使用哈希分区（如`hash(key)%128`）；-使用RedisCluster自动分片。3.题目：解释分布式事务的解决方案（2PC或TCC），并说明其优缺点。答案与解析：-2PC（两阶段提交）：1.阶段1：-询问所有参与者是否可以提交；2.阶段2：-执行提交或回滚。-优点：强一致性；-缺点：无法容错（单点故障导致阻塞）。-TCC（Try-Confirm-Cancel）：-对每个操作定义Try、Confirm、Cancel接口；-优点：弹性高；-缺点：实现复杂。四、网络与系统（4题，每题15分，共60分）1.题目：解释TCP的三次握手和四次挥手过程。答案与解析：-三次握手：1.客户端发送SYN=1，seq=x；2.服务器回复SYN=1,ACK=1,seq=y,ack=x+1；3.客户端回复ACK=1,ack=y+1。-四次挥手：1.客户端发送FIN=1；2.服务器回复ACK=1,ack=x+1；3.服务器发送FIN=1；4.客户端回复ACK=1,ack=y+1。2.题目：为什么HTTPS比HTTP安全？答案与解析：-HTTPS优势：1.加密：TLS/SSL加密传输数据；2.认证：CA证书验证服务器身份；3.完整性：HMAC防止数据篡改。3.题目：解释DNS解析过程。答案与解析：1.客户端向本地DNS发起请求；2.本地DNS检查缓存，未命中则向根DNS请求；3.根DNS返回顶级域DNS地址；4.重复向下一级DNS请求，直到获取IP；5.本地DNS返回IP给客户端。4.题目：解释负载均衡的几种策略（轮询、最少连接、IP哈希）。答案与解析：-轮询：按顺序分配请求；-最少连接：分配到连接数最少的节点；-IP哈希：同一IP始终访问同一节点（会话保持）。五、算法与数据结构（4题，每题15分，共60分）1.题目：给定一个数组，找出其中和最大的连续子数组，返回其和。例如，输入`[-2,1,-3,4,-1,2,1,-5,4]`，输出`6`（子数组`[4,-1,2,1]`）。答案与解析：pythondefmax_subarray(nums):max_current=max_global=nums[0]fornuminnums[1:]:max_current=max(num,max_current+num)max_global=max(max_global,max_current)returnmax_global解析：-动态规划，`max_current`记录当前最大和，`max_global`记录全局最大和。2.题目：给定一个数组，返回其中重复次数超过一半的元素。答案与解析：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：-Boyer-Moore投票算法，时间复杂