小米技术岗面试题概览与答案详解

小米技术岗面试题概览与答案详解一、编程语言与基础算法（15题，共75分）1.（5分）编写一个函数，实现快速排序算法。输入一个整数数组，输出排序后的数组。答案与解析：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：快速排序通过分治法实现，选择一个基准值（pivot），将数组分为小于、等于、大于三部分，递归排序左右两部分。2.（5分）实现一个函数，检查一个字符串是否是回文串（忽略大小写和非字母字符）。答案与解析：pythondefis_palindrome(s):s=''.join(c.lower()forcinsifc.isalnum())returns==s[::-1]解析：先过滤非字母字符并转为小写，再检查字符串是否对称。3.（10分）给定一个数组，找出其中不重复的三元组，使得三元组的和为0。答案与解析：pythondefthree_sum(nums):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==0: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<0:left+=1else:right-=1returnresult解析：排序后固定一个数，双指针查找另外两个数，避免重复解。4.（10分）实现一个二叉树的深度优先遍历（前序、中序、后序）。答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorder_traversal(root):result=[]defdfs(node):ifnotnode:returnresult.append(node.val)dfs(node.left)dfs(node.right)dfs(root)returnresultdefinorder_traversal(root):result=[]defdfs(node):ifnotnode:returndfs(node.left)result.append(node.val)dfs(node.right)dfs(root)returnresultdefpostorder_traversal(root):result=[]defdfs(node):ifnotnode:returndfs(node.left)dfs(node.right)result.append(node.val)dfs(root)returnresult解析：前序根左右，中序左根右，后序左右根。5.（5分）实现一个函数，检查一个链表是否存在环。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefhas_cycle(head):slow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse解析：快慢指针，快指针每次两步，慢指针一步，相遇则存在环。6.（5分）编写一个函数，反转一个链表。答案与解析：pythondefreverse_list(head):prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev解析：迭代反转，保存next节点。7.（10分）实现一个函数，找出一个无重复字符的最长子串。答案与解析：pythondeflength_of_longest_substring(s):char_map={}start=0max_len=0forend,charinenumerate(s):ifcharinchar_mapandchar_map[char]>=start:start=char_map[char]+1char_map[char]=endmax_len=max(max_len,end-start+1)returnmax_len解析：滑动窗口，记录字符上一次出现的位置，动态调整窗口。8.（10分）实现一个函数，合并多个有序链表。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmerge_k_lists(lists):ifnotlists:returnNonedefmerge_two_lists(l1,l2):dummy=ListNode(0)curr=dummywhilel1andl2:ifl1.val<l2.val:curr.next=l1l1=l1.nextelse:curr.next=l2l2=l2.nextcurr=curr.nextcurr.next=l1orl2returndummy.nextwhilelen(lists)>1:merged=[]foriinrange(0,len(lists),2):l1=lists[i]l2=lists[i+1]ifi+1<len(lists)elseNonemerged.append(merge_two_lists(l1,l2))lists=mergedreturnlists[0]解析：分治法合并，每次合并两个链表。9.（5分）编写一个函数，计算斐波那契数列的第n项。答案与解析：pythondeffib(n):ifn<=1:returnna,b=0,1for_inrange(2,n+1):a,b=b,a+breturnb解析：动态规划，空间复杂度O(1)。10.（5分）实现一个函数，找出一个字符串的所有字母异位词。答案与解析：pythonfromcollectionsimportCounterdeffind_anagrams(s,p):result=[]len_p=len(p)len_s=len(s)iflen_p>len_s:returnresultp_count=Counter(p)s_count=Counter(s[:len_p])ifp_count==s_count:result.append(0)foriinrange(len_p,len_s):s_count[s[i]]+=1s_count[s[i-len_p]]-=1ifs_count[s[i-len_p]]==0:dels_count[s[i-len_p]]ifp_count==s_count:result.append(i-len_p+1)returnresult解析：滑动窗口，统计字符频率。11.（10分）实现一个函数，判断一个数是否是快乐数。答案与解析：pythondefis_happy(n):seen=set()whilen!=1andnnotinseen:seen.add(n)n=sum(int(digit)2fordigitinstr(n))returnn==1解析：循环求各位平方和，判断是否进入1或循环。12.（10分）实现一个函数，找出一个数组中的所有唯一二叉搜索树（BST）的结构。答案与解析：pythonfromitertoolsimportproductdefgenerate_unique_bsts(n):defgenerate_trees(start,end):ifstart>end:return[None]all_trees=[]forroot_valinrange(start,end+1):left_trees=generate_trees(start,root_val-1)right_trees=generate_trees(root_val+1,end)forleftinleft_trees:forrightinright_trees:root=TreeNode(root_val)root.left=leftroot.right=rightall_trees.append(root)returnall_treesreturngenerate_trees(1,n)classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right解析：递归生成所有可能的BST，组合左右子树。13.（5分）编写一个函数，找出一个字符串的最长公共前缀。答案与解析：pythondeflongest_common_prefix(strs):ifnotstrs:return""prefix=strs[0]forsinstrs[1:]:whilenots.startswith(prefix):prefix=prefix[:-1]ifnotprefix:return""returnprefix解析：从第一个字符串开始，逐个比较，缩短前缀。14.（10分）实现一个函数，找出一个无重复字符的最长子序列。答案与解析：pythondeflength_of_longest_subsequence(s):char_index={}max_len=0start=0fori,charinenumerate(s):ifcharinchar_index:start=max(start,char_index[char]+1)char_index[char]=imax_len=max(max_len,i-start+1)returnmax_len解析：动态规划，记录字符上次出现位置，更新最长子序列。15.（5分）编写一个函数，判断一个数是否是完美数（等于其所有正因子之和）。答案与解析：pythondefis_perfect_number(num):ifnum<=1:returnFalsesum_factors=1foriinrange(2,int(num0.5)+1):ifnum%i==0:sum_factors+=iifi!=num//i:sum_factors+=num//ireturnsum_factors==num解析：遍历到sqrt(num)，统计因子。二、系统设计（5题，共100分）1.（20分）设计一个微博系统，要求支持实时发布、关注、取消关注、查看时间线等功能。答案与解析：设计要点：1.数据存储：-用户表：存储用户信息。-关注关系表：存储用户关注关系。-微博表：存储微博内容，包括发布时间、用户ID、内容等。-评论表：存储微博评论。-点赞表：存储微博点赞关系。2.实时发布：-使用消息队列（如Kafka）处理发布请求，确保高并发。-微博表使用分区和索引优化查询。3.关注功能：-关注关系表使用索引优化查询。-使用Redis缓存用户关注列表。4.时间线：-使用Redis订阅关注用户发布事件，实时更新时间线。-时间线按发布时间倒序排列。5.性能优化：-使用CDN加速静态资源加载。-使用分页加载减少数据传输。2.（20分）设计一个短链接系统，要求支持长链接转短链接、短链接跳转长链接、统计短链接访问次数等功能。答案与解析：设计要点：1.数据存储：-短链接表：存储短链接ID、长链接、创建时间、访问次数等。2.短链接生成：-使用哈希算法（如SHA256）生成短链接ID。-使用Base62编码缩短ID长度。3.跳转功能：-使用内存缓存（如Redis）加速短链接查询。-使用分布式缓存处理高并发。4.统计功能：-每次跳转时更新访问次数。-使用Redis进行实时统计。5.性能优化：-使用负载均衡分发请求。-使用CDN缓存短链接数据。3.（20分）设计一个在线音乐播放系统，要求支持歌曲播放、随机播放、歌单创建、点赞等功能。答案与解析：设计要点：1.数据存储：-歌曲表：存储歌曲信息，包括封面、播放时长等。-用户表：存储用户信息。-歌单表：存储歌单信息。-播放记录表：存储用户播放记录。-点赞表：存储用户点赞关系。2.播放功能：-使用流式传输（如HLS）支持断点续播。-使用缓存（如CDN）加速音乐加载。3.随机播放：-使用随机算法（如Fisher-Yates）生成随机播放列表。-使用Redis缓存随机播放列表。4.歌单创建：-使用Redis缓存歌单信息。-使用消息队列处理歌单