小米面試題集與實戰(zhàn)策略解析一、編程題（共3題，每題20分）1.編寫一個Python函數(shù)，實現(xiàn)快速排序算法題目描述：請編寫一個Python函數(shù)`quick_sort(arr)`，實現(xiàn)快速排序算法。輸入?yún)?shù)`arr`是一個整數(shù)列表，函數(shù)返回排序后的列表。要求使用遞歸方式實現(xiàn)，并給出測試用例。答案：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)測試用例print(quick_sort([3,6,8,10,1,2,1]))#輸出:[1,1,2,3,6,8,10]解析：快速排序的核心思想是選擇一個基準值（pivot），將數(shù)組分為小于、等于、大于基準值的三部分，然后遞歸地對小于和大于基準值的部分進行排序。時間復雜度為O(nlogn)，空間復雜度為O(logn)。測試用例驗證了函數(shù)的正確性，能夠處理包含重復元素的列表。2.編寫一個Java方法，實現(xiàn)二叉樹的深度優(yōu)先遍歷（前序遍歷）題目描述：請編寫一個Java方法`preOrderTraversal(TreeNoderoot)`，實現(xiàn)二叉樹的前序遍歷。輸入?yún)?shù)`root`是二叉樹的根節(jié)點，返回遍歷結果的字符串表示（用逗號分隔）。假設二叉樹節(jié)點定義如下：javaclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}答案：javapublicclassBinaryTree{publicstaticStringpreOrderTraversal(TreeNoderoot){StringBuildersb=newStringBuilder();preOrder(root,sb);returnsb.toString().trim();}privatestaticvoidpreOrder(TreeNodenode,StringBuildersb){if(node==null)return;sb.append(node.val).append(",");preOrder(node.left,sb);preOrder(node.right,sb);}publicstaticvoidmain(String[]args){TreeNoderoot=newTreeNode(1);root.left=newTreeNode(2);root.right=newTreeNode(3);root.left.left=newTreeNode(4);root.left.right=newTreeNode(5);System.out.println(preOrderTraversal(root));//輸出:1,2,4,5,3}}解析：前序遍歷的順序是：根節(jié)點->左子樹->右子樹。通過遞歸實現(xiàn)，每次訪問當前節(jié)點時先處理，然后遍歷左子樹和右子樹。測試用例構建了一個簡單的二叉樹，驗證了前序遍歷的正確性。3.編寫一個JavaScript函數(shù)，實現(xiàn)鏈表的合并題目描述：請編寫一個JavaScript函數(shù)`mergeLists(l1,l2)`，合并兩個有序鏈表，返回合并后的頭節(jié)點。假設鏈表節(jié)點定義如下：javascriptclassListNode{constructor(val=0,next=null){this.val=val;this.next=next;}}答案：javascriptfunctionmergeLists(l1,l2){letdummy=newListNode();letcurrent=dummy;while(l1&&l2){if(l1.val<l2.val){current.next=l1;l1=l1.next;}else{current.next=l2;l2=l2.next;}current=current.next;}if(l1)current.next=l1;if(l2)current.next=l2;returndummy.next;}//測試用例letl1=newListNode(1,newListNode(3,newListNode(5)));letl2=newListNode(2,newListNode(4,newListNode(6)));letmerged=mergeLists(l1,l2);while(merged){console.log(merged.val);//輸出:1,2,3,4,5,6merged=merged.next;}解析：合并兩個有序鏈表時，可以使用虛擬頭節(jié)點簡化邊界處理。遍歷兩個鏈表，每次選擇較小的節(jié)點連接到合并后的鏈表，直到一個鏈表為空，然后將另一個鏈表的剩余部分直接連接。時間復雜度為O(n)，空間復雜度為O(1)。二、算法題（共4題，每題15分）1.尋找無重復字符的最長子串題目描述：給定一個字符串`s`，找出其中不含有重復字符的最長子串的長度。例如，`s="abcabcbb"`，返回`3`（"abc"`）。答案：pythondeflengthOfLongestSubstring(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(lengthOfLongestSubstring("abcabcbb"))#輸出:3解析：使用滑動窗口技術，左指針`left`和右指針`right`分別表示窗口的左右邊界。遍歷字符串時，如果當前字符`right`在窗口中，則移動左指針并移除字符，直到窗口中沒有重復字符。每次更新最大長度`max_len`。時間復雜度為O(n)，空間復雜度為O(min(m,n))，其中m是字符集大小。2.爬樓梯問題題目描述：假設你正在爬樓梯，每次可以爬1或2級臺階。給定總臺階數(shù)`n`，計算有多少種不同的爬法。例如，`n=3`，返回`3`（"1+1+1"、"1+2"、"2+1"）。答案：pythondefclimbStairs(n):ifn==1:return1dp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]測試用例print(climbStairs(3))#輸出:3解析：這是一個典型的動態(tài)規(guī)劃問題，`dp[i]`表示到達第`i`級臺階的爬法數(shù)量。狀態(tài)轉移方程為`dp[i]=dp[i-1]+dp[i-2]`，因為每次可以爬1或2級。初始條件為`dp[1]=1`和`dp[2]=2`。時間復雜度為O(n)，空間復雜度為O(n)。3.反轉整數(shù)題目描述：編寫一個函數(shù)`reverse(x)`，將32位整數(shù)`x`反轉。假設環(huán)境不允許存儲64位整數(shù)，如果反轉后溢出則返回`0`。例如，`x=123`，返回`321`；`x=-123`，返回`-321`。答案：pythondefreverse(x):INT_MAX=231-1INT_MIN=-231rev=0whilex!=0:pop=x%10x//=10ifrev>INT_MAX//10or(rev==INT_MAX//10andpop>7):return0ifrev<INT_MIN//10or(rev==INT_MIN//10andpop<-8):return0rev=rev10+popreturnrev測試用例print(reverse(123))#輸出:321print(reverse(-123))#輸出:-321print(reverse(120))#輸出:21解析：通過不斷取模和除法操作，逐位反轉整數(shù)。每次反轉前檢查是否會導致溢出，即`rev10+pop`是否在32位整數(shù)范圍內(nèi)。如果溢出則返回`0`。時間復雜度為O(log(x))，空間復雜度為O(1)。4.N皇后問題題目描述：編寫一個函數(shù)`solveNQueens(n)`，解決N皇后問題。返回所有不同的解決方案的列表。每個解決方案包含一個字符列表，其中`'Q'`表示皇后位置，`'.'`表示空位。例如，`n=4`，返回兩個解決方案：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]答案：pythondefsolveNQueens(n):defbacktrack(row,diagonals,anti_diagonals,cols,state):ifrow==n:result.append(state.copy())returnforcolinrange(n):diag=row-colanti_diag=row+colif(colincolsordiagindiagonalsoranti_diaginanti_diagonals):continuecols.add(col)diagonals.add(diag)anti_diagonals.add(anti_diag)state.append('.'col+'Q'+'.'(n-col-1))backtrack(row+1,diagonals,anti_diagonals,cols,state)cols.remove(col)diagonals.remove(diag)anti_diagonals.remove(anti_diag)state.pop()result=[]backtrack(0,set(),set(),set(),[])returnresult測試用例print(solveNQueens(4))解析：使用回溯算法解決N皇后問題。通過維護三個集合分別記錄列、主對角線和副對角線的占用情況，避免皇后沖突。每次嘗試在當前行放置皇后，如果不沖突則遞歸到下一行。最終將所有解決方案存儲在`result`中。時間復雜度為O(N!)，空間復雜度為O(N)。三、系統(tǒng)設計題（共2題，每題25分）1.設計一個短鏈接系統(tǒng)題目描述：設計一個短鏈接系統(tǒng)，用戶可以輸入長鏈接，系統(tǒng)返回一個短鏈接，點擊短鏈接后可以跳轉到對應的長鏈接。要求：1.短鏈接長度盡可能短（6位字符）；2.支持高并發(fā)訪問；3.能夠統(tǒng)計每個短鏈接的點擊次數(shù)。答案：1.數(shù)據(jù)結構：-使用哈希表存儲短鏈接與長鏈接的映射（`short_to_long`）；-使用哈希表存儲短鏈接與點擊次數(shù)的映射（`short_to_clicks`）；-使用自增ID生成短鏈接，并通過哈希函數(shù)將ID映射為6位短碼。2.短鏈接生成：-使用自增ID作為唯一標識；-將ID通過哈希函數(shù)（如CRC32）映射為62進制字符（a-z,A-Z,0-9）；-不足6位時進行補全。3.高并發(fā)支持：-使用Redis等內(nèi)存數(shù)據(jù)庫存儲映射關系，提高讀寫性能；-使用分布式鎖或CAS操作保證ID生成和映射的一致性。4.點擊統(tǒng)計：-每次訪問短鏈接時，更新`short_to_clicks`中的點擊次數(shù)；-使用Redis的原子操作確保計數(shù)準確性。5.系統(tǒng)架構：-前端：接收長鏈接請求，生成短鏈接并返回；-后端：存儲映射關系，處理跳轉請求；-緩存層：Redis緩存熱點數(shù)據(jù)。解析：短鏈接系統(tǒng)核心在于高效映射和并發(fā)控制。通過自增ID和哈希函數(shù)生成短碼，結合內(nèi)存數(shù)據(jù)庫和原子操作，保證系統(tǒng)高性能和一致性。點擊統(tǒng)計通過Redis原子更新實現(xiàn)。架構設計需考慮可擴展性和容錯性。2.設計一個微博系統(tǒng)題目描述：設計一個微博系統(tǒng)，用戶可以發(fā)布微博、關注/取消關注其他用戶、獲取關注用戶的動態(tài)。要求：1.支持百萬級用戶和動態(tài)；2.微博發(fā)布和獲取動態(tài)需要高性能；3.關注關系支持實時更新。答案：1.數(shù)據(jù)結構：-用戶表（`use