版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
小米面试编程题及答案详解一、编程基础题(共3题,每题10分)1.题目(10分):编写一个函数,输入一个正整数`n`,返回`n`的所有因子(包括1和`n`本身),并按从小到大的顺序排列。示例:输入:`n=12`输出:`[1,2,3,4,6,12]`答案与解析:pythondeffind_factors(n):factors=[]foriinrange(1,n+1):ifn%i==0:factors.append(i)returnfactors测试print(find_factors(12))#输出:[1,2,3,4,6,12]解析:-遍历从1到`n`的所有数字,检查是否能整除`n`。-若能整除,则该数字是`n`的因子,加入列表中。-最后返回排序后的因子列表。2.题目(10分):实现一个`merge_intervals`函数,输入一个包含多个区间的列表(每个区间是`[start,end]`的列表),合并所有重叠或相邻的区间,并返回合并后的结果。示例:输入:`[[1,3],[2,6],[8,10]]`输出:`[[1,6],[8,10]]`答案与解析:pythondefmerge_intervals(intervals):ifnotintervals:return[]按区间的起始位置排序intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:#重叠或相邻last[1]=max(last[1],current[1])else:merged.append(current)returnmerged测试print(merge_intervals([[1,3],[2,6],[8,10]]))#输出:[[1,6],[8,10]]解析:-首先按区间的起始位置排序,确保可以按顺序合并。-初始化`merged`列表,存储合并后的区间。-遍历每个区间,若当前区间的起始位置≤前一个区间的结束位置,则合并(更新结束位置);否则,添加新区间。3.题目(10分):编写一个函数,输入一个字符串`s`,返回`s`中不重复字符的最长子串的长度。示例:输入:`"abcabcbb"`输出:`3`(最长子串为"abc")答案与解析:pythondeflength_of_longest_substring(s):char_set=set()left=0max_len=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len测试print(length_of_longest_substring("abcabcbb"))#输出:3解析:-使用滑动窗口技术,`left`和`right`分别表示窗口的左右边界。-遍历字符串,若`s[right]`已存在于窗口中,则移动`left`并移除`s[left]`,直到`s[right]`不再重复。-更新最大长度`max_len`。二、算法与数据结构题(共4题,每题15分)1.题目(15分):给定一个包含`n`个节点的无向图,使用邻接矩阵表示。编写一个函数,判断该图是否是二分图(即可以分成两个集合,使得每条边的两个节点属于不同集合)。示例:邻接矩阵:0101101001011010输出:`True`(可以分成集合`{0,2}`和`{1,3}`)答案与解析:pythondefis_bipartite(matrix):n=len(matrix)color=[-1]n#-1表示未染色defdfs(node,c):color[node]=cforneighborinrange(n):ifmatrix[node][neighbor]==1:ifcolor[neighbor]==-1:ifnotdfs(neighbor,1-c):returnFalseelifcolor[neighbor]==c:returnFalsereturnTrueforiinrange(n):ifcolor[i]==-1:ifnotdfs(i,0):returnFalsereturnTrue测试matrix=[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]print(is_bipartite(matrix))#输出:True解析:-使用深度优先搜索(DFS)染色,`color[node]`表示节点的颜色(0或1)。-若发现相邻节点颜色相同,则不是二分图。-遍历所有节点,确保每个连通分量都满足二分图条件。2.题目(15分):实现一个LRU(最近最少使用)缓存,支持`get`和`put`操作。缓存容量为`capacity`。示例: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)self.cache[key]=valueself.order.append(key)iflen(self.cache)>self.capacity:oldest=self.order.pop(0)delself.cache[oldest]测试lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#返回1lru.put(3,3)#去除键2print(lru.get(2))#返回-1答案与解析:-使用字典`cache`存储键值对,列表`order`记录访问顺序。-`get`操作:若键存在,将其移到`order`末尾(表示最近使用),返回值。-`put`操作:若键已存在,更新值并移动到末尾;若不存在,添加到`cache`和`order`。-若`cache`超过`capacity`,删除最旧的键(`order`的第一个元素)。3.题目(15分):给定一个整数数组`nums`,返回所有和为`target`的三元组`[nums[i],nums[j],nums[k]]`,且`i<j<k`。示例:输入:`nums=[-1,0,1,2,-1,-4]`,`target=0`输出:`[[-1,-1,2],[-1,0,1]]`答案与解析:pythondefthree_sum(nums,target):nums.sort()n=len(nums)result=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target: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<target:left+=1else:right-=1returnresult测试print(three_sum([-1,0,1,2,-1,-4],0))#输出:[[-1,-1,2],[-1,0,1]]解析:-先排序数组,便于跳过重复元素。-固定第一个数`nums[i]`,使用双指针`left`和`right`在剩余部分寻找和为`target-nums[i]`的两个数。-若找到,记录并跳过重复值;若和小于`target`,移动`left`;否则移动`right`。4.题目(15分):编写一个函数,输入一个字符串`s`,返回`s`中所有唯一字符的最长子串的长度。示例:输入:`"abcabcbb"`输出:`3`(最长子串为"abc")答案与解析:pythondeflength_of_longest_unique_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测试print(length_of_longest_unique_substring("abcabcbb"))#输出:3解析:-使用哈希表`char_map`记录字符的最新位置。-`left`表示当前无重复字符子串的起始位置。-遍历字符串,若`s[right]`已存在且位置≥`left`,则更新`left`为该位置加1。-更新最大长度`max_len`。三、系统设计题(共2题,每题20分)1.题目(20分):设计一个简单的URL缓存系统,支持以下操作:-`get(url)`:返回URL对应的内容,若未缓存则返回空字符串。-`put(url,content)`:缓存URL及其内容,若超出缓存容量则驱逐最久未使用的URL。缓存容量为`capacity`,假设每个URL的内容不超过100字符。要求:-时间复杂度:`get`和`put`均为O(1)。-可使用任何数据结构实现。答案与解析:pythonclassURLCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,url:str)->str:ifurlinself.cache:self.order.remove(url)self.order.append(url)returnself.cache[url]return""defput(self,url:str,content:str)->None:ifurlinself.cache:self.order.remove(url)self.cache[url]=contentself.order.append(url)iflen(self.cache)>self.capacity:oldest=self.order.pop(0)delself.cache[oldest]测试cache=URLCache(2)cache.put("url1","content1")cache.put("url2","content2")print(cache.get("url1"))#返回"content1"cache.put("url3","content3")#驱逐"url2"print(cache.get("url2"))#返回""解析:-使用字典`cache`存储URL及其内容,列表`order`记录访问顺序。-`get`操作:若URL存在,更新访问顺序并返回内容;否则返回空字符串。-`put`操作:若URL已存在,更新内容并移动到末尾;若不存在,添加到`cache`和`order`。-若超出容量,删除最旧的URL(`order`的第一个元素)。2.题目(20分):设计一个简单的微博系统,支持以下操作:-`post(user_id,content)`:用户发布一条微博,内容不超过280字符。-`follow(follower_id,followee_id)`:用户`follower_id`关注用户`followee_id`。-`getTimeline(user_id)`:返回用户`user_id`的微博时间线(包括自己和他关注的人的微博,按时间倒序排列)。要求:-`post`和`follow`操作需高效。-`getTimeline`操作的时间复杂度尽可能低(可适当牺牲`post`和`follow`的复杂度)。答案与解析:pythonfromcollectionsimportdefaultdict,dequeimporttimeclassWeiboSystem:def__init__(self):self.users=defaultdict(set)#user_id:setoffollowee_idsself.posts=defaultdict(list)#user_id:listof(timestamp,content)defpost(self,user_id:int,content:str)->None:timestamp=time.time()self.posts[user_id].append((timestamp,content))deffollow(self,follower_id:int,followee_id:int)->None:self.users[follower_id].add(followee_id)defgetTimeline(self
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年泵车安全题库带答案
- 2026年大学游泳考试题库及答案
- 2026年天津市保安员业务知识考试复习题库及参考答案
- 2026年网络安全应急响应培训模拟试卷及参考答案
- 2026年建筑八大员材料员专业题库带答案
- 2026年宝山编制考试题库(含答案)
- 2026年经济金融笔试题库及答案
- 天津市养老护理员技师培训模拟题及答案
- 2026年苍南县马站镇人民政府面向社会公开招聘工作人员考试题库(含答案)
- 2026年精神科护理学题库及答案
- 2025年石河子大学马克思主义基本原理概论期末考试真题汇编
- 2026年医疗保险审核部门面试题及应对策略
- 2026-2031中国法兰行业市场前景分析预测报告
- 施工便道临时方案
- 信息科技课程标准2025年版
- 眼科手术并发症处理规定
- 风机叶片覆冰安全培训课件
- 2025云南曲靖市人力资源和社会保障局招聘公益性岗位工作人员3人考试参考题库及答案解析
- 医院服务接待礼仪
- 《中职语文基础知识手册》全套教学课件
- 【MOOC】人工智能与信息社会-北京大学 中国大学慕课MOOC答案
评论
0/150
提交评论