2026年互联网公司算法工程师题

2026年互联网公司算法工程师题一、编程实现题（共3题，每题30分，总分90分）1.（30分）题目：实现一个函数`topKFrequent(nums,k)`，输入一个整数数组`nums`和一个整数`k`，返回`nums`中出现频率最高的`k`个元素。你可以假设`nums`中所有元素都是正整数，且`k`小于等于`nums`的长度。要求：-不能使用排序，时间复杂度尽量低。-请用Python实现。示例：pythonnums=[1,1,1,2,2,3]k=2输出：[1,2]答案与解析：答案：pythonfromcollectionsimportCounterdeftopKFrequent(nums,k):count=Counter(nums)freq=list(count.values())bucket=[[]for_inrange(len(nums)+1)]fornum,cntincount.items():bucket[cnt].append(num)result=[]foriinrange(len(bucket)-1,-1,-1):fornuminbucket[i]:result.append(num)iflen(result)==k:returnresult解析：-使用`Counter`统计每个数字的出现频率。-建立`bucket`数组，索引代表频率，值是出现该频率的数字列表。-从高频率开始遍历`bucket`，按顺序收集前`k`个数字。-时间复杂度：O(n)，空间复杂度：O(n)。2.（30分）题目：实现一个函数`merge(intervals)`，输入一个二维数组`intervals`，其中`intervals[i]=[start_i,end_i]`表示一个区间，合并所有重叠的区间，并返回一个不重叠的区间数组。要求：-合并后不重叠的区间按顺序排列。-请用Python实现。示例：pythonintervals=[[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]答案与解析：答案：pythondefmerge(intervals):ifnotintervals:return[]按起点排序intervals.sort(key=lambdax:x[0])merged=[]forintervalinintervals:ifnotmergedormerged[-1][1]<interval[0]:merged.append(interval)else:merged[-1][1]=max(merged[-1][1],interval[1])returnmerged解析：-首先按区间的起点排序。-遍历区间，如果当前区间的起点大于合并区间的终点，则直接添加；否则更新合并区间的终点。-时间复杂度：O(nlogn)，空间复杂度：O(n)。3.（30分）题目：实现一个函数`wordBreak(s,wordDict)`，输入一个字符串`s`和一个单词集合`wordDict`，判断`s`是否可以由`wordDict`中的单词按顺序拼接而成。可以重复使用`wordDict`中的单词。要求：-请用Python实现。示例：pythons="leetcode"wordDict=["leet","code"]输出：True答案与解析：答案：pythondefwordBreak(s,wordDict):dp=[False](len(s)+1)dp[0]=Trueforiinrange(1,len(s)+1):forwordinwordDict:ifi>=len(word)ands[i-len(word):i]==wordanddp[i-len(word)]:dp[i]=Truebreakreturndp[len(s)]解析：-使用动态规划（DP）数组`dp`，`dp[i]`表示`s[:i]`是否可以由`wordDict`拼接。-初始化`dp[0]=True`，表示空字符串可以拼接。-遍历`s`的每个位置`i`，检查`wordDict`中是否有单词以`s[i-len(word):i]`结尾，且`dp[i-len(word)]`为`True`。-时间复杂度：O(nml)，其中`n`是`s`的长度，`m`是`wordDict`的长度，`l`是单词的平均长度。-空间复杂度：O(n)。二、算法设计题（共2题，每题25分，总分50分）1.（25分）题目：设计一个算法，支持用户实时查询某个城市在过去24小时内最多有多少人同时在线。假设输入是按时间顺序的日志，每条日志包含用户ID、城市和时间戳（格式为UNIX时间戳）。要求：-支持实时查询。-时间复杂度尽量低。-请描述算法思路，并用Python伪代码实现核心逻辑。示例：pythonlogs=[["user1","北京",1650846400],["user2","北京",1650846401],["user1","上海",1650846402],["user3","北京",1650846403],["user2","北京",1650846404],["user1","北京",1650846405]]查询时间：1650846400输出：1（只有user2在此时间点在线）答案与解析：答案：算法思路：1.使用哈希表记录每个城市的在线用户集合。2.遍历时，对于每个日志：-如果用户之前不在该城市的集合中，则添加；否则移除。-使用滑动窗口（固定24小时）维护当前城市的在线用户集合。3.查询时返回当前窗口内最大的在线用户数。伪代码：pythonfromcollectionsimportdefaultdict,dequeclassOnlineUsers:def__init__(self):self.city_users=defaultdict(set)self.time_window=deque()defadd_log(self,user_id,city,timestamp):iftimestamp-self.time_window[0]>243600:self.time_window.popleft()forusersinself.city_users.values():users.discard(user_id)ifcitynotinself.city_users:self.city_users[city]=set()ifuser_idnotinself.city_users[city]:self.city_users[city].add(user_id)self.time_window.append(timestamp)defquery_max_users(self,city):returnlen(self.city_users.get(city,set()))解析：-使用`defaultdict(set)`记录每个城市的在线用户集合。-使用`deque`维护时间窗口（24小时），定期移除过时的用户。-查询时直接返回该城市的在线用户数。-时间复杂度：O(1)查询，O(n)处理日志。2.（25分）题目：设计一个算法，支持用户上传图片并自动生成缩略图。假设图片的宽高比固定，且需要支持批量上传。要求：-输出缩略图的宽度和高度。-避免重复生成已存在的缩略图。-请描述算法思路，并用Python伪代码实现核心逻辑。示例：pythonupload_images([{"path":"image1.jpg","width":800,"height":600},{"path":"image1.jpg","width":800,"height":600},#重复{"path":"image2.jpg","width":1024,"height":768}])输出：image1.jpg:200x150image2.jpg:256x192答案与解析：答案：算法思路：1.使用哈希表记录已生成的缩略图尺寸（基于图片路径和宽高比）。2.上传时：-计算缩略图尺寸（保持宽高比）。-检查哈希表中是否存在该尺寸的缩略图，若存在则跳过；否则生成并记录。伪代码：pythondefupload_images(images):thumbnails={}forimageinimages:path=image["path"]width=image["width"]height=image["height"]aspect_ratio=width/heightthumbnail_width=200thumbnail_height=int(thumbnail_width/aspect_ratio)key=(path,thumbnail_width,thumbnail_height)ifkeynotinthumbnails:thumbnails[key]=(thumbnail_width,thumbnail_height)print(f"{path}:{thumbnail_width}x{thumbnail_height}")解析：-使用`thumbnails`哈希表记录已生成的缩略图尺寸。-计算缩略图尺寸时保持宽高比。-时间复杂度：O(n)，空间复杂度：O(n)。三、系统设计题（共1题，25分）1.（25分）题目：设计一个实时推荐系统，用户在浏览商品时，系统需要根据用户的历史行为（如点击、加购、购买）和当前浏览的商品，实时推荐相关的商品。要求：-描述系统架构。-说明关键技术选型。-分析可能的挑战和解决方案。答案与解析：答案：系统架构：1.数据采集层：-用户行为日志（点击、加购、购买）通过埋点收集，实时传输到消息队列（如Kafka）。2.数据处理层：-消息队列接入流处理框架（如Flink），实时处理日志，更新用户画像和商品关联信息。3.推荐服务层：-实时推荐服务（如基于规则的推荐、协同过滤、深度学习模型），根据用户画像和当前商品生成推荐列表。4.缓存层：-Redis缓存热门推荐结果，降低后端计算压力。5.前端展示层：-用户浏览商品时，前端请求推荐服务，返回推荐列表。关键技术选型：-消息队列：Kafka，高吞吐量、低延迟。-流处理框架：Flink，实时数据处理。-推荐算法：-协同过滤（基于用户/商品的相似度）。-深度学习模型（如GraphNeuralNetwork，处理复杂关联）。-缓存：Redis，高并发访问。挑战与解决方案：1.实时性：-挑战：用户行为快速变化，