2026年計(jì)算機(jī)科學(xué)面試題及解析一、編程題（共3題，每題15分）1.（15分）題目：給定一個(gè)包含重復(fù)元素的整數(shù)數(shù)組，返回該數(shù)組所有可能的子集（無重復(fù)子集）。要求：-不能使用遞歸或回溯算法。-時(shí)間復(fù)雜度盡可能低。-示例輸入：`[1,2,2]`，輸出：`[[],[1],[1,2],[1,2,2],[2],[2,2]]`2.（15分）題目：實(shí)現(xiàn)一個(gè)LRU（LeastRecentlyUsed）緩存，支持以下操作：-`get(key)`:獲取鍵`key`對應(yīng)的值，如果不存在返回-1。-`put(key,value)`:插入或更新鍵值對，如果緩存已滿，則刪除最久未使用的緩存項(xiàng)。要求：-使用哈希表和雙向鏈表實(shí)現(xiàn)，確保`get`和`put`操作的時(shí)間復(fù)雜度為O(1)。-示例輸入：-`put(1,1)`-`put(2,2)`-`get(1)`→返回1-`put(3,3)`（此時(shí)緩存滿，刪除鍵1）-`get(2)`→返回23.（15分）題目：設(shè)計(jì)一個(gè)算法，判斷一個(gè)字符串是否是另一個(gè)字符串的“變位詞”（字母重新排列后相同）。要求：-忽略大小寫和空格。-示例輸入：-`s1="Listen"`,`s2="Silent"`→返回`true`-`s1="Hello"`,`s2="World"`→返回`false`二、算法題（共4題，每題10分）1.（10分）題目：給定一個(gè)包含`n`個(gè)整數(shù)的數(shù)組，返回所有和為`target`的四個(gè)不同數(shù)字的數(shù)組。要求：-不能使用重復(fù)的數(shù)字。-示例輸入：`nums=[1,0,-1,0,-2,2]`,`target=0`，輸出：`[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`2.（10分）題目：實(shí)現(xiàn)一個(gè)函數(shù)，檢查一個(gè)二叉樹是否是平衡二叉樹（左右子樹高度差不超過1）。要求：-返回布爾值，并優(yōu)化時(shí)間復(fù)雜度（O(n)）。3.（10分）題目：設(shè)計(jì)一個(gè)算法，找出數(shù)組中重復(fù)次數(shù)超過`n/2`的元素。要求：-只允許使用常數(shù)額外空間。-示例輸入：`nums=[3,2,3]`→返回`3`4.（10分）題目：給定一個(gè)字符串`s`，找到最長的無重復(fù)字符的子串長度。要求：-示例輸入：`s="abcabcbb"`→返回`3`（"abc"是最長無重復(fù)子串）三、系統(tǒng)設(shè)計(jì)題（共2題，每題20分）1.（20分）題目：設(shè)計(jì)一個(gè)簡單的微博系統(tǒng)，要求支持以下功能：-用戶發(fā)布微博（限制長度不超過200字）。-用戶關(guān)注/取消關(guān)注其他用戶。-用戶獲取自己關(guān)注的人的最新微博（時(shí)間復(fù)雜度要求低）。要求：-描述數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、核心算法思路，以及可能的擴(kuò)展方案（如分頁、緩存）。2.（20分）題目：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接生成服務(wù)（如`tinyurl`）。要求：-支持高并發(fā)訪問。-鏈接生成和解析速度快。-鏈接具有唯一性和可擴(kuò)展性。-描述技術(shù)選型（如數(shù)據(jù)庫、緩存、分布式架構(gòu)）及關(guān)鍵實(shí)現(xiàn)細(xì)節(jié)。四、數(shù)據(jù)庫題（共2題，每題15分）1.（15分）題目：設(shè)計(jì)一個(gè)電商訂單表，包含以下字段：-`order_id`（主鍵）-`user_id`（用戶ID）-`product_id`（商品ID）-`quantity`（數(shù)量）-`order_time`（下單時(shí)間）要求：-說明字段類型選擇及索引設(shè)計(jì)。-編寫SQL查詢：找出每個(gè)用戶的總消費(fèi)金額。2.（15分）題目：假設(shè)有一個(gè)數(shù)據(jù)庫事務(wù)，包含以下步驟：1.更新訂單狀態(tài)為“已支付”。2.減少庫存數(shù)量。要求：-解釋如何保證事務(wù)的原子性和一致性。-如果使用MySQL，說明如何設(shè)置事務(wù)隔離級(jí)別。五、分布式與網(wǎng)絡(luò)題（共3題，每題10分）1.（10分）題目：解釋CAP理論，并說明在分布式系統(tǒng)中如何選擇一致性（Consistency）、可用性（Availability）和分區(qū)容錯(cuò)性（PartitionTolerance）。2.（10分）題目：簡述Redis和Memcached的區(qū)別，以及它們在緩存場景中的適用場景。3.（10分）題目：解釋HTTP和HTTPS的區(qū)別，以及HTTPS如何通過SSL/TLS協(xié)議保證數(shù)據(jù)安全。答案及解析一、編程題1.（15分）答案：pythondefsubsetsWithDup(nums):result=[[]]nums.sort()#先排序，方便去重foriinrange(len(nums)):ifi==0ornums[i]!=nums[i-1]:new_subsets=[]forsubsetinresult:new_subsets.append(subset+[nums[i]])result.extend(new_subsets)returnresult解析：-先對數(shù)組排序，便于處理重復(fù)元素。-使用迭代法構(gòu)建子集，避免遞歸。-對于每個(gè)新元素，如果與前一個(gè)元素不同，則可以安全添加到所有現(xiàn)有子集中；如果相同，則跳過（避免重復(fù)子集）。2.（15分）答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=self.Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodenode.prev=self.headself.head.next=node解析：-使用雙向鏈表維護(hù)訪問順序，頭節(jié)點(diǎn)為最近使用，尾節(jié)點(diǎn)為最久未使用。-哈希表`cache`存儲(chǔ)鍵到鏈表節(jié)點(diǎn)的映射，實(shí)現(xiàn)O(1)的`get`和`put`。-`get`時(shí)將節(jié)點(diǎn)移到頭部，`put`時(shí)如果容量超限則刪除尾部節(jié)點(diǎn)。3.（15分）答案：pythondefisAnagram(s1:str,s2:str)->bool:s1=''.join(s1.lower().split())s2=''.join(s2.lower().split())iflen(s1)!=len(s2):returnFalsecount={}forcharins1:count[char]=count.get(char,0)+1forcharins2:ifcharnotincount:returnFalsecount[char]-=1ifcount[char]<0:returnFalsereturnTrue解析：-忽略大小寫和空格，統(tǒng)一處理。-使用哈希表統(tǒng)計(jì)字符頻率，如果兩個(gè)字符串頻率一致則返回`true`。二、算法題1.（10分）答案：pythondeffourSum(nums,target):nums.sort()n=len(nums)result=[]foriinrange(n-3):ifi>0andnums[i]==nums[i-1]:continueforjinrange(i+1,n-2):ifj>i+1andnums[j]==nums[j-1]:continueleft,right=j+1,n-1whileleft<right:total=nums[i]+nums[j]+nums[left]+nums[right]iftotal==target:result.append([nums[i],nums[j],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ù)字。-固定前兩個(gè)指針，使用雙指針法在剩余部分查找目標(biāo)和。-如果找到解，則移動(dòng)左右指針并跳過重復(fù)數(shù)字。2.（10分）答案：pythondefisBalanced(root):defcheck(node):ifnotnode:return0left=check(node.left)right=check(node.right)ifleft==-1orright==-1orabs(left-right)>1:return-1returnmax(left,right)+1returncheck(root)!=-1解析：-遞歸檢查每個(gè)節(jié)點(diǎn)的左右子樹高度差是否小于等于1。-如果任意節(jié)點(diǎn)不平衡，則返回-1。-最終返回非-1表示平衡。3.（10分）答案：pythondefmajorityElement(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：-Boyer-Moore投票算法。-遍歷數(shù)組，遇到候選數(shù)則計(jì)數(shù)+1，否則-1。-當(dāng)計(jì)數(shù)為0時(shí)更換候選數(shù)，最終候選數(shù)為答案。4.（10分）答案：pythondeflengthOfLongestSubstring(s:str)->int:max_len=0start=0char_set=set()forendinrange(len(s)):whiles[end]inchar_set:char_set.remove(s[start])start+=1char_set.add(s[end])max_len=max(max_len,end-start+1)returnmax_len解析：-使用滑動(dòng)窗口法，`start`和`end`表示窗口左右邊界。-遇到重復(fù)字符時(shí)移動(dòng)`start`并移除窗口左側(cè)字符。-更新最大長度。三、系統(tǒng)設(shè)計(jì)題1.（20分）答案：-數(shù)據(jù)結(jié)構(gòu)：-用戶表：`user_id`,`name`,`follows`（存儲(chǔ)關(guān)注的用戶ID列表）。-微博表：`id`,`user_id`,`content`,`time`（時(shí)間索引）。-算法：-獲取關(guān)注人微博：使用`user_id`倒序查詢微博，并按時(shí)間降序返回。-擴(kuò)展：-分頁：使用`LIMIT`和`OFFSET`。-緩存：使用Redis緩存熱點(diǎn)用戶微博。2.（20分）答案：-技術(shù)選型：-哈希函數(shù)：使用Base62編碼（`a-z`,`0-9`,`A-Z`）生成短鏈接。-數(shù)據(jù)存儲(chǔ)：Redis緩存熱點(diǎn)鏈接，MySQL存儲(chǔ)長期鏈接。-關(guān)鍵實(shí)現(xiàn)：-唯一性：使用雪花算法或數(shù)據(jù)庫自增ID映射。-解析：通過哈希函數(shù)反解原始ID。四、數(shù)據(jù)庫題1.（15分）答案：sqlCREATETABLEorders(order_idINTAUTO_INCREMENTPRIMARYKEY,user_idINT,product_idINT,quantityINT,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,INDEXidx_user_id(user_id));SELECTuser_id,SUM(quantityprice)AStotal_spentFROMordersoJ