2026年互聯(lián)網(wǎng)公司面試者必做編程與算法題集一、編程基礎(chǔ)（5題，每題6分）1.字符串反轉(zhuǎn)（6分）題目：請(qǐng)編寫一個(gè)函數(shù)，將輸入的字符串反轉(zhuǎn)。例如，輸入`"hello"`，輸出`"olleh"`。要求不使用內(nèi)置的反轉(zhuǎn)函數(shù)。2.鏈表反轉(zhuǎn)（6分）題目：給定一個(gè)單鏈表，請(qǐng)編寫代碼將其反轉(zhuǎn)。鏈表節(jié)點(diǎn)定義如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next3.數(shù)組去重（6分）題目：給定一個(gè)無序數(shù)組，請(qǐng)編寫函數(shù)去除重復(fù)元素，并返回新的數(shù)組長(zhǎng)度。例如，輸入`[1,2,2,3,3,4]`，返回`[1,2,3,4]`，長(zhǎng)度為4。4.字符串匹配（6分）題目：請(qǐng)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的字符串匹配函數(shù)，判斷子串是否在主串中。例如，主串`"hello"`，子串`"ll"`，返回`True`。要求時(shí)間復(fù)雜度不超過O(n)。5.深度優(yōu)先搜索（6分）題目：給定一個(gè)二叉樹，請(qǐng)編寫深度優(yōu)先搜索（DFS）函數(shù)，遍歷所有節(jié)點(diǎn)并返回結(jié)果列表。二叉樹節(jié)點(diǎn)定義如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right二、算法進(jìn)階（5題，每題8分）6.快速排序（8分）題目：請(qǐng)實(shí)現(xiàn)快速排序算法，對(duì)給定數(shù)組進(jìn)行排序。要求使用遞歸方式實(shí)現(xiàn)。7.二叉樹遍歷（8分）題目：給定一個(gè)二叉樹，請(qǐng)分別實(shí)現(xiàn)廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）的遍歷，并返回結(jié)果列表。二叉樹結(jié)構(gòu)同上。8.動(dòng)態(tài)規(guī)劃（8分）題目：給定一個(gè)數(shù)組，其中每個(gè)元素表示跳格子問題中每個(gè)格子的最大跳躍長(zhǎng)度。例如，輸入`[2,3,1,1,4]`，返回可以跳到的最遠(yuǎn)位置（即最右邊的索引）。要求使用動(dòng)態(tài)規(guī)劃解決。9.最長(zhǎng)公共子序列（8分）題目：給定兩個(gè)字符串，請(qǐng)編寫函數(shù)計(jì)算它們的最長(zhǎng)公共子序列的長(zhǎng)度。例如，`"abcde"`和`"ace"`，最長(zhǎng)公共子序列為`"ace"`，返回3。10.數(shù)組中的第K個(gè)最大元素（8分）題目：給定一個(gè)無序數(shù)組，請(qǐng)編寫函數(shù)找到數(shù)組中的第K個(gè)最大元素。例如，輸入`[3,2,1,5,6,4]`，K=2，返回5。三、系統(tǒng)設(shè)計(jì)（3題，每題10分）11.LRU緩存機(jī)制（10分）題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)LRU（LeastRecentlyUsed）緩存機(jī)制，支持get和put操作。緩存容量為固定值，超出容量時(shí)需要淘汰最久未使用的元素。要求時(shí)間復(fù)雜度為O(1)。12.算法面試高頻問題：斐波那契數(shù)列（10分）題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，計(jì)算斐波那契數(shù)列的第N項(xiàng)。例如，N=5，返回5。要求優(yōu)化時(shí)間復(fù)雜度，避免遞歸的重復(fù)計(jì)算。13.算法面試高頻問題：合并兩個(gè)排序鏈表（10分）題目：給定兩個(gè)排序鏈表，請(qǐng)編寫函數(shù)合并它們，并返回合并后的排序鏈表。例如，鏈表1`[1,2,4]`，鏈表2`[1,3,4]`，返回`[1,1,2,3,4,4]`。四、編程實(shí)踐（2題，每題12分）14.字符串編輯距離（12分）題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，計(jì)算兩個(gè)字符串的編輯距離（即通過插入、刪除、替換操作將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串的最少操作次數(shù)）。例如，`"horse"`和`"ros"`，編輯距離為3（"horse"→"ros"可以通過"h"→"r"，"o"→"o"，"r"→"s"）。15.算法面試高頻問題：二分查找（12分）題目：給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，請(qǐng)編寫函數(shù)找到目標(biāo)值的索引。如果不存在，返回-1。例如，數(shù)組`[1,2,3,4,5]`，目標(biāo)值3，返回2。要求時(shí)間復(fù)雜度為O(logn)。答案與解析一、編程基礎(chǔ)1.字符串反轉(zhuǎn)（6分）答案：pythondefreverse_string(s:str)->str:returns[::-1]解析：使用Python的切片操作`[::-1]`可以高效反轉(zhuǎn)字符串，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。2.鏈表反轉(zhuǎn)（6分）答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：通過迭代方式反轉(zhuǎn)鏈表，使用三個(gè)指針`prev`、`current`和`next_node`，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。3.數(shù)組去重（6分）答案：pythondefremove_duplicates(nums:List[int])->int:ifnotnums:return0slow=0forfastinrange(1,len(nums)):ifnums[fast]!=nums[slow]:slow+=1nums[slow]=nums[fast]returnslow+1解析：使用雙指針法，`slow`指向當(dāng)前不重復(fù)的最后一個(gè)元素，`fast`遍歷數(shù)組。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。4.字符串匹配（6分）答案：pythondefcontains_substring(s:str,sub:str)->bool:ifnotsub:returnTruelen_s,len_sub=len(s),len(sub)foriinrange(len_s-len_sub+1):ifs[i:i+len_sub]==sub:returnTruereturnFalse解析：暴力匹配，遍歷主串，每次比較子串長(zhǎng)度范圍內(nèi)的子串。時(shí)間復(fù)雜度為O(nm)，但題目要求O(n)可優(yōu)化為KMP算法。5.深度優(yōu)先搜索（6分）答案：pythondefdfs(root:TreeNode,result:List[int]=[])->List[int]:ifnotroot:returnresultresult.append(root.val)dfs(root.left,result)dfs(root.right,result)returnresult解析：遞歸遍歷左子樹和右子樹，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(h)（h為樹的高度）。二、算法進(jìn)階6.快速排序（8分）答案：pythondefquick_sort(arr:List[int])->List[int]:iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：選擇中間值作為基準(zhǔn)，遞歸對(duì)左右子數(shù)組排序。平均時(shí)間復(fù)雜度為O(nlogn)，最壞為O(n^2)。7.二叉樹遍歷（8分）BFS答案：pythonfromcollectionsimportdequedefbfs(root:TreeNode)->List[int]:ifnotroot:return[]queue=deque([root])result=[]whilequeue:node=queue.popleft()result.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnresultDFS答案：pythondefdfs(root:TreeNode,result:List[int]=[])->List[int]:ifnotroot:returnresultresult.append(root.val)dfs(root.left,result)dfs(root.right,result)returnresult解析：BFS使用隊(duì)列實(shí)現(xiàn)層序遍歷，DFS使用遞歸實(shí)現(xiàn)。時(shí)間復(fù)雜度均為O(n)，空間復(fù)雜度為O(n)。8.動(dòng)態(tài)規(guī)劃（8分）答案：pythondefjump_max(arr:List[int])->int:n=len(arr)dp=[0]nforiinrange(1,n):max_step=min(i,arr[i-1])forjinrange(max_step,0,-1):ifdp[i-j]+j>=i:dp[i]=dp[i-j]+jbreakreturndp[-1]解析：從后向前計(jì)算每個(gè)位置可達(dá)的最遠(yuǎn)距離。時(shí)間復(fù)雜度為O(n^2)，可優(yōu)化為O(n)。9.最長(zhǎng)公共子序列（8分）答案：pythondeflongest_common_subsequence(text1:str,text2:str)->int:m,n=len(text1),len(text2)dp=[[0](n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):iftext1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])returndp[-1][-1]解析：動(dòng)態(tài)規(guī)劃構(gòu)建二維表，時(shí)間復(fù)雜度為O(mn)，空間復(fù)雜度為O(mn)。10.數(shù)組中的第K個(gè)最大元素（8分）答案：pythonimportheapqdeffind_kth_largest(nums:List[int],k:int)->int:returnheapq.nlargest(k,nums)[-1]解析：使用堆排序，`heapq.nlargest`可高效找到第K個(gè)最大元素，時(shí)間復(fù)雜度為O(nlogk)。三、系統(tǒng)設(shè)計(jì)11.LRU緩存機(jī)制（10分）答案：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:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：使用`OrderedDict`維護(hù)插入順序，`move_to_end`實(shí)現(xiàn)最近使用移到末尾。時(shí)間復(fù)雜度為O(1)。12.斐波那契數(shù)列（10分）答案：pythondeffib(n:int)->int:ifn<=1:returnndp=[0](n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：動(dòng)態(tài)規(guī)劃避免遞歸重復(fù)計(jì)算，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。可優(yōu)化為O(1)空間。13.合并兩個(gè)排序鏈表（10分）答案：pythondefmerge_two_lists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1orl2returndummy.next解析：迭代合并兩個(gè)有序鏈表，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。四、編程實(shí)踐14.字符串編輯距離（12分）答案：pythondefedit_distance(s1:str,s2:str)->int:m,n=len(s1),len(s2)dp=[[0](n+1)f