新浪微博算法工程师面试问题解析

2026年新浪微博算法工程师面试问题解析一、编程基础与数据结构（共5题，总分20分）1.（4分）实现一个LRU（LeastRecentlyUsed）缓存，要求使用链表和哈希表结合的方式，支持`get`和`put`操作，时间复杂度为O(1)。2.（4分）给定一个无重复元素的数组`nums`和一个目标值`target`，返回所有相加和为`target`的`nums`的索引组合。例如：`nums=[2,3,6,7]`,`target=7`，返回`[[0,1],[1,2]]`。3.（5分）设计一个算法，找出数组中重复次数超过`n/3`的元素，假设数组长度为`n`且至少有两个重复元素。4.（4分）实现快速排序算法，要求原地排序，并写出其平均时间复杂度和最坏情况时间复杂度。5.（3分）解释什么是布隆过滤器（BloomFilter），并说明其优缺点及适用场景。二、算法设计（共3题，总分15分）1.（5分）新浪微博的推荐系统需要实时处理用户的行为日志（如点击、点赞、评论），设计一个数据结构支持以下操作：-插入用户行为日志（包含用户ID、内容ID、行为类型、时间戳）。-查询某个用户最近`k`条行为，按时间降序排列。2.（5分）假设微博消息包含大量emoji表情符号，设计一个算法去除消息中的重复emoji，同时保留首次出现的顺序。3.（5分）微博的热搜榜需要实时更新，要求：-支持每分钟统计一次热门话题，时间复杂度尽可能低。-热搜榜最多显示前10个话题，新话题需要动态插入。三、系统设计（共2题，总分15分）1.（8分）设计一个微博消息的分发系统，要求：-支持用户发布消息（文本+图片/视频），消息需要异步处理并推送给关注者。-使用消息队列解决高并发下的性能瓶颈问题。2.（7分）微博的评论系统需要支持以下功能：-用户可以回复其他用户的评论，形成树状结构。-查询某个评论的所有回复，要求前`k`级回复。四、机器学习与深度学习（共2题，总分10分）1.（5分）微博文本情感分析中，为什么需要使用词嵌入（WordEmbedding）？列举至少两种常见的词嵌入方法（如Word2Vec、BERT）。2.（5分）解释过拟合（Overfitting）和欠拟合（Underfitting）的概念，并提出至少两种解决方法（如正则化、交叉验证）。五、分布式与数据库（共2题，总分10分）1.（5分）微博的数据库使用MySQL+Redis组合，说明Redis在推荐系统中的作用（如缓存热点数据）。2.（5分）设计一个分布式任务调度系统，要求：-支持定时任务（如每日统计用户活跃度）。-处理任务失败重试的逻辑。六、开放性问题（共1题，总分5分）1.（5分）微博推荐系统的冷启动问题是什么？如何缓解冷启动问题？答案与解析一、编程基础与数据结构1.（4分）LRU缓存实现pythonclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._move_to_head(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:node=Node(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.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_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres解析：-使用双向链表维护访问顺序，头节点为最近访问，尾节点为最久未访问。-哈希表`cache`存储键值对，实现O(1)的`get`和`put`操作。-删除尾节点时释放内存，保证缓存大小不超过`capacity`。2.（4分）三数之和组合问题pythondefthreeSum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:s=nums[i]+nums[left]+nums[right]ifs==target:res.append([i,left,right])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifs<target:left+=1else:right-=1returnres解析：-排序后使用双指针法，固定第一个数，在剩余部分找两数和。-跳过重复元素避免重复组合。3.（5分）找出出现次数超过`n/3`的元素pythondefmajorityElement(nums):candidate1,candidate2,count1,count2=None,None,0,0fornuminnums:ifnum==candidate1:count1+=1elifnum==candidate2:count2+=1elifcount1==0:candidate1,count1=num,1elifcount2==0:candidate2,count2=num,1else:count1-=1count2-=1res=[]count1,count2=0,0fornuminnums:ifnum==candidate1:count1+=1elifnum==candidate2:count2+=1ifcount1>len(nums)//3:res.append(candidate1)ifcount2>len(nums)//3:res.append(candidate2)returnres解析：-Boyer-Moore多数投票算法的扩展，维护两个候选者和计数器。-首次遍历排除非多数元素，第二次验证候选者的实际出现次数。4.（4分）快速排序算法pythondefquicksort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquicksort(left)+middle+quicksort(right)解析：-平均时间复杂度O(nlogn)，最坏情况O(n²)（选择最坏枢轴）。-原地排序可通过交换实现，但代码中为简化使用列表分治。5.（3分）布隆过滤器-原理：将键映射为多个哈希函数，存储在位数组中。-优点：空间效率高，支持快速查询。-缺点：存在误判（假阳性），无法删除元素（除非使用计数布隆过滤器）。-适用场景：缓存、爬虫URL去重、恶意IP检测。二、算法设计1.（5分）实时用户行为日志处理pythonfromcollectionsimportdequeclassBehaviorLog:def__init__(self):self.logs={}#user_id:dequeof(timestamp,action)definsert(self,user_id,content_id,action,timestamp):ifuser_idnotinself.logs:self.logs[user_id]=deque()self.logs[user_id].append((timestamp,action,content_id))self.logs[user_id].sort(reverse=True)#保持时间降序defquery(self,user_id,k):returnself.logs.get(user_id,[])[:k]解析：-使用`deque`存储每个用户的最近行为，按时间降序排列。-插入时保持队列长度不超过实时窗口（如最近1小时）。2.（5分）去重emoji的算法pythondefremove_duplicate_emojis(s):seen=set()res=[]forcharins:ifcharnotinseen:res.append(char)seen.add(char)return''.join(res)解析：-使用集合`seen`记录已出现的emoji，保留首次出现的顺序。-适用于微博消息中emoji重复的情况。3.（5分）热搜榜设计pythonfromcollectionsimportdefaultdict,dequeclassHotSearch:def__init__(self):self.topic_counts=defaultdict(int)self.rank=deque(maxlen=10)#存储前10个话题defupdate(self,topic):self.topic_counts[topic]+=1iftopicnotinself.rank:self.rank.append(topic)self.rank=deque(sorted(self.rank,key=lambdax:self.topic_counts[x],reverse=True),maxlen=10)defget_top(self):returnlist(self.rank)解析：-使用哈希表统计话题热度，队列维护前10名。-动态插入时按热度排序，保证实时性。三、系统设计1.（8分）微博消息分发系统-核心组件：1.消息队列（Kafka/RabbitMQ）：异步处理发布请求，削峰填谷。2.发布服务：接收用户请求，写入消息队列。3.消费服务：按关注者分组消费消息，推送到WebSocket/长轮询。-高并发解决方案：-限流：令牌桶算法控制消息写入速度。-分片：将用户关注关系分片存储，避免单节点过载。2.（7分）评论系统树状结构设计-数据存储：-评论ID、父评论ID、用户ID、内容、时间戳。-父评论ID为空时为顶级评论，否则递归查询子评论。-查询优化：-使用递归或BFS遍历评论树，限制递归层数（如前3级）。-缓存热门评论的子树，避免重复计算。四、机器学习与深度学习1.（5分）词嵌入的作用与方法-作用：将文本转化为数