2026年IT巨頭面試技巧：軟件開發(fā)人員筆試面試全攻略編程能力測試（15題，共75分）1.數(shù)組與字符串操作（3題，每題25分）題目1（25分）：給定一個字符串`s`和一個整數(shù)`k`，將字符串`s`中所有長度為`k`的子串反轉(zhuǎn)，其余字符保持不變。請實現(xiàn)該功能，并分析時間復(fù)雜度。示例輸入：`s="abcdefg",k=2`示例輸出：`"badcfeg"`要求：-不能使用額外的字符串或數(shù)組存儲空間-考慮`k`等于1和`s`為空的情況題目2（25分）：實現(xiàn)一個函數(shù)，找出數(shù)組中最長的連續(xù)遞增子數(shù)組，并返回其長度。如果存在多個最長連續(xù)遞增子數(shù)組，返回任意一個的長度。示例輸入：`arr=[1,3,5,4,7,9,2,6,8]`示例輸出：`5`（對應(yīng)子數(shù)組[4,7,9,2,6]）要求：-不能使用遞歸-考慮數(shù)組為空或所有元素相同的情況題目3（25分）：實現(xiàn)一個函數(shù)，判斷一個字符串是否是有效的括號組合。字符串中可能包含`'()[]{}'`四種括號。示例輸入：`"()[]{}"`示例輸出：`true`要求：-時間復(fù)雜度不超過O(n)-可以使用棧實現(xiàn)2.數(shù)據(jù)結(jié)構(gòu)與算法（6題，每題12分）題目4（12分）：實現(xiàn)一個LRU（最近最少使用）緩存，支持get和put操作。緩存容量為`capacity`，超出容量時需要刪除最久未使用的元素。示例輸入：`capacity=2``["LRUCache","put","put","get","put","get","get"]``[[],[1,1],[2,2],[1],[3,3],[2],[4]]`示例輸出：`[null,null,null,1,null,-1,-1]`要求：-使用哈希表和雙向鏈表實現(xiàn)-get和put操作的平均時間復(fù)雜度為O(1)題目5（12分）：給定一個整數(shù)數(shù)組，返回所有和為`target`的三個數(shù)的組合。結(jié)果中不能有重復(fù)的三元組。示例輸入：`nums=[2,7,11,15],target=9`示例輸出：`[[2,7,0]]`（假設(shè)索引從0開始）要求：-可以假設(shè)每個輸入只對應(yīng)一個解-不能使用重復(fù)的元素題目6（12分）：實現(xiàn)快速排序算法，并分析其平均時間復(fù)雜度和最壞情況時間復(fù)雜度。示例輸入：`arr=[3,6,8,10,1,2,1]`示例輸出：`[1,1,2,3,6,8,10]`要求：-不能使用遞歸-分析時間復(fù)雜度變化條件題目7（12分）：設(shè)計一個算法，找出二叉樹中的最大路徑和。路徑可以從任意節(jié)點開始，到任意節(jié)點結(jié)束，但必須至少包含一個節(jié)點。示例輸入：1/\23示例輸出：`6`（路徑1-2-3）要求：-可以使用遞歸-考慮負(fù)數(shù)節(jié)點的情況題目8（12分）：實現(xiàn)一個函數(shù)，判斷一個鏈表是否有環(huán)。如果有環(huán)，返回進(jìn)入環(huán)的第一個節(jié)點；如果沒有環(huán)，返回null。示例輸入：3->2->0->-4^|||示例輸出：`節(jié)點2`要求：-可以使用快慢指針-不能使用額外的存儲空間題目9（12分）：實現(xiàn)二分查找算法，并說明其適用條件。示例輸入：`arr=[1,2,3,4,5,6,7,8,9],target=4`示例輸出：`3`（索引從0開始）要求：-處理target不存在的情況-分析時間復(fù)雜度題目10（12分）：實現(xiàn)一個函數(shù)，將32位無符號整數(shù)反轉(zhuǎn)。如果反轉(zhuǎn)后數(shù)值超出32位整數(shù)的范圍，返回0。示例輸入：`x=123456789`示例輸出：`987654321`要求：-考慮整數(shù)溢出情況-時間復(fù)雜度為O(log(x))題目11（12分）：實現(xiàn)一個函數(shù)，檢查一個字符串是否是回文串?？梢院雎苑亲帜笖?shù)字字符和大小寫。示例輸入：`"Aman,aplan,acanal:Panama"`示例輸出：`true`要求：-可以使用雙指針方法-考慮空字符串情況題目12（12分）：給定一個鏈表，將其反轉(zhuǎn)，并返回反轉(zhuǎn)后的鏈表頭節(jié)點。示例輸入：`1->2->3->4->5`示例輸出：`5->4->3->2->1`要求：-不能使用遞歸-分析時間復(fù)雜度3.系統(tǒng)設(shè)計（3題，每題25分）題目13（25分）：設(shè)計一個簡單的URL短鏈接系統(tǒng)。需要支持：1.將長URL轉(zhuǎn)換為短URL2.將短URL解析為原始長URL3.每個長URL對應(yīng)唯一短URL要求：-說明核心數(shù)據(jù)結(jié)構(gòu)-描述算法流程-分析性能瓶頸題目14（25分）：設(shè)計一個簡單的消息隊列系統(tǒng)。需要支持：1.生產(chǎn)者發(fā)送消息2.消費(fèi)者接收消息3.保證消息至少被消費(fèi)一次要求：-說明核心組件-描述消息存儲方式-分析高并發(fā)場景下的解決方案題目15（25分）：設(shè)計一個簡單的用戶登錄系統(tǒng)。需要支持：1.用戶注冊（用戶名唯一）2.用戶登錄（驗證密碼）3.密碼加密存儲要求：-說明核心數(shù)據(jù)結(jié)構(gòu)-描述密碼加密方式-分析安全漏洞及防護(hù)措施答案與解析編程能力測試答案題目1（25分）：pythondefreverse_substrings(s:str,k:int)->str:ifnotsork<=1:returnsarr=list(s)n=len(arr)foriinrange(0,n,k):ifi+k<=n:arr[i:i+k]=arr[i:i+k][::-1]return''.join(arr)解析：-時間復(fù)雜度：O(n)，每個字符被訪問一次-空間復(fù)雜度：O(1)，僅使用常數(shù)額外空間-處理k=1時，無需反轉(zhuǎn)-處理s為空時，直接返回空字符串-每次處理長度為k的子串，如果剩余長度小于k則不處理題目2（25分）：pythondeffind_longest_increasing_subarray(arr:List[int])->int:ifnotarr:return0max_len=1current_len=1foriinrange(1,len(arr)):ifarr[i]>arr[i-1]:current_len+=1max_len=max(max_len,current_len)else:current_len=1returnmax_len解析：-時間復(fù)雜度：O(n)，遍歷數(shù)組一次-空間復(fù)雜度：O(1)，僅使用常數(shù)額外空間-初始化兩個計數(shù)器，分別記錄當(dāng)前和最大長度-遍歷時比較相鄰元素，如果遞增則增加當(dāng)前長度，否則重置-處理數(shù)組為空或所有元素相同的情況題目3（25分）：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：-時間復(fù)雜度：O(n)，每個字符被訪問一次-空間復(fù)雜度：O(n)，最壞情況下棧存儲所有字符-使用棧存儲左括號，遇到右括號時匹配棧頂-初始化一個特殊字符作為哨兵，避免空棧時出錯-最后檢查棧是否為空題目4（12分）：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:self.cache[key]=valueself.cache.move_to_end(key)iflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：-使用OrderedDict實現(xiàn)LRU，保持插入順序-get操作將訪問的鍵移動到末尾-put操作同樣將鍵移動到末尾，如果超出容量則刪除第一個元素-時間復(fù)雜度：O(1)-空間復(fù)雜度：O(capacity)題目5（12分）：pythondefthreeSum(nums:List[int],target:int)->List[List[int]]: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解析：-首先排序，便于跳過重復(fù)元素-使用固定指針+雙指針方法-每次固定一個數(shù)，然后使用雙指針找另外兩個數(shù)-跳過重復(fù)元素避免重復(fù)三元組-時間復(fù)雜度：O(n2)-空間復(fù)雜度：O(1)（如果忽略輸出空間）題目6（12分）：pythondefquick_sort(arr:List[int])->List[int]:def_quick_sort(nums,low,high):iflow<high:pivot=_partition(nums,low,high)_quick_sort(nums,low,pivot-1)_quick_sort(nums,pivot+1,high)def_partition(nums,low,high):pivot=nums[high]i=low-1forjinrange(low,high):ifnums[j]<=pivot:i+=1nums[i],nums[j]=nums[j],nums[i]nums[i+1],nums[high]=nums[high],nums[i+1]returni+1_quick_sort(arr,0,len(arr)-1)returnarr解析：-平均時間復(fù)雜度：O(nlogn)-最壞情況時間復(fù)雜度：O(n2)（當(dāng)每次選擇的樞軸都是最小或最大元素時）-使用遞歸實現(xiàn)，但題目要求非遞歸版本-非遞歸實現(xiàn)可以使用棧模擬遞歸調(diào)用棧-空間復(fù)雜度：O(logn)（遞歸棧）題目7（12分）：pythondefmaxPathSum(root:TreeNode)->int:def_maxPathSum(node):ifnotnode:returnfloat('-inf')left=max(_maxPathSum(node.left),0)right=max(_maxPathSum(node.right),0)current_max=node.val+left+rightnonlocalmax_summax_sum=max(max_sum,current_max)returnnode.val+max(left,right)max_sum=float('-inf')_maxPathSum(root)returnmax_sum解析：-使用后序遍歷（左右中）-每個節(jié)點計算以該節(jié)點為根的最大路徑和-更新全局最大值-返回值表示以該節(jié)點為根的子樹最大路徑和（可以延伸到一側(cè)）-時間復(fù)雜度：O(n)-空間復(fù)雜度：O(h)（遞歸棧）題目8（12分）：pythondefdetectCycle(head:ListNode)->ListNode:slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:找到交點后，移動slow到頭節(jié)點slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：-使用快慢指針法-快指針每次走兩步，慢指針每次走一步-如果有環(huán)，快慢指針最終會相遇-相遇后，將慢指針移到頭節(jié)點，再次以相同速度移動，相遇點即為入口-時間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)題目9（12分）：pythondefbinary_search(arr:List[int],target:int)->int:left,right=0,len(arr)-1whileleft<=right:mid=left+(right-left)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid-1return-1解析：-適用于已排序數(shù)組-每次將搜索范圍減半-時間復(fù)雜度：O(logn)-空間復(fù)雜度：O(1)-適用條件：數(shù)組必須有序-處理target不存在的情況返回-1題目10（12分）：pythondefreverse(x:int)->int: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解析：-逐位反轉(zhuǎn)數(shù)字-每次處理最后一位，然后更新剩余數(shù)字-檢查反轉(zhuǎn)后是否溢出-時間復(fù)雜度：O(logx)-空間復(fù)雜度：O(1)題目11（12分）：pythondefisPalindrome(s:str)->bool:left,right=0,len(s)-1whileleft<right:whileleft<rightandnots[left].isalnum():left+=1whileleft<rightandnots[right].isalnum():right-=1ifs[left].lower()!=s[right].lower():returnFalseleft,right=left+1,right-1returnTrue解析：-使用雙指針法-跳過非字母數(shù)字字符-比較對應(yīng)字符是否相等（忽略大小寫）-時間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)題目12（12分）：pythondefreverseList(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurr