编程试题（附答案）

编程试题（附答案）问题背景随着社交网络的普及，用户之间的关注关系形成了复杂的有向图结构。为了分析用户行为和社交影响力，需设计一个社交网络用户关系分析系统，实现基础关系管理、共同关注统计、影响力范围计算等功能。以下为具体需求。功能需求功能1：用户关系管理系统需支持以下操作：-添加关注关系：给定用户A和用户B（A≠B），记录A关注B的关系。若关系已存在，无需重复存储。-查询直接关注列表：给定用户X，返回X直接关注的所有用户（即X主动关注的人），结果按用户ID升序排列。-查询粉丝列表：给定用户X，返回所有关注X的用户（即X的粉丝），结果按用户ID升序排列。功能2：共同关注用户统计给定两个用户A和B，计算同时被A和B关注的用户集合（共同关注用户）。若集合非空，需按以下规则排序：-优先按共同关注用户的粉丝数（即被多少人关注）从多到少排序；-若粉丝数相同，按用户ID升序排列。功能3：影响力范围分析用户的影响力范围定义为：从该用户出发，通过最多k次关注跳转（k≥0）能到达的所有用户（包括间接关注）。其中：-跳转规则：若用户X关注Y（X→Y），则从X到Y为1次跳转；若Y关注Z（Y→Z），则从X到Z需2次跳转（X→Y→Z）。-特别地，k=0时，影响力范围仅包含用户自身；k≥1时，需包含所有通过≤k次跳转可达的用户（不包含自身）。请实现函数，给定用户X和正整数k，返回其影响力范围内所有用户的集合（去重），结果按用户ID升序排列。功能4：大规模数据优化当用户数量超过10万、关注关系超过1000万时，前3项功能的查询效率可能下降。请说明优化思路，并给出至少2种具体优化方案（需结合数据结构或算法原理）。输入输出示例示例1（功能1）输入操作序列：addABaddACaddBCaddCAquery_followAquery_followerC输出：["B","C"]["A","B"]示例2（功能2）用户关注关系：A关注：B、C、DB关注：C、D、EC的粉丝数：5（被A、B、F、G、H关注）D的粉丝数：3（被A、B、I关注）E的粉丝数：2（被B、J关注）输入：计算A和B的共同关注用户输出：["C","D"]示例3（功能3）用户关注关系：A→B，B→C，C→D，D→E，A→D（k=2）输入：X=A，k=2输出：["B","C","D"]试题要求1.代码需使用Python语言实现，要求逻辑清晰、注释完整；2.功能3需处理k较大的情况（如k=1000），需避免超时；3.功能4的优化方案需具体可行，需结合时间复杂度或空间复杂度分析。答案功能1：用户关系管理实现实现思路使用两个字典存储关注关系：-`follow_map`：键为用户ID，值为该用户关注的用户集合（避免重复）。-`follower_map`：键为用户ID，值为关注该用户的粉丝集合（避免重复）。添加关注关系时，若A→B不存在，则向`follow_map[A]`添加B，并向`follower_map[B]`添加A。查询时，将集合转换为排序后的列表。代码实现```pythonclassSocialNetwork:def__init__(self):self.follow_map=dict(){用户:关注的用户集合}self.follower_map=dict(){用户:粉丝集合}defadd_follow(self,a:str,b:str)->None:"""添加关注关系（a关注b）"""ifa==b:return不能关注自己处理follow_mapifanotinself.follow_map:self.follow_map[a]=set()ifbnotinself.follow_map[a]:self.follow_map[a].add(b)处理follower_mapifbnotinself.follower_map:self.follower_map[b]=set()ifanotinself.follower_map[b]:self.follower_map[b].add(a)defquery_follow(self,x:str)->list:"""查询x的直接关注列表（升序）"""follows=self.follow_map.get(x,set())returnsorted(follows)defquery_follower(self,x:str)->list:"""查询x的粉丝列表（升序）"""followers=self.follower_map.get(x,set())returnsorted(followers)```功能2：共同关注用户统计实现实现思路1.获取A和B的关注列表，取交集得到共同关注用户集合；2.对每个共同关注用户，查询其粉丝数（即`follower_map`中对应集合的大小）；3.按粉丝数降序、用户ID升序排序。代码实现```pythondefget_common_followers(sn:SocialNetwork,a:str,b:str)->list:"""计算a和b的共同关注用户（排序后）"""获取关注列表a_follows=sn.follow_map.get(a,set())b_follows=sn.follow_map.get(b,set())common=a_follows&b_follows集合交集ifnotcommon:return[]收集（用户ID，粉丝数）元组user_info=[]foruserincommon:follower_count=len(sn.follower_map.get(user,set()))user_info.append((user,follower_count))排序：先按粉丝数降序，再按用户ID升序user_info.sort(key=lambdax:(-x[1],x[0]))return[user[0]foruserinuser_info]```功能3：影响力范围分析实现实现思路使用广度优先搜索（BFS）遍历，限制最大层数为k：-初始化队列，起始用户为X，初始跳转次数为0；-每次从队列中取出用户，遍历其关注的用户（下一层），若跳转次数+1≤k且未被访问过，则加入队列并记录；-最终收集所有访问过的用户（k=0时仅包含X自身；k≥1时排除X）。代码实现```pythondefget_influence_range(sn:SocialNetwork,x:str,k:int)->list:"""计算用户x的影响力范围（最多k次跳转）"""ifk<0:return[]visited=set()queue=[(x,0)](当前用户,已用跳转次数)visited.add(x)BFS遍历whilequeue:current,steps=queue.pop(0)若已达到最大跳转次数，不再扩展ifsteps>=k:continue获取当前用户的关注列表follows=sn.follow_map.get(current,set())forneighborinfollows:ifneighbornotinvisited:visited.add(neighbor)queue.append((neighbor,steps+1))处理k=0的情况（仅包含自身）ifk==0:return[x]k≥1时，排除自身influence=[userforuserinvisitedifuser!=x]returnsorted(influence)```功能4：大规模数据优化方案优化思路大规模数据下，关键瓶颈是查询时的时间复杂度（如集合交集、BFS遍历）和空间复杂度（如存储全量关系）。需通过数据结构优化和算法优化降低复杂度。具体优化方案1.关注关系的存储优化：邻接表→邻接链表+位图-现状：`follow_map`使用集合存储，查询时需遍历整个集合，时间复杂度O(n)（n为关注数）。-优化：对用户ID进行整数映射（如将用户ID哈希为唯一整数），使用位图（BitArray）存储关注关系。例如，用户A的关注关系用一个长度为N的位图表示（N为总用户数），第i位为1表示关注用户i。-优势：集合交集操作可通过位图按位与操作实现，时间复杂度O(N/64)（64位整数运算），远低于集合遍历的O(n)。2.影响力范围的BFS优化：双向BFS+层级缓存-现状：k较大时（如k=1000），BFS需遍历k层，每层可能产生大量节点，时间复杂度O(V+E)（V为用户数，E为关注关系数）。-优化：-双向BFS：从起始用户和目标用户同时搜索（若需判断是否可达），但本题需收集所有可达用户，可改为限制每轮扩展的节点数，优先处理高活跃度用户（关注数多的用户）。-层级缓存：预计算每个用户的1层、2层…k层关注关系，缓存结果。例如，用户X的k层影响力范围=X的1层范围∪X的2层范围∪…∪X的k层范围。缓存后查询时间降为O(1)，但需权衡空间（缓存空间复杂度O(Vk)）。3.粉丝数统计的预计算-现状：计算共同关注用户时，需实时查询每个用户的粉丝数（即`len(follower_map[user])`），若`follower_map`用集合存储，时间复杂度O(1)（集合的长度已缓存），但大规模数据下集合的哈希冲突可能影响性能。