科技公司面试题解析与答案

2026年科技公司面试题解析与答案编程与算法题（5题，每题20分，共100分）题目1（20分）：问题描述：给定一个包含重复元素的整数数组，请找出所有不重复的三元组，使得这三个数的和等于一个给定的目标值。你可以假设每个输入只对应一个答案，但不允许重复的三元组。例如，给定数组`nums=[-1,0,1,2,-1,-4]`和目标值`target=0`，一个有效的三元组是`[-1,0,1]`。要求：-时间复杂度不超过O(n²)。-输出所有唯一的三元组，不能包含重复的解。答案与解析：答案：pythondefthreeSum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：1.排序数组：先对数组进行排序，方便后续使用双指针法。2.固定第一个数：遍历数组，固定第一个数`nums[i]`，使用双指针`left`和`right`分别指向`i+1`和`n-1`。3.去重处理：-如果`nums[i]`与前一个数相同，跳过（避免重复解）。-如果`nums[left]`与前一个数相同，右移`left`。-如果`nums[right]`与前一个数相同，左移`right`。4.计算和：-如果`total==target`，记录三元组，并移动双指针同时跳过重复值。-如果`total<target`，左移`left`以增加和。-如果`total>target`，右移`right`以减少和。时间复杂度：O(n²)，排序O(nlogn)，双指针遍历O(n²)。题目2（20分）：问题描述：设计一个算法，找出数组中不重复的数字，并返回它们的数量。数组中的数字范围在`1`到`n`（n是数组的长度），其中恰好有一个数字出现了两次，其他数字各出现一次。例如，给定数组`[4,3,2,7,8,2,3,1]`，返回`5`（因为数字`5`没有出现）。要求：-不使用额外空间（或使用O(1)额外空间）。-返回不重复数字的数量。答案与解析：答案：pythondeffindDisappearedNumbers(nums):n=len(nums)foriinrange(n):index=abs(nums[i])-1ifnums[index]<0:continuenums[index]=-nums[index]returnsum(1fornuminnumsifnum>0)解析：1.标记法：利用数组本身的值作为标记。遍历数组，对于每个`nums[i]`，将其对应的索引`abs(nums[i])-1`处的值取反。-例如，`nums[i]=2`，则`nums[1]`取反。2.判断重复：如果某个索引对应的值已经是负数，说明该索引对应的数字`index+1`出现过。3.统计不重复数字：遍历数组，统计正数的数量（未被取反的索引+1）。时间复杂度：O(n)，空间复杂度：O(1)。题目3（20分）：问题描述：给定一个非空字符串`s`，最多包含`1000`个字符，其中包含字母和数字。请编写一个算法，找出字符串中最长的回文子串的长度。例如，给定`s="babad"`，最长回文子串可以是`"bab"`或`"aba"`，返回`3`。要求：-可以使用动态规划或中心扩展法。答案与解析：答案（中心扩展法）：pythondeflongestPalindrome(s):ifnots:return0start,end=0,0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returnend-start+1defexpandAroundCenter(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：1.中心扩展法：对于每个字符，尝试以它为中心扩展回文（奇数长度和偶数长度）。-奇数长度：`expandAroundCenter(s,i,i)`-偶数长度：`expandAroundCenter(s,i,i+1)`2.更新最长回文：记录当前最长的回文子串的起始和结束位置。3.返回长度：最长回文子串的长度为`end-start+1`。时间复杂度：O(n²)，空间复杂度：O(1)。题目4（20分）：问题描述：设计一个算法，将一个给定数组中的`0`移动到数组的末尾，同时保持非零元素的相对顺序。例如，给定`nums=[0,1,0,3,12]`，移动后为`[1,3,12,0,0]`。要求：-不能使用额外空间（或使用O(1)额外空间）。-只需遍历一次数组。答案与解析：答案：pythondefmoveZeroes(nums):slow=0forfastinrange(len(nums)):ifnums[fast]!=0:nums[slow],nums[fast]=nums[fast],nums[slow]slow+=1解析：1.双指针法：-`slow`指向下一个非零元素应放置的位置。-`fast`遍历数组，遇到非零元素时，与`slow`交换，并移动`slow`。2.过程：-初始`slow=0`，遍历`fast`从`0`到`n-1`。-如果`nums[fast]!=0`，交换`nums[slow]`和`nums[fast]`，然后`slow+=1`。3.结果：所有非零元素按原顺序移到前面，`0`在后面。时间复杂度：O(n)，空间复杂度：O(1)。题目5（20分）：问题描述：给定一个字符串`s`，请你将其转换成最长回文子串。例如，给定`s="aabbac"`，最长回文子串可以是`"bbab"`或`"abba"`，返回`"bbab"`（或`"abba"`）。要求：-可以使用动态规划或马拉车算法（Manacher'sAlgorithm）。答案与解析：答案（动态规划）：pythondeflongestPalindromeDP(s):n=len(s)ifn==0:return""dp=[[False]nfor_inrange(n)]start,max_len=0,1foriinrange(n):dp[i][i]=Trueforiinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truestart=imax_len=2forlengthinrange(3,n+1):foriinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truestart=imax_len=lengthreturns[start:start+max_len]解析：1.动态规划表`dp[i][j]`：-`dp[i][j]`为`True`表示`s[i..j]`是回文。2.初始化：-所有单个字符是回文，`dp[i][i]=True`。-检查两个字符，`dp[i][i+1]=(s[i]==s[i+1])`。3.状态转移：-对于长度`length`从`3`到`n`，检查`s[i..j]`是否为回文：-如果`s[i]==s[j]`且`s[i+1..j-1]`是回文，则`dp[i][j]=True`。4.记录最长回文：-更新最长回文的起始位置`start`和长度`max_len`。5.返回结果：子串`s[start:start+max_len]`。时间复杂度：O(n²)，空间复杂度：O(n²)。系统设计题（2题，每题30分，共60分）题目6（30分）：问题描述：设计一个简单的微博（Twitter）系统，支持以下核心功能：1.用户发布微博（限制长度不超过280字符）。2.用户关注其他用户。3.用户查看自己关注的人发布的最新`10`条微博。要求：-描述系统架构（数据存储、主要模块）。-说明关键技术选型（数据库、缓存等）。-处理高并发场景下的挑战（例如，用户查看热门微博时）。答案与解析：答案：1.系统架构：-前端：Web/App界面（React/Vue+Flutter）。-后端：微博服务（Node.js/Go+SpringBoot）。-数据库：-用户表：`users`（`id`,`username`,`password`,`follows`）。-微博表：`tweets`（`id`,`user_id`,`content`,`timestamp`）。-关注关系表：`follows`（`follower_id`,`followee_id`）。-缓存：Redis（缓存用户关注列表、热门微博）。-消息队列：Kafka/RabbitMQ（异步处理发布、关注等操作）。2.关键技术选型：-数据库：-用户和关注关系使用MySQL（关系型，支持事务）。-微博使用MongoDB（文档存储，适合长文本）。-缓存：Redis（热点数据缓存，如用户关注列表、热门微博）。-消息队列：Kafka（解耦服务，处理高并发写入）。3.高并发处理：-缓存穿透：用户关注列表存入Redis，减少数据库查询。-热点数据预热：热门用户微博提前加载到缓存。-分页加载：查看微博时，后端分页返回`10`条最新数据。-限流：Token限流（防止恶意攻击）。解析：1.数据存储：-用户和关注关系使用关系型数据库（MySQL），支持事务。-微博使用MongoDB，方便存储长文本和扩展字段（如图片）。2.缓存策略：-用户关注列表存入Redis，查询时直接返回，避免数据库压力。-热门微博缓存，用户查看时优先从Redis获取。3.高并发优化：-使用消息队列异步处理关注、发布等操作，降低系统延迟。-分页加载避免一次性加载过多数据。挑战：-数据一致性：关注关系和微博发布需要强一致性（使用MySQL事务）。-缓存失效：关注列表更新时，需要异步刷新Redis。题目7（30分）：问题描述：设计一个实时聊天系统（类似微信），支持以下功能：1.用户登录、登出。2.发送和接收消息（支持文本、图片、语音）。3.群聊功能（支持创建群组、加入群组、发送群消息）。要求：-描述系统架构（消息传输、存储）。-说明如何保证消息的实时性和可靠性。-处理大用户量下的性能问题。答案与解析：答案：1.系统架构：-前端：App端（iOS/Android+Flutter/ReactNative）。-后端：聊天服务（WebSocket+Node.js/Go）。-数据库：Redis（缓存会话信息、消息队列）。-消息存储：MongoDB（存储已读状态、消息记录）。-实时通信：WebSocket（双向通信）。2.消息传输与存储：-实时传输：W