计算机科学面试题及解析

2026年计算机科学面试题及解析一、编程题（共3题，每题15分）1.（15分）题目：给定一个包含重复元素的整数数组，返回该数组所有可能的子集（无重复子集）。要求：-不能使用递归或回溯算法。-时间复杂度尽可能低。-示例输入：`[1,2,2]`，输出：`[[],[1],[1,2],[1,2,2],[2],[2,2]]`2.（15分）题目：实现一个LRU（LeastRecentlyUsed）缓存，支持以下操作：-`get(key)`:获取键`key`对应的值，如果不存在返回-1。-`put(key,value)`:插入或更新键值对，如果缓存已满，则删除最久未使用的缓存项。要求：-使用哈希表和双向链表实现，确保`get`和`put`操作的时间复杂度为O(1)。-示例输入：-`put(1,1)`-`put(2,2)`-`get(1)`→返回1-`put(3,3)`（此时缓存满，删除键1）-`get(2)`→返回23.（15分）题目：设计一个算法，判断一个字符串是否是另一个字符串的“变位词”（字母重新排列后相同）。要求：-忽略大小写和空格。-示例输入：-`s1="Listen"`,`s2="Silent"`→返回`true`-`s1="Hello"`,`s2="World"`→返回`false`二、算法题（共4题，每题10分）1.（10分）题目：给定一个包含`n`个整数的数组，返回所有和为`target`的四个不同数字的数组。要求：-不能使用重复的数字。-示例输入：`nums=[1,0,-1,0,-2,2]`,`target=0`，输出：`[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`2.（10分）题目：实现一个函数，检查一个二叉树是否是平衡二叉树（左右子树高度差不超过1）。要求：-返回布尔值，并优化时间复杂度（O(n)）。3.（10分）题目：设计一个算法，找出数组中重复次数超过`n/2`的元素。要求：-只允许使用常数额外空间。-示例输入：`nums=[3,2,3]`→返回`3`4.（10分）题目：给定一个字符串`s`，找到最长的无重复字符的子串长度。要求：-示例输入：`s="abcabcbb"`→返回`3`（"abc"是最长无重复子串）三、系统设计题（共2题，每题20分）1.（20分）题目：设计一个简单的微博系统，要求支持以下功能：-用户发布微博（限制长度不超过200字）。-用户关注/取消关注其他用户。-用户获取自己关注的人的最新微博（时间复杂度要求低）。要求：-描述数据结构设计、核心算法思路，以及可能的扩展方案（如分页、缓存）。2.（20分）题目：设计一个高并发的短链接生成服务（如`tinyurl`）。要求：-支持高并发访问。-链接生成和解析速度快。-链接具有唯一性和可扩展性。-描述技术选型（如数据库、缓存、分布式架构）及关键实现细节。四、数据库题（共2题，每题15分）1.（15分）题目：设计一个电商订单表，包含以下字段：-`order_id`（主键）-`user_id`（用户ID）-`product_id`（商品ID）-`quantity`（数量）-`order_time`（下单时间）要求：-说明字段类型选择及索引设计。-编写SQL查询：找出每个用户的总消费金额。2.（15分）题目：假设有一个数据库事务，包含以下步骤：1.更新订单状态为“已支付”。2.减少库存数量。要求：-解释如何保证事务的原子性和一致性。-如果使用MySQL，说明如何设置事务隔离级别。五、分布式与网络题（共3题，每题10分）1.（10分）题目：解释CAP理论，并说明在分布式系统中如何选择一致性（Consistency）、可用性（Availability）和分区容错性（PartitionTolerance）。2.（10分）题目：简述Redis和Memcached的区别，以及它们在缓存场景中的适用场景。3.（10分）题目：解释HTTP和HTTPS的区别，以及HTTPS如何通过SSL/TLS协议保证数据安全。答案及解析一、编程题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解析：-先对数组排序，便于处理重复元素。-使用迭代法构建子集，避免递归。-对于每个新元素，如果与前一个元素不同，则可以安全添加到所有现有子集中；如果相同，则跳过（避免重复子集）。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解析：-使用双向链表维护访问顺序，头节点为最近使用，尾节点为最久未使用。-哈希表`cache`存储键到链表节点的映射，实现O(1)的`get`和`put`。-`get`时将节点移到头部，`put`时如果容量超限则删除尾部节点。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解析：-忽略大小写和空格，统一处理。-使用哈希表统计字符频率，如果两个字符串频率一致则返回`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解析：-先排序，便于跳过重复数字。-固定前两个指针，使用双指针法在剩余部分查找目标和。-如果找到解，则移动左右指针并跳过重复数字。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解析：-递归检查每个节点的左右子树高度差是否小于等于1。-如果任意节点不平衡，则返回-1。-最终返回非-1表示平衡。3.（10分）答案：pythondefmajorityElement(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：-Boyer-Moore投票算法。-遍历数组，遇到候选数则计数+1，否则-1。-当计数为0时更换候选数，最终候选数为答案。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解析：-使用滑动窗口法，`start`和`end`表示窗口左右边界。-遇到重复字符时移动`start`并移除窗口左侧字符。-更新最大长度。三、系统设计题1.（20分）答案：-数据结构：-用户表：`user_id`,`name`,`follows`（存储关注的用户ID列表）。-微博表：`id`,`user_id`,`content`,`time`（时间索引）。-算法：-获取关注人微博：使用`user_id`倒序查询微博，并按时间降序返回。-扩展：-分页：使用`LIMIT`和`OFFSET`。-缓存：使用Redis缓存热点用户微博。2.（20分）答案：-技术选型：-哈希函数：使用Base62编码（`a-z`,`0-9`,`A-Z`）生成短链接。-数据存储：Redis缓存热点链接，MySQL存储长期链接。-关键实现：-唯一性：使用雪花算法或数据库自增ID映射。-解析：通过哈希函数反解原始ID。四、数据库题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