2026年程序員面試編程題及答案集一、算法設(shè)計(jì)題（共3題，每題20分）1.題目（20分）：“滑動(dòng)窗口最大值”問(wèn)題給定一個(gè)數(shù)組`nums`和一個(gè)整數(shù)`k`，設(shè)計(jì)一個(gè)算法，找到數(shù)組中每個(gè)長(zhǎng)度為`k`的子數(shù)組的最大值，并按順序輸出結(jié)果。示例：輸入：`nums=[1,3,-1,-3,5,3,6,7]`,`k=3`輸出：`[3,3,5,5,6,7]`要求：-不能使用排序，時(shí)間復(fù)雜度要求為`O(n)`。-寫出代碼并解釋核心思路。2.題目（20分）：“字符串解碼”問(wèn)題給定一個(gè)字符串`s`，其中包含數(shù)字和字母，數(shù)字表示后續(xù)字母的重復(fù)次數(shù)，字母需要解碼為字符串。例如：輸入：`s="3[a]2[bc]"`輸出：`"aaabcbc"`要求：-不能使用遞歸，時(shí)間復(fù)雜度要求為`O(n)`。-寫出代碼并解釋核心思路。3.題目（20分）：“合并K個(gè)有序鏈表”問(wèn)題給定`k`個(gè)鏈表，每個(gè)鏈表有序，要求合并成一個(gè)有序鏈表。示例：輸入：`lists=[[1,4,5],[1,3,4],[2,6]]`輸出：`[1,1,2,3,4,4,5,6]`要求：-不能使用內(nèi)置排序，時(shí)間復(fù)雜度要求為`O(nlogk)`。-寫出代碼并解釋核心思路。二、數(shù)據(jù)結(jié)構(gòu)題（共3題，每題20分）1.題目（20分）：“設(shè)計(jì)LRU緩存”問(wèn)題LRU（LeastRecentlyUsed）緩存，通過(guò)哈希表和雙向鏈表實(shí)現(xiàn)，支持`get`和`put`操作。要求：-`get(key)`：返回鍵對(duì)應(yīng)的值，如果不存在返回-1。-`put(key,value)`：如果鍵存在，更新值；如果不存在，添加鍵值對(duì)，如果緩存已滿，刪除最久未使用的鍵。-時(shí)間復(fù)雜度要求為`O(1)`。-寫出代碼并解釋核心思路。2.題目（20分）：“二叉樹(shù)遍歷”問(wèn)題給定一個(gè)二叉樹(shù)，實(shí)現(xiàn)前序、中序、后序遍歷的遞歸和非遞歸版本。示例：1/\23/\45-前序遍歷：`[1,2,4,5,3]`-中序遍歷：`[4,2,5,1,3]`-后序遍歷：`[4,5,2,3,1]`要求：-寫出代碼并解釋核心思路。3.題目（20分）：“格雷編碼”問(wèn)題格雷編碼是一種二進(jìn)制數(shù)的排列方式，相鄰的兩個(gè)二進(jìn)制數(shù)只有一個(gè)比特不同。給定`n`，生成所有格雷編碼。示例：輸入：`n=2`輸出：`[00,01,11,10]`（按順序排列）要求：-寫出代碼并解釋核心思路。三、系統(tǒng)設(shè)計(jì)題（共2題，每題30分）1.題目（30分）：“設(shè)計(jì)短鏈接服務(wù)”問(wèn)題實(shí)現(xiàn)一個(gè)短鏈接服務(wù)，將長(zhǎng)鏈接轉(zhuǎn)換為短鏈接，并支持通過(guò)短鏈接解析回長(zhǎng)鏈接。要求：-短鏈接長(zhǎng)度不超過(guò)6位，支持自定義前綴（如`/`）。-高并發(fā)場(chǎng)景下，解析速度要快。-寫出核心邏輯和數(shù)據(jù)庫(kù)設(shè)計(jì)。2.題目（30分）：“設(shè)計(jì)微博系統(tǒng)”問(wèn)題設(shè)計(jì)一個(gè)微博系統(tǒng)，支持用戶發(fā)布、評(píng)論、關(guān)注、點(diǎn)贊等功能。要求：-數(shù)據(jù)庫(kù)表設(shè)計(jì)，并說(shuō)明選型理由（MySQL或NoSQL）。-說(shuō)明核心模塊的架構(gòu)設(shè)計(jì)（如消息隊(duì)列、緩存）。-提出至少3個(gè)高并發(fā)解決方案。四、編碼實(shí)現(xiàn)題（共4題，每題15分）1.題目（15分）：“字符串去重”問(wèn)題給定一個(gè)字符串，刪除所有重復(fù)的字符，保留首次出現(xiàn)的順序。示例：輸入：`s="abbac"`輸出：`"abc"`要求：-時(shí)間復(fù)雜度要求為`O(n)`，空間復(fù)雜度要求為`O(1)`（假設(shè)字符集固定）。-寫出代碼并解釋核心思路。2.題目（15分）：“數(shù)字翻轉(zhuǎn)”問(wèn)題給定一個(gè)整數(shù)，反轉(zhuǎn)其數(shù)字，如果反轉(zhuǎn)后超過(guò)32位整數(shù)范圍，返回0。示例：輸入：`x=123`輸出：`321`要求：-不能使用庫(kù)函數(shù)，時(shí)間復(fù)雜度要求為`O(logx)`。-寫出代碼并解釋核心思路。3.題目（15分）：“二叉搜索樹(shù)驗(yàn)證”問(wèn)題給定一個(gè)二叉樹(shù)，判斷其是否為有效的二叉搜索樹(shù)。示例：2/\13輸出：`true`要求：-不能使用遞歸，可以使用棧實(shí)現(xiàn)。-寫出代碼并解釋核心思路。4.題目（15分）：“字符串匹配”問(wèn)題實(shí)現(xiàn)KMP算法，找到字符串`text`中是否存在子串`pattern`，如果存在，返回起始索引。示例：輸入：`text="abababab",pattern="abab"`輸出：`0`要求：-寫出代碼并解釋核心思路。答案與解析一、算法設(shè)計(jì)題1.滑動(dòng)窗口最大值代碼：pythondefmaxSlidingWindow(nums,k):fromcollectionsimportdequeresult=[]dq=deque()#存儲(chǔ)索引，單調(diào)遞減foriinrange(len(nums)):移除不在窗口內(nèi)的元素ifdqanddq[0]<i-k+1:dq.popleft()移除小于當(dāng)前元素的元素whiledqandnums[i]>nums[dq[-1]]:dq.pop()dq.append(i)窗口形成后，記錄最大值ifi>=k-1:result.append(nums[dq[0]])returnresult解析：使用雙端隊(duì)列存儲(chǔ)窗口的最大值的索引，保證隊(duì)頭始終是當(dāng)前窗口的最大值。每次滑動(dòng)窗口時(shí)，先移除不在窗口內(nèi)的索引，然后從隊(duì)尾移除所有小于當(dāng)前元素的索引，最后將當(dāng)前索引加入隊(duì)列。時(shí)間復(fù)雜度為`O(n)`。2.字符串解碼代碼：pythondefdecodeString(s):stack=[]num=0current_str=""forcharins:ifchar.isdigit():num=num10+int(char)elifchar=='[':stack.append((current_str,num))current_str=""num=0elifchar==']':prev_str,prev_num=stack.pop()current_str=prev_str+current_strprev_numelse:current_str+=charreturncurrent_str解析：使用棧處理括號(hào)嵌套，遇到數(shù)字時(shí)累積，遇到`[`時(shí)保存當(dāng)前字符串和數(shù)字，遇到`]`時(shí)將當(dāng)前字符串重復(fù)并拼接回前一個(gè)字符串。時(shí)間復(fù)雜度為`O(n)`。3.合并K個(gè)有序鏈表代碼：pythondefmergeKLists(lists):fromheapqimportheappop,heappushheap=[]fori,nodeinenumerate(lists):ifnode:heappush(heap,(node.val,i,node))dummy=ListNode(0)current=dummywhileheap:val,idx,node=heappop(heap)current.next=nodecurrent=current.nextifnode.next:heappush(heap,(node.next.val,idx,node.next))returndummy.next解析：使用最小堆維護(hù)當(dāng)前所有鏈表頭部，每次彈出最小節(jié)點(diǎn)并加入結(jié)果，然后將該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)加入堆。時(shí)間復(fù)雜度為`O(nlogk)`。二、數(shù)據(jù)結(jié)構(gòu)題1.LRU緩存代碼：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=deque()defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.popleft()delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用哈希表存儲(chǔ)鍵值對(duì)，雙向鏈表維護(hù)訪問(wèn)順序。`get`操作將鍵移到隊(duì)尾，`put`操作先移除最久未使用的鍵（隊(duì)頭），然后添加新鍵值對(duì)。時(shí)間復(fù)雜度為`O(1)`。2.二叉樹(shù)遍歷前序遍歷（非遞歸）：pythondefpreorderTraversal(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult解析：使用棧模擬遞歸，先訪問(wèn)節(jié)點(diǎn)，然后右左入棧。時(shí)間復(fù)雜度為`O(n)`。3.格雷編碼代碼：pythondefgrayCode(n):return[i^(i>>1)foriinrange(1<<n)]解析：格雷編碼的生成公式為`i^(i>>1)`，其中`i`從`0`到`2^n-1`。時(shí)間復(fù)雜度為`O(n)`。三、系統(tǒng)設(shè)計(jì)題1.短鏈接服務(wù)核心邏輯：-使用哈希函數(shù)（如MD5）將長(zhǎng)鏈接映射為短碼，如`a-zA-Z0-9`。-存儲(chǔ)短碼與長(zhǎng)鏈接的映射關(guān)系，使用Redis緩存熱點(diǎn)數(shù)據(jù)。-短碼沖突時(shí)，通過(guò)自增或隨機(jī)重試解決。數(shù)據(jù)庫(kù)設(shè)計(jì)：sqlCREATETABLEshort_links(short_codeVARCHAR(6)PRIMARYKEY,long_urlVARCHAR(1024),created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);2.微博系統(tǒng)數(shù)據(jù)庫(kù)設(shè)計(jì)：sqlCREATETABLEusers(user_idINTPRIMARYKEY,usernameVARCHAR(50),passwordVARCHAR(255));CREATETABLEposts(post_idINTPRIMARYKEY,user_idINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id));CREATETABLEcomments(comment_idINTPRIMARYKEY,post_idINT,user_idINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(post_id)REFERENCESposts(post_id),FOREIGNKEY(user_id)REFERENCESusers(user_id));架構(gòu)設(shè)計(jì)：-消息隊(duì)列（Kafka）處理用戶行為日志，用于推薦系統(tǒng)。-緩存（Redis）存儲(chǔ)熱點(diǎn)用戶和文章。-負(fù)載均衡（Nginx）分?jǐn)傉?qǐng)求壓力。高并發(fā)方案：1.分區(qū)（Sharding）用戶表和帖子表。2.異步寫入數(shù)據(jù)庫(kù)。3.限流（RateLimiting）防止惡意攻擊。四、編碼實(shí)現(xiàn)題1.字符串去重代碼：pythondefremoveDuplicates(s:str)->str:stack=[]forcharins:ifstackandstack[-1]==char:stack.pop()else:stack.append(char)return''.join(stack)解析：使用棧處理字符串，遇到重復(fù)字符時(shí)彈出，否則入棧。時(shí)間復(fù)雜度為`O(n)`。2.數(shù)字翻轉(zhuǎn)代碼：pythondefreverse(x:int)->int:result=0INT_MAX,INT_MIN=231-1,-231whilex:digit=x%10x=x//10ifresult>INT_MAX//10or(result==INT_MAX//10anddigit>7):return0ifresult<INT_MIN//10or(result==INT_MIN//10anddigit<-8):return0result=result10+digitreturnresult解析：逐位翻轉(zhuǎn)數(shù)字，同時(shí)檢查溢出。時(shí)間復(fù)雜度為`O(logx)`。3.二叉搜索樹(shù)驗(yàn)證代碼：pythondefisValidBST(root):stack,prev=[],float('-inf')whilestackorroot:whileroot:stack.append(root)root=root.leftroot=stack.pop()ifroot.val<=prev:returnFalseprev=root.valroot