2026年計算機科學(xué)面試題及答案一、編程題（共3題，每題15分，總分45分）題目1（15分）：編寫一個函數(shù)，輸入一個字符串，返回該字符串中所有唯一字符的列表。如果輸入字符串為空，返回空列表。例如，輸入`"leetcode"`，輸出`['e','t','c','d','o','l']`。要求時間復(fù)雜度為O(n)。答案：pythondefunique_chars(s:str)->list:ifnots:return[]char_set=set()result=[]forcharins:ifcharnotinchar_set:char_set.add(char)result.append(char)returnresult示例測試print(unique_chars("leetcode"))#輸出:['e','t','c','d','o','l']解析：1.使用集合`char_set`記錄已出現(xiàn)的字符，確保唯一性。2.遍歷字符串，如果字符不在集合中，則添加到集合和結(jié)果列表中。3.時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)，符合題目要求。題目2（15分）：給定一個整數(shù)數(shù)組，返回一個新數(shù)組，其中每個元素是原數(shù)組中對應(yīng)元素的前綴和。例如，輸入`[1,2,3,4]`，輸出`[1,3,6,10]`。答案：pythondefprefix_sum(arr:list)->list:ifnotarr:return[]result=[]current_sum=0fornuminarr:current_sum+=numresult.append(current_sum)returnresult示例測試print(prefix_sum([1,2,3,4]))#輸出:[1,3,6,10]解析：1.初始化`current_sum`為0，用于累加前綴和。2.遍歷數(shù)組，每次將當(dāng)前元素加到`current_sum`，并添加到結(jié)果列表中。3.時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。題目3（15分）：實現(xiàn)一個LRU（最近最少使用）緩存。緩存容量為`capacity`，支持`get`和`put`操作。`get(key)`返回鍵對應(yīng)的值，如果鍵不存在返回-1；`put(key,value)`將鍵值對插入緩存，如果鍵已存在則更新值，如果超出容量則刪除最久未使用的鍵。例如，容量為2的緩存：-`put(1,1)`-`put(2,2)`-`get(1)`→返回1-`put(3,3)`（此時驅(qū)逐鍵2）-`get(2)`→返回-1答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeynotinself.cache:return-1self.order.remove(key)self.order.append(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)示例測試lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#輸出:1lru.put(3,3)print(lru.get(2))#輸出:-1解析：1.使用字典`cache`存儲鍵值對，列表`order`記錄訪問順序。2.`get`操作將鍵移動到列表末尾表示最近使用。3.`put`操作處理鍵存在、緩存已滿的情況，先刪除最久未使用的鍵。4.時間復(fù)雜度為O(1)，空間復(fù)雜度為O(capacity)。二、算法題（共3題，每題15分，總分45分）題目4（15分）：給定一個二叉樹，判斷其是否是平衡二叉樹。平衡二叉樹的定義是：對于任意節(jié)點，其左右子樹的高度差不超過1。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:defcheck(node:TreeNode)->int:ifnotnode:return0left_height=check(node.left)right_height=check(node.right)ifleft_height==-1orright_height==-1orabs(left_height-right_height)>1:return-1returnmax(left_height,right_height)+1returncheck(root)!=-1示例測試構(gòu)建平衡二叉樹：[3,9,20,null,null,15,7]root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20,TreeNode(15),TreeNode(7))print(is_balanced(root))#輸出:True解析：1.遞歸計算每個節(jié)點的左右子樹高度，如果高度差超過1或子樹不平衡（返回-1），則整棵樹不平衡。2.時間復(fù)雜度為O(n)，空間復(fù)雜度為O(h)，h為樹的高度。題目5（15分）：給定一個包含重復(fù)元素的數(shù)組，返回所有不重復(fù)的全排列。例如，輸入`[1,1,2]`，輸出`[[1,1,2],[1,2,1],[2,1,1]]`。答案：pythondefpermute_unique(nums:list)->list:defbacktrack(path,used,result):iflen(path)==len(nums):result.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path,used,result)path.pop()used[i]=Falsenums.sort()result=[]used=[False]len(nums)backtrack([],used,result)returnresult示例測試print(permute_unique([1,1,2]))#輸出:[[1,1,2],[1,2,1],[2,1,1]]解析：1.先對數(shù)組排序，以便跳過重復(fù)元素。2.使用回溯法生成排列，`used`數(shù)組記錄是否使用過當(dāng)前元素。3.跳過與前一個相同且前一個未使用的元素，避免重復(fù)排列。4.時間復(fù)雜度為O(n!)，空間復(fù)雜度為O(n)。題目6（15分）：給定一個正整數(shù)`n`，生成所有可能的括號組合。例如，輸入`3`，輸出`["((()))","(()())","(())()","()(())","()()()"]`。答案：pythondefgenerate_parentheses(n:int)->list:defbacktrack(s='',left=0,right=0):iflen(s)==2n:result.append(s)returnifleft<n:backtrack(s+'(',left+1,right)ifright<left:backtrack(s+')',left,right+1)result=[]backtrack()returnresult示例測試print(generate_parentheses(3))#輸出:["((()))","(()())","(())()","()(())","()()()"]解析：1.使用回溯法生成括號組合，`left`和`right`分別記錄左括號和右括號的數(shù)量。2.每次選擇添加左括號或右括號，但必須滿足左括號數(shù)量不超過n，右括號數(shù)量不超過左括號。3.時間復(fù)雜度為O(4^n/sqrt(n))，空間復(fù)雜度為O(n)。三、系統(tǒng)設(shè)計題（共1題，25分）題目7（25分）：設(shè)計一個簡單的微博系統(tǒng)，支持以下功能：1.用戶注冊和登錄。2.發(fā)布微博（包含文本內(nèi)容、時間戳、用戶ID）。3.關(guān)注/取消關(guān)注用戶。4.判斷用戶是否關(guān)注了另一個用戶。5.獲取用戶的時間線（包含自己發(fā)布的微博和關(guān)注用戶發(fā)布的微博，按時間降序排列）。答案：pythonclassUser:def__init__(self,user_id:str,username:str):self.user_id=user_idself.username=usernameself.following=set()self.tweets=[]classTweet:def__init__(self,tweet_id:int,user_id:str,content:str,timestamp:int):self.tweet_id=tweet_idself.user_id=user_idself.content=contentself.timestamp=timestampclassWeiboSystem:def__init__(self):self.users={}self.tweets=[]self.tweet_id_counter=1defregister(self,user_id:str,username:str)->None:ifuser_idinself.users:raiseValueError("Useralreadyexists")self.users[user_id]=User(user_id,username)deflogin(self,user_id:str)->User:ifuser_idnotinself.users:raiseValueError("Userdoesnotexist")returnself.users[user_id]defpost_tweet(self,user:User,content:str)->Tweet:tweet=Tweet(self.tweet_id_counter,user.user_id,content,int(time.time()))self.tweets.append(tweet)user.tweets.append(tweet)self.tweet_id_counter+=1returntweetdeffollow(self,user:User,target_id:str)->None:iftarget_idnotinself.users:raiseValueError("Targetuserdoesnotexist")user.following.add(target_id)defunfollow(self,user:User,target_id:str)->None:user.following.discard(target_id)defis_following(self,user:User,target_id:str)->bool:returntarget_idinuser.followingdefget_timeline(self,user:User)->list:timeline=[]all_tweets=set(user.tweets)forfollowerinuser.following:all_tweets.update(self.users[follower].tweets)sorted_tweets=sorted(all_tweets