小米公司校招面試題與答案解析一、編程題（共3題，每題10分，總計30分）題目1：請實現(xiàn)一個函數(shù)，輸入一個正整數(shù)n，輸出n的階乘。要求不使用遞歸，時間復(fù)雜度盡可能低。答案解析：pythondeffactorial(n):result=1foriinrange(1,n+1):result=ireturnresult解析：-時間復(fù)雜度：O(n)，通過循環(huán)從1乘到n，避免了遞歸帶來的棧溢出問題。-空間復(fù)雜度：O(1)，僅使用常量級額外空間存儲結(jié)果。-優(yōu)化點：若n特別大，可考慮使用高精度計算庫（如Python的`decimal`），但校招通常默認(rèn)標(biāo)準(zhǔn)整型。題目2：給定一個字符串s，統(tǒng)計其中字母和數(shù)字的個數(shù)，字母區(qū)分大小寫，數(shù)字區(qū)分0-9。要求輸出為一個字典，鍵為"letters"和"digits"，值為對應(yīng)數(shù)量。答案解析：pythondefcount_letters_digits(s):count={"letters":0,"digits":0}forcharins:ifchar.isalpha():count["letters"]+=1elifchar.isdigit():count["digits"]+=1returncount解析：-時間復(fù)雜度：O(n)，遍歷字符串一次。-關(guān)鍵點：`isalpha()`和`isdigit()`是Python內(nèi)置方法，校招可放心使用。-邊界處理：空字符串返回`{"letters":0,"digits":0}`，無需額外判斷。題目3：實現(xiàn)一個函數(shù)，輸入一個列表，返回列表中的最大值，但要求不能使用內(nèi)置的`max()`函數(shù)。答案解析：pythondeffind_max(lst):ifnotlst:returnNone#處理空列表max_value=lst[0]fornuminlst[1:]:ifnum>max_value:max_value=numreturnmax_value解析：-時間復(fù)雜度：O(n)，線性遍歷列表。-空間復(fù)雜度：O(1)，僅使用常量級空間。-優(yōu)化點：若列表為空，返回`None`或拋異常，需根據(jù)需求調(diào)整。二、算法題（共4題，每題10分，總計40分）題目1：給定一個無重復(fù)元素的數(shù)組nums和一個目標(biāo)值target，返回所有相加等于target的數(shù)字對。例如，nums=[2,7,11,15],target=9，返回`[[2,7]]`。答案解析：pythondeftwo_sum(nums,target):num_dict={}result=[]fornuminnums:complement=target-numifcomplementinnum_dict:result.append([complement,num])num_dict[num]=Truereturnresult解析：-時間復(fù)雜度：O(n)，通過哈希表實現(xiàn)單次遍歷。-空間復(fù)雜度：O(n)，存儲每個數(shù)字的哈希表。-關(guān)鍵點：使用字典記錄已遍歷的數(shù)字，避免重復(fù)計算。題目2：實現(xiàn)一個函數(shù)，輸入一個正整數(shù)n，判斷其是否為素數(shù)。答案解析：pythondefis_prime(n):ifn<=1:returnFalseifn<=3:returnTrueifn%2==0orn%3==0:returnFalsei=5whileii<=n:ifn%i==0orn%(i+2)==0:returnFalsei+=6returnTrue解析：-優(yōu)化點：-排除偶數(shù)和能被3整除的數(shù)，減少后續(xù)判斷次數(shù)。-只需檢查到√n即可，因為若n有大于√n的因數(shù)，必存在小于√n的配對因數(shù)。-時間復(fù)雜度：O(√n)。題目3：給定一個字符串s，找到其中最長的不重復(fù)子串的長度。例如，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解析：-滑動窗口法：-左右指針分別表示子串的左右邊界。-遇到重復(fù)字符時，移動左指針并移除對應(yīng)字符。-時間復(fù)雜度：O(n)，每個字符最多被訪問兩次。題目4：實現(xiàn)一個函數(shù)，輸入一個鏈表，返回其反轉(zhuǎn)后的鏈表。答案解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_linked_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：-迭代法：-使用三個指針`prev`、`current`、`next_node`。-每次將當(dāng)前節(jié)點的`next`指向前一個節(jié)點。-時間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)。三、系統(tǒng)設(shè)計題（共2題，每題15分，總計30分）題目1：設(shè)計一個簡單的微博系統(tǒng)，需要支持以下功能：1.用戶發(fā)布微博（含文本內(nèi)容、時間戳）。2.用戶關(guān)注其他用戶。3.用戶查看自己關(guān)注的人的最新微博。答案解析：核心模塊設(shè)計：1.用戶表（User）：-`user_id`（主鍵）、`username`、`password`（加密存儲）。2.微博表（Tweet）：-`tweet_id`（主鍵）、`user_id`（外鍵）、`content`、`timestamp`。3.關(guān)注表（Follow）：-`follower_id`、`followee_id`（外鍵），聯(lián)合主鍵。功能實現(xiàn)：-發(fā)布微博：向`Tweet`表插入數(shù)據(jù)，`user_id`關(guān)聯(lián)用戶。-關(guān)注用戶：向`Follow`表插入數(shù)據(jù)。-查看微博：-查詢`Follow`表獲取當(dāng)前用戶關(guān)注的人的`user_id`。-按`user_id`和`timestamp`降序查詢`Tweet`表，返回最新5條（可擴展）。數(shù)據(jù)庫選型建議：-關(guān)系型數(shù)據(jù)庫（如MySQL）：適合事務(wù)性操作（如關(guān)注、發(fā)布）。-緩存（如Redis）：緩存熱門用戶微博，提升讀取性能。優(yōu)化點：-分頁加載：查看微博時支持`limit`分頁。-實時性：可用WebSocket推送新微博。題目2：設(shè)計一個短鏈接系統(tǒng)（如tinyurl），要求：1.輸入長鏈接，生成短鏈接。2.輸入短鏈接，返回對應(yīng)長鏈接。答案解析：核心設(shè)計：1.短鏈接表（ShortLink）：-`short_id`（主鍵，如6位隨機字母數(shù)字組合）、`long_url`、`created_at`。2.映射關(guān)系：使用哈希函數(shù)或隨機生成短ID。實現(xiàn)步驟：-生成短鏈接：-對`long_url`做MD5或SHA256，取前6位作為`short_id`。-若沖突，重新生成。-存儲`short_id`和`long_url`。-解析短鏈接：-根據(jù)`short_id`查詢`long_url`，返回結(jié)果。技術(shù)選型：-前端：HTTP重定向（301/302）。-后端：-存儲：Redis（高速查詢）或MySQL（持久化）。-ID生成：可用`base62`編碼（a-zA-Z0-9）。優(yōu)化點：-沖突處理：使用隨機算法（如UUID取后6位）減少沖突。-緩存：將熱門短鏈接緩存到內(nèi)存。四、行為面試題（共3題，每題10分，總計30分）題目1：請分享一次你解決過的最復(fù)雜的團(tuán)隊合作問題，你是如何處理的？參考回答：-背景：描述項目中的沖突（如成員意見分歧、進(jìn)度延誤）。-行動：-組織會議，讓各方表達(dá)觀點。-提出折中方案（如分工優(yōu)化、技術(shù)選型調(diào)整）。-跟進(jìn)任務(wù)分配，定期檢查進(jìn)度。-結(jié)果：團(tuán)隊達(dá)成共識，項目按時完成。題目2：你為什么選擇加入小米？參考回答：-結(jié)合小米業(yè)務(wù)：如對消費電子、AIoT的興趣。