互联网公司算法工程师面试题及答案详解

2026年互联网公司算法工程师面试题及答案详解一、编程能力（共5题，每题10分，总分50分）1.（10分）编写一个函数，实现快速排序算法。输入一个整数数组，返回排序后的数组。要求：不能使用内置排序函数，需手动实现。答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：快速排序的核心是分治思想，通过选择一个基准值（pivot），将数组分为小于、等于、大于三部分，然后递归排序左右两部分。时间复杂度平均为O(nlogn)，最坏情况为O(n²)。2.（10分）给定一个字符串，判断它是否是回文串。例如，"racecar"是回文串，"hello"不是。要求：不使用额外空间。答案：pythondefis_palindrome(s):left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:returnFalseleft+=1right-=1returnTrue解析：双指针法从两端向中间遍历，比较字符是否相同。时间复杂度为O(n)，空间复杂度为O(1)。注意忽略非字母数字字符的情况。3.（10分）实现一个无重复字符的最长子串查找功能。例如，输入"abcabcbb"，返回"abc"（长度为3）。答案：pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：滑动窗口技术，使用哈希表记录字符上一次出现的位置。时间复杂度为O(n)，空间复杂度为O(min(m,n))，其中m为字符集大小。4.（10分）设计一个LRU（最近最少使用）缓存，支持get和put操作。例如：-get(1)→返回1-put(2,2)→缓存为{1=1,2=2}-get(1)→返回1-put(3,3)→缓存满，删除最久未使用键2-get(2)→返回-1答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用哈希表记录键值对，双端队列记录访问顺序。get时移动元素到队尾，put时先删除最久未使用元素，然后插入新元素。时间复杂度为O(1)。5.（10分）给定一个包含n个整数的数组，判断数组中是否存在三个元素a,b,c，使得a+b+c=0。找出所有不重复的三元组。答案：pythondefthree_sum(nums):nums.sort()result=[]foriinrange(len(nums)-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,len(nums)-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnresult解析：排序后使用双指针法，固定第一个数，然后左右夹逼查找。时间复杂度为O(n²)，需要忽略重复三元组。二、系统设计（共3题，每题15分，总分45分）1.（15分）设计一个微博系统，要求支持以下功能：-用户发布微博（支持文字、图片、视频）-用户关注/取消关注其他用户-实时显示用户关注人的最新动态（最多10条）-支持分页加载历史消息答案：核心组件：1.用户模块（User）：存储用户信息（ID、昵称、关注列表、粉丝列表）。2.微博模块（Tweet）：存储微博内容（ID、用户ID、内容、时间戳、点赞数、转发数）。3.关系模块（Follow）：存储关注关系（用户ID1→用户ID2）。4.消息队列（Kafka/RabbitMQ）：实时推送动态。数据存储：-用户和关系使用MySQL（高可用分片）。-微博使用MongoDB（文档存储，支持混合内容）。-缓存Redis存储热门用户动态（热点数据）。实时推荐逻辑：-用户关注的人的微博通过Redis订阅，按时间降序缓存10条。-分页加载历史消息时，查询MongoDB按时间降序分页。高可用方案：-负载均衡（Nginx）分发请求。-微博和用户数据使用主从复制。解析：关键点在于实时动态的优化（Redis缓存）和大数据量的分页处理（MongoDB索引）。关系数据库用于事务一致性，NoSQL用于高性能读。2.（15分）设计一个短链接系统（如tinyURL），要求：-输入长链接，返回短链接-通过短链接跳转到对应长链接-支持高并发访问答案：核心组件：1.短链接生成器：使用Base62编码（a-z,A-Z,0-9）将ID映射为6位短码。2.缓存层（Redis）：缓存短链接→长链接映射，加速查询。3.数据库（MySQL）：持久化短链接和长链接映射。4.API网关（Nginx）：负载均衡，防DDoS攻击。生成逻辑：pythonimportbase64importhashlibdefencode_id(num):chars="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"base=len(chars)encoded=""whilenum>0:encoded=chars[num%base]+encodednum//=basereturnencoded.zfill(6)#补足6位defgenerate_short_url(long_url):hash_obj=hashlib.sha256(long_url.encode())num=int(hash_obj.hexdigest(),16)short_code=encode_id(num)returnf"https://short.url/{short_code}"解析：Base62编码减少短链接长度。Redis缓存解决高并发热点问题。数据库用于数据持久化。Nginx防攻击。3.（15分）设计一个高并发秒杀系统，要求：-用户点击秒杀按钮时，系统需判断库存是否充足-限制用户购买数量（每人限购1件）-防止超卖和并发攻击答案：核心组件：1.库存系统（Redis）：使用原子操作`DECRBY`扣减库存，设置过期防止超卖。2.用户限购（Redis）：使用`SETNX`或布隆过滤器记录用户购买状态。3.秒杀接口（APIGateway）：-请求先验证用户限购状态。-库存充足则扣减库存，返回成功；否则返回失败。4.消息队列（Kafka）：记录秒杀日志，用于复盘。防并发方案：-请求先经过分布式锁（RedisSETNX）。-超卖时通过补偿机制重试扣减库存。解析：Redis原子操作是关键，防止库存超卖。限购使用Redis避免重复购买。消息队列用于日志和后续补偿。三、算法与数据结构（共5题，每题10分，总分50分）1.（10分）给定一个二叉树，判断它是否是平衡二叉树（左右子树高度差不超过1）。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root):defheight(node):ifnotnode:return0left_h=height(node.left)right_h=height(node.right)ifleft_h==-1orright_h==-1orabs(left_h-right_h)>1:return-1returnmax(left_h,right_h)+1returnheight(root)!=-1解析：后序遍历计算高度，遇到不平衡时提前返回-1。时间复杂度为O(n)。2.（10分）实现一个二叉树的前序遍历（非递归）。答案：pythondefpreorder_traversal(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult解析：栈模拟递归，先访问节点，再右后左压栈。3.（10分）设计一个算法，找出数组中重复次数超过n/2的元素。答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：Boyer-Moore投票算法，时间O(n)，空间O(1)。4.（10分）给定一个链表，反转链表并返回反转后的头节点。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev,current=None,headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent