2026年互联网公司技术大咖面试题解析

2026年互联网公司技术大咖面试题解析一、编程能力测试（共5题，每题20分，总分100分）考察点：基础编程能力、算法思维、代码质量题目1（20分）：问题描述：给定一个非空字符串`s`，请实现一个函数`repeatedSubstringPattern(s)`，返回`true`如果字符串可以由它自己的一个子串重复多次构成，否则返回`false`。示例：-输入：`"abab"`→输出：`true`（因为可以由`"ab"`重复两次构成）-输入：`"abcabcabc"`→输出：`true`（可以由`"abc"`重复三次构成）-输入：`"a"`→输出：`false`要求：1.不能使用内置库函数。2.时间复杂度优于O(n²)。答案与解析：答案：pythondefrepeatedSubstringPattern(s:str)->bool:n=len(s)foriinrange(1,n//2+1):ifn%i==0:substring=s[:i]ifsubstring(n//i)==s:returnTruereturnFalse解析：1.核心思路：-如果字符串`s`可以由子串重复构成，那么子串的长度`i`必须是`s`长度的约数（即`s`的长度能被`i`整除）。-从`1`到`n//2`遍历所有可能的子串长度`i`，检查`s[:i]`重复`n//i`次是否等于原字符串。-如果找到满足条件的子串，返回`true`；否则返回`false`。2.时间复杂度分析：-遍历的次数为`O(n/2)`，即`O(n)`。-每次检查子串重复时，字符串拼接的时间复杂度为`O(n)`，但整体仍为`O(n)`。3.优化思路：-更高效的方法可以使用KMP算法预处理字符串，但此处为避免复杂度，采用简单暴力解法。题目2（20分）：问题描述：给定一个包含`n`个整数的数组`nums`，判断该数组是否可以由两个不同的子集组成，使得这两个子集的元素和相等。示例：-输入：`[1,5,11,5]`→输出：`true`（可以分成`[1,5,5]`和`[11]`）-输入：`[1,2,3,5]`→输出：`false`要求：1.子集可以包含重复元素。2.子集不需要是连续的。答案与解析：答案：pythondefcan_partition(nums):total_sum=sum(nums)iftotal_sum%2!=0:returnFalsetarget=total_sum//2n=len(nums)dp=[False](target+1)dp[0]=Truefornuminnums:forjinrange(target,num-1,-1):dp[j]=dp[j]ordp[j-num]returndp[target]解析：1.核心思路：-如果所有数字的总和是奇数，则无法分成两个等和子集，直接返回`false`。-问题转化为：是否存在一个子集，其和等于`total_sum//2`。-使用动态规划（DP）解决，定义`dp[j]`表示是否可以用子集达到和为`j`。2.DP状态转移：-初始：`dp[0]=True`（和为0总是可达）。-遍历每个数字`num`，从`target`倒序到`num`更新`dp`，避免重复使用同一数字。3.时间复杂度：-空间复杂度：`O(target)`。-时间复杂度：`O(ntarget)`，适用于数字量不大的情况。题目3（20分）：问题描述：实现一个函数`minMeetingRooms(intervals)`，其中`intervals`是一个二维数组，每个元素表示一个会议的起始和结束时间`[[s1,e1],[s2,e2],...]`。返回至少需要多少间会议室才能满足所有会议不冲突。示例：-输入：`[[0,30],[5,10],[15,20]]`→输出：`2`-输入：`[[7,10],[2,4]]`→输出：`1`要求：1.会议时间不一定是整数。2.可以假设所有会议开始时间不同。答案与解析：答案：pythondefminMeetingRooms(intervals):ifnotintervals:return0start_times=sorted([i[0]foriinintervals])end_times=sorted([i[1]foriinintervals])rooms=0used_end=0i,j=0,0whilei<len(start_times):ifstart_times[i]>=end_times[used_end]:used_end+=1else:rooms+=1i+=1returnrooms解析：1.核心思路：-将所有会议的开始时间和结束时间分别排序。-使用双指针遍历`start_times`和`end_times`，记录当前使用的会议室数量。-如果当前会议的开始时间大于等于某个会议室的结束时间，则该会议室可被复用。2.时间复杂度：-排序时间：`O(nlogn)`。-双指针遍历：`O(n)`。3.关键点：-排序后，只需比较当前会议是否可以复用已有会议室，无需额外空间存储状态。题目4（20分）：问题描述：给定一个二叉树，判断它是否是高度平衡的二叉树。一棵二叉树每个节点的左右子树的高度差不超过1。示例：-输入：3/\920/\157→输出：`true`-输入：1/\22/\34→输出：`false`要求：1.不需要计算非平衡节点的最小深度。答案与解析：答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisBalanced(root:TreeNode)->bool:defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)balanced=left_balancedandright_balancedandabs(left_height-right_height)<=1returnmax(left_height,right_height)+1,balancedreturncheck(root)[1]解析：1.核心思路：-使用递归计算每个节点的左右子树高度，同时判断左右子树是否平衡。-如果任意节点的左右子树高度差大于1，则整棵树不平衡。2.递归函数`check(node)`返回：-当前节点的高度。-当前子树是否平衡。3.时间复杂度：-每个节点访问一次，时间复杂度：`O(n)`。题目5（20分）：问题描述：实现一个函数`topKFrequent(nums,k)`，返回`nums`中出现频率最高的`k`个元素。示例：-输入：`nums=[1,1,1,2,2,3],k=2`→输出：`[1,2]`-输入：`nums=[4,4,4,5,5,5,5,6],k=1`→输出：`[5]`要求：1.不考虑元素顺序。2.可以使用排序或堆实现。答案与解析：答案：pythonfromcollectionsimportCounterimportheapqdeftopKFrequent(nums,k):count=Counter(nums)使用最小堆，堆大小为kheap=[]fornum,freqincount.items():heapq.heappush(heap,(freq,num))iflen(heap)>k:heapq.heappop(heap)提取堆中的元素return[numforfreq,numinheap]解析：1.核心思路：-使用`Counter`统计每个数字的频率。-使用最小堆维护频率最高的`k`个元素，堆中存储`(频率,数字)`。-遍历`Counter`时，如果堆大小超过`k`，弹出最小元素。2.时间复杂度：-`Counter`统计：`O(n)`。-堆操作：每次插入或弹出是`O(logk)`，共`O(nlogk)`。3.替代方案：-可以先排序频率，但时间复杂度为`O(nlogn)`。堆更优。二、系统设计测试（共3题，每题33分，总分99分）考察点：分布式系统、高并发、数据库设计题目6（33分）：问题描述：设计一个高并发的短链接系统。要求：1.用户输入长链接，系统返回短链接。2.短链接访问时自动跳转回长链接。3.系统需要支持高并发访问（每秒百万级请求）。4.短链接生成唯一且易于记忆（如`/abc123`）。要求：1.描述核心组件和数据结构。2.说明如何处理高并发和分布式扩展。3.如何保证短链接的唯一性和快速生成。答案与解析：答案：1.核心组件：-API服务：接收长链接请求，生成短链接，缓存访问记录。-短链接生成器：使用自增ID或分布式唯一ID生成算法（如Twitter的Snowflake算法）。-分布式缓存（Redis/Memcached）：缓存短链接到长链接的映射，加速访问。-数据库（MySQL/PostgreSQL）：持久化短链接和访问日志。-负载均衡器：分散请求到多个API服务实例。2.高并发处理：-缓存穿透：使用布隆过滤器或空对象缓存防止无效请求直接查询数据库。-读写分离：将查询操作（短链接到长链接的映射）分发给缓存，更新操作（如统计点击数）写入数据库。-限流：使用令牌桶或漏桶算法限制请求速率。3.短链接生成：-自增ID+编码：将ID转换为62进制字符（如`a-z0-9`），减少长度。-分布式ID：Snowflake算法生成全局唯一ID，避免冲突。解析：1.分布式扩展：-API服务部署在Kubernetes集群中，通过负载均衡器扩展。-缓存和数据库使用分片或集群架构。2.唯一性保证：-Snowflake算法结合机器ID和序列号，确保全局唯一。3.性能优化：-缓存命中率越高，数据库压力越小。题目7（33分）：问题描述：设计一个高并发的实时消息推送系统（如微信、抖音）。要求：1.支持单点登录（SSO），用户跨设备同步状态。2.支持离线消息存储，用户上线后立即推送未读消息。3.系统需要支持百万级用户同时在线。要求：1.描述核心组件和数据结构。2.如何实现消息的实时性和可靠性。3.如何处理用户状态同步和消息队列。答案与解析：答案：1.核心组件：-认证服务（OAuth2/OIDC）：处理SSO和用户授权。-消息队列（Kafka/RabbitMQ）：解耦消息生产者和消费者。-消息存储（Redis/Memcached）：缓存在线用户和实时消息。-关系数据库（MySQL/PostgreSQL）：持久化用户关系和消息记录。-推送服务（WebSocket/Server-SentEvents）：实时推送消息。2.实时性和可靠性：-消息队列：保证消息不丢失，即使服务宕机。-持久化：消息先写入数据库，确认后再删除。-心跳检测：通过WebSocket或长轮询检测用户在线状态。3.用户状态同步：-在线状态：使用Redis存储在线用户ID，支持快速查询。-离线消息：用户上线时，从数据库拉取未读消息。解析：1.可扩展性：-消息队列水平扩展，支持高吞吐量。-推送服务使用WebSocket保持长连接，减少HTTP轮询开销。2.可靠性：-消息确认机制（ACK），防止消息丢失。-冗余部署和故障转移。题目8（33分）：问题描述：设计一个高并发的秒杀系统。要求：1.用户点击秒杀按钮后，系统需要在1秒内返回购买结果（成功或失败）。2.防止超卖和恶意刷单。3.系统需要支持每秒千级用户请求。要求：1.描述核心组件和数据结构。2.如何处理高并发和库存扣减。3.如何防止重复下单和超卖。答案与解析：答案：1.核心组件：-前端拦截：使用验证码或滑动验证防止机器刷单。-分布式锁（Redis/Lock）：保证库存扣减的原子性。-事务数据库：使用乐观锁或悲观锁防止超卖。-消息队列：解耦秒杀请求和库存更新。2.高并发处理：-限流：使用令牌桶算法限制请求速率。-库存预减：用户下单时先扣减库存，确认后再写入数据库。3.防止重复下单：-数据库唯一索引：限制用户对同一商品的多次下单。-分布式锁：确保同一用户同一时间只能下单一次。解析：1.库存扣减策略：-RedisLua脚本：在单线程中完成库存扣减和订单生成，避免事务开销。-数据库乐观锁：通过版本号判断库存是否被修改。2.防止超卖：-幂等性设计：用户下单后，即使系统崩溃，也能恢复时重试。三、综合能力测试（共2题，每题33分，总分66分）考察点：面试技巧、行业理解、问题解决题目9（33分）：问题描述：你正在面试一个候选人说：“请谈谈你对微服务架构的理解，以及为什么它适合互联网公司？”要求：1.候选人应如何回答？2.面试官应如何评估答案？答案与解析：答案：1.候选人回答要点：-定义：微服务是将大型应用拆分为一组小型、独立服务，每个服务负责特定业务功能。-优势：-独立部署：每个服务可独立升级，不影响其他服务。-技术异构：每个服务可使用最适合的技术栈。-弹性扩展：只需扩展需求高的服务。-互联网场景适用性：-快速迭代：微服务支持并行开发，加速产品上线。-高并发：水平扩展单个服务可应对突发流量。2.面试