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

2026年互联网公司算法工程师面试问题及答案一、编程基础（共5题，每题10分，总分50分）1.题目：请实现一个函数，输入一个非负整数n，返回它的二进制表示中1的个数。例如，输入5，返回2，因为5的二进制表示为101。答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount解析：通过位运算，每次将n右移一位，并统计最低位的1的个数，直到n为0。2.题目：请实现一个函数，输入一个字符串s，返回s的子串中不包含重复字符的最长子串的长度。例如，输入"abcabcbb"，返回3，因为"abc"是长度最长的无重复字符子串。答案：pythondeflength_of_longest_substring(s):char_set=set()left=0max_length=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_length=max(max_length,right-left+1)returnmax_length解析：使用滑动窗口技术，左指针和右指针分别表示当前子串的左右边界，通过维护一个集合记录当前子串中的字符，当遇到重复字符时，移动左指针并更新最大长度。3.题目：请实现一个函数，输入一个链表的头节点head，返回链表的中间节点。如果链表中有两个中间节点，返回第二个中间节点。例如，输入1->2->3->4->5，返回3；输入1->2->3->4->5->6，返回4。答案：pythondefmiddle_node(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextreturnslow解析：使用快慢指针法，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好在中间位置。4.题目：请实现一个函数，输入一个正整数n，判断它是否是偶数。如果是，返回True；否则，返回False。答案：pythondefis_even(n):returnn%2==0解析：通过取模运算判断n是否能被2整除，如果能，则是偶数；否则，是奇数。5.题目：请实现一个函数，输入一个字符串s，返回s的翻转。例如，输入"hello"，返回"olleh"。答案：pythondefreverse_string(s):returns[::-1]解析：使用Python的切片操作，`s[::-1]`表示从后往前逐个字符取值，实现字符串翻转。二、数据结构与算法（共5题，每题10分，总分50分）1.题目：请实现一个函数，输入一个非空数组nums和一个目标值target，返回数组中和为target的三个数的组合。例如，输入nums=[-1,0,1,2]，target=0，返回[[-1,0,1]]。答案：pythondefthree_sum(nums,target):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==target:result.append([nums[i],nums[left],nums[right]])left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1eliftotal<target:left+=1else:right-=1returnresult解析：先对数组排序，然后使用双指针法，固定一个数，另两个数通过双指针查找，确保不重复。2.题目：请实现一个函数，输入一个非空链表，返回链表的反转。例如，输入1->2->3->4->5，返回5->4->3->2->1。答案：pythondefreverse_linked_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：使用迭代法反转链表，维护三个指针：prev、current和next_node，逐个反转节点。3.题目：请实现一个函数，输入一个非空数组nums，返回数组中的众数。众数是指在数组中出现次数最多的元素。例如，输入[3,2,3]，返回[3]。答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：使用Boyer-Moore投票算法，维护一个候选者和计数器，遍历数组时更新候选者和计数器。4.题目：请实现一个函数，输入一个字符串s，返回s的字典序排列。例如，输入"cba"，返回"abc"。答案：pythondefsorted_string(s):return''.join(sorted(s))解析：使用Python的内置排序函数，对字符串进行排序并拼接。5.题目：请实现一个函数，输入一个非空数组nums，返回数组中的最大子数组和。例如，输入[-2,1,-3,4,-1,2,1,-5,4]，返回6，因为子数组[4,-1,2,1]的和最大。答案：pythondefmax_subarray(nums):max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum解析：使用Kadane算法，维护两个变量：current_sum和max_sum，当前子数组和最大子数组和。三、系统设计（共5题，每题10分，总分50分）1.题目：请设计一个简单的URL短链接系统，要求能够将长URL转换为短URL，并能够将短URL解析回长URL。答案：-数据结构：使用哈希表存储长URL和短URL的映射关系。-算法：将长URL通过哈希函数生成短URL，短URL可以是随机生成的字符串。-伪代码：pythonclassURLShortener:def__init__(self):self.url_map={}self.base_url="http://short.url/"defshorten(self,long_url):short_key=self._generate_short_key()self.url_map[short_key]=long_urlreturnself.base_url+short_keydefrestore(self,short_url):short_key=short_url.split('/')[-1]returnself.url_map.get(short_key,None)def_generate_short_key(self):importuuidreturnstr(uuid.uuid4())解析：使用哈希表存储长URL和短URL的映射关系，通过随机生成的字符串作为短URL，确保唯一性。2.题目：请设计一个简单的微博系统，要求支持用户发布微博、关注用户、查看关注用户的微博。答案：-数据结构：使用哈希表存储用户信息，使用图结构存储关注关系。-算法：用户发布微博时，将微博存入数据库，并更新用户的微博列表；关注用户时，更新用户和被关注用户的关注关系；查看关注用户的微博时，遍历关注关系并获取微博。-伪代码：pythonclassWeiboSystem:def__init__(self):self.users={}self.followees={}defpost_weibo(self,user_id,content):ifuser_idnotinself.users:self.users[user_id]={'weibos':[]}self.users[user_id]['weibos'].append(content)deffollow(self,user_id,followee_id):ifuser_idnotinself.followees:self.followees[user_id]=set()self.followees[user_id].add(followee_id)defget_weibos(self,user_id):weibos=[]ifuser_idinself.followees:forfolloweeinself.followees[user_id]:iffolloweeinself.users:weibos.extend(self.users[followee]['weibos'])returnweibos解析：使用哈希表存储用户信息和微博，使用图结构存储关注关系，通过遍历关注关系获取关注用户的微博。3.题目：请设计一个简单的新闻推荐系统，要求根据用户的历史行为推荐新闻。答案：-数据结构：使用哈希表存储用户行为数据，使用协同过滤算法进行推荐。-算法：收集用户的历史行为数据，如点击、阅读等，使用协同过滤算法计算用户相似度，根据相似用户的偏好推荐新闻。-伪代码：pythonclassNewsRecommender:def__init__(self):self.user_behavior={}self.news_rating={}defrecord_behavior(self,user_id,news_id,action):ifuser_idnotinself.user_behavior:self.user_behavior[user_id]={}self.user_behavior[user_id][news_id]=actiondefrecommend(self,user_id,top_n=5):ratings={}fornews_id,actioninself.user_behavior[user_id].items():forother_user_id,other_ratingsinself.user_behavior.items():ifother_user_id!=user_idandnews_idinother_ratings:ratings[news_id]=ratings.get(news_id,0)+other_ratings[news_id]returnsorted(ratings,key=ratings.get,reverse=True)[:top_n]解析：使用哈希表存储用户行为数据，通过协同过滤算法计算用户相似度，根据相似用户的偏好推荐新闻。4.题目：请设计一个简单的即时通讯系统，要求支持用户注册、登录、发送消息。答案：-数据结构：使用哈希表存储用户信息，使用WebSocket或长轮询技术实现实时消息传输。-算法：用户注册时，将用户信息存入数据库；用户登录时，验证用户信息并生成会话；发送消息时，通过WebSocket或长轮询技术实时传输消息。-伪代码：pythonclassChatSystem:def__init__(self):self.users={}self.messages=[]defregister(self,user_id,password):self.users[user_id]={'password':password}deflogin(self,user_id,password):ifuser_idinself.usersandself.users[user_id]['password']==password:returnTruereturnFalsedefsend_message(self,sender_id,receiver_id,content):message={'sender_id':sender_id,'receiver_id':receiver_id,'content':content}self.messages.append(message)实时传输消息self._deliver_message(message)def_deliver_message(self,message):实现消息传输逻辑pass解析：使用哈希表存储用户信息，通过WebSocket或长轮询技术实现实时消息传输，确保消息的实时性