计算机科学面试题及答案

2026年计算机科学面试题及答案一、编程题（共3题，每题15分，总分45分）题目1（15分）：编写一个函数，输入一个字符串，返回该字符串中所有唯一字符的列表。如果输入字符串为空，返回空列表。例如，输入`"leetcode"`，输出`['e','t','c','d','o','l']`。要求时间复杂度为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`记录已出现的字符，确保唯一性。2.遍历字符串，如果字符不在集合中，则添加到集合和结果列表中。3.时间复杂度为O(n)，空间复杂度为O(n)，符合题目要求。题目2（15分）：给定一个整数数组，返回一个新数组，其中每个元素是原数组中对应元素的前缀和。例如，输入`[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.遍历数组，每次将当前元素加到`current_sum`，并添加到结果列表中。3.时间复杂度为O(n)，空间复杂度为O(n)。题目3（15分）：实现一个LRU（最近最少使用）缓存。缓存容量为`capacity`，支持`get`和`put`操作。`get(key)`返回键对应的值，如果键不存在返回-1；`put(key,value)`将键值对插入缓存，如果键已存在则更新值，如果超出容量则删除最久未使用的键。例如，容量为2的缓存：-`put(1,1)`-`put(2,2)`-`get(1)`→返回1-`put(3,3)`（此时驱逐键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.时间复杂度为O(1)，空间复杂度为O(capacity)。二、算法题（共3题，每题15分，总分45分）题目4（15分）：给定一个二叉树，判断其是否是平衡二叉树。平衡二叉树的定义是：对于任意节点，其左右子树的高度差不超过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示例测试构建平衡二叉树：[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.递归计算每个节点的左右子树高度，如果高度差超过1或子树不平衡（返回-1），则整棵树不平衡。2.时间复杂度为O(n)，空间复杂度为O(h)，h为树的高度。题目5（15分）：给定一个包含重复元素的数组，返回所有不重复的全排列。例如，输入`[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.先对数组排序，以便跳过重复元素。2.使用回溯法生成排列，`used`数组记录是否使用过当前元素。3.跳过与前一个相同且前一个未使用的元素，避免重复排列。4.时间复杂度为O(n!)，空间复杂度为O(n)。题目6（15分）：给定一个正整数`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`分别记录左括号和右括号的数量。2.每次选择添加左括号或右括号，但必须满足左括号数量不超过n，右括号数量不超过左括号。3.时间复杂度为O(4^n/sqrt(n))，空间复杂度为O(n)。三、系统设计题（共1题，25分）题目7（25分）：设计一个简单的微博系统，支持以下功能：1.用户注册和登录。2.发布微博（包含文本内容、时间戳、用户ID）。3.关注/取消关注用户。4.判断用户是否关注了另一个用户。5.获取用户的时间线（包含自己发布的微博和关注用户发布的微博，按时间降序排列）。答案：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