程序员面试攻略及编程题解析

2026年程序员面试攻略及编程题解析一、编程题（共5题，总分100分）1.算法题（共2题，每题50分）题目1（50分）：题目描述：给定一个整数数组`nums`和一个整数`target`，请找出数组中和为目标值`target`的两个数，并返回它们的索引。你可以假设每个输入都只会对应一个答案，且不能重复使用同一个元素。示例：输入：`nums=[2,7,11,15]`,`target=9`输出：`[0,1]`解释：因为`nums[0]+nums[1]==9`，返回`[0,1]`。要求：-时间复杂度：O(n)-空间复杂度：O(n)答案与解析：答案：pythondeftwo_sum(nums,target):num_to_index={}forindex,numinenumerate(nums):complement=target-numifcomplementinnum_to_index:return[num_to_index[complement],index]num_to_index[num]=indexreturn[]解析：1.思路分析：-使用哈希表（字典）记录每个数字及其索引，可以在O(1)时间内查找补数。-遍历数组时，对于每个数字`num`，计算`complement=target-num`，检查`complement`是否已在哈希表中：-若存在，返回`[complement的索引,当前索引]`。-若不存在，将`num`及其索引存入哈希表。-若遍历完数组未找到，返回空列表。2.复杂度分析：-时间复杂度：O(n)，只需遍历数组一次。-空间复杂度：O(n)，最坏情况下哈希表存储所有数字。题目2（50分）：题目描述：给你一个字符串`s`，请你将`s`分成尽可能多的子串，要求每个子串都是回文串。返回分割后子串的数量。示例：输入：`s="aab"`输出：`2`解释：可以分割成`["aa","b"]`或`["a","a","b"]`，最大分割数量为2。要求：-子串分割后不能重新排序。-可以使用动态规划或中心扩展法解决。答案与解析：答案：pythondefmax_palindrome分割(s):n=len(s)dp=[[False]nfor_inrange(n)]count=[0]n#count[i]表示以s[0..i]分割的最大回文子串数量初始化单字符为回文foriinrange(n):dp[i][i]=Truecount[i]=1初始化长度为2的子串foriinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truecount[i]=max(count[i],2)动态规划处理更长子串forlengthinrange(3,n+1):#子串长度从3到nforiinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truecount[j]=max(count[j],count[i+1]+1)returncount[n-1]解析：1.思路分析：-使用动态规划（DP）解决，定义`dp[i][j]`表示`s[i..j]`是否为回文串。-初始化：-单字符`dp[i][i]`为回文。-长度为2的子串`s[i..i+1]`，若`s[i]==s[i+1]`为回文。-状态转移：-对于长度`length>=3`的子串`s[i..j]`，若`s[i]==s[j]`且`s[i+1..j-1]`为回文，则`s[i..j]`为回文。-同时记录分割数量：`count[j]=max(count[j],count[i+1]+1)`，表示以`s[0..j]`分割的最大回文子串数量。2.复杂度分析：-时间复杂度：O(n²)，双重循环遍历所有子串。-空间复杂度：O(n²)，存储`dp`数组。2.数据结构与系统设计题（共3题，每题33.3分）题目3（33.3分）：题目描述：设计一个LRU（LeastRecentlyUsed）缓存机制，支持以下操作：-`LRU(`)初始化缓存容量为`capacity`。-`get(key)`返回键`key`对应的值，若不存在返回-1。访问键`key`后将其标记为最近使用。-`put(key,value)`插入或更新键值对，若缓存已满则移除最久未使用的键。要求：-使用双向链表和哈希表实现，确保`get`和`put`操作时间复杂度为O(1)。答案与解析：答案：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}初始化伪头部和伪尾部self.head=DLinkedNode()self.tail=DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):添加节点到头部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):移除节点prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):移动节点到头部self._remove_node(node)self._add_node(node)def_pop_tail(self):弹出尾部节点res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1将访问的节点移动到头部self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:移除尾部节点tail=self._pop_tail()delself.cache[tail.key]else:更新节点值node.value=valueself._move_to_head(node)解析：1.思路分析：-双向链表：用于存储最近使用的节点，头节点为最近使用，尾节点为最久未使用。-哈希表：用于快速查找节点，键为`key`，值为链表节点。-操作实现：-`get(key)`：若存在，移动节点到头部并返回值；若不存在，返回-1。-`put(key,value)`：若存在，更新值并移动到头部；若不存在，创建新节点并添加到头部，若超出容量则移除尾部节点。2.复杂度分析：-时间复杂度：O(1)，所有操作均通过哈希表和链表节点直接访问。-空间复杂度：O(capacity)，哈希表和链表存储最多`capacity`个节点。题目4（33.3分）：题目描述：设计一个Twitter-like系统，支持以下功能：-`postTweet(user_id,tweet_id)`：用户`user_id`发布一条`tweet_id`。-`getFeed(user_id,k)`：返回用户`user_id`的`k`条最新推文。推文来自用户`user_id`及其关注的人（包括自己），按时间降序排列。-`follow(follower_id,followee_id)`：`follower_id`开始关注`followee_id`。-`unfollow(follower_id,followee_id)`：`follower_id`取消关注`followee_id`（不能取消关注自己）。要求：-`getFeed`操作应高效处理大量关注者，时间复杂度尽可能低。答案与解析：答案：pythonfromcollectionsimportdefaultdict,dequeimporttimeclassTwitter:def__init__(self):self.user_tweets=defaultdict(deque)#用户推文队列self.user_follows=defaultdict(set)#用户关注列表self.timestamp=0#时间戳defpostTweet(self,user_id:int,tweet_id:int)->None:self.user_tweets[user_id].appendleft((self.timestamp,tweet_id))self.timestamp+=1限制推文数量iflen(self.user_tweets[user_id])>100:self.user_tweets[user_id].pop()defgetFeed(self,user_id:int,k:int)->list:res=[]users=self.user_follows[user_id]|{user_id}#关注者和自己foruidinusers:fortweetinself.user_tweets[uid]:res.append(tweet)按时间降序排列并取前k条res.sort(reverse=True,key=lambdax:x[0])return[tweet[1]fortweetinres[:k]]deffollow(self,follower_id:int,followee_id:int)->None:iffollower_id!=followee_id:self.user_follows[follower_id].add(followee_id)defunfollow(self,follower_id:int,followee_id:int)->None:iffollower_id!=followee_id:self.user_follows[follower_id].discard(followee_id)解析：1.思路分析：-数据结构：-`user_tweets`：字典，键为`user_id`，值为`(timestamp,tweet_id)`的队列（使用`deque`实现O(1)头尾操作）。-`user_follows`：字典，键为`user_id`，值为关注的`followee_id`集合。-操作实现：-`postTweet`：将`(timestamp,tweet_id)`添加到用户队首，并更新时间戳。限制推文数量为100条。-`getFeed`：合并关注者和自己的推文，按时间降序排列并取前`k`条。-`follow`：添加关注关系（不能关注自己）。-`unfollow`：移除关注关系（不能取消关注自己）。2.复杂度分析：-时间复杂度：`getFeed`为O(nlogn)，n为关注者总数。可优化为优先队列实现O(nlogk)。-空间复杂度：O(n)，存储所有用户推文和关注关系。题目5（33.3分）：题目描述：设计一个简单的文件系统，支持以下操作：-`createFile(path,content)`：在`path`创建文件并写入`content`。若父目录不存在则创建。-`readFile(path)`：返回`path`文件的内容。-`createDir(path)`：创建目录。若父目录不存在则创建。-`readDir(path)`：返回`path`目录下的所有文件和子目录名称。要求：-使用树形结构或嵌套字典实现，支持多级目录。答案与解析：答案：pythonclassFileSystemNode:def__init__(self,is_file=False,content=""):self.is_file=is_fileself.content=contentself.children={}#字典，键为名称，值为子节点classFileSystem:def__init__(self):self.root=FileSystemNode()#根目录def_split_path(self,path):parts=path.strip("/").split("/")returnpartsdef_create_node(self,node,parts,idx):ifidx==len(parts):returnname=parts[idx]ifnamenotinnode.children:node.children[name]=FileSystemNode()self._create_node(node.children[name],parts,idx+1)defcreateFile(self,path:str,content:str)->None:parts=self._split_path(path)file_name=parts[-1]parent_path="/".join(parts[:-1])ifparent_path=="":parent=self.rootelse:parent=self._get_node(self.root,self._split_path(parent_path))ifparentisNone:parent=FileSystemNode()self._create_node(self.root,self._split_path(parent_path),0)file_node=FileSystemNode(is_file=True,content=content)parent.children[file_name]=file_nodedefreadFile(self,path:str)->str:parts=self._split_path(path)node=self._get_node(self.root,parts)ifnodeandnode.is_file:returnnode.contentreturn""defcreateDir(self,path:str)->None:parts=self._split_path(path)dir_name=parts[-1]parent_path="/".join(parts[:-1])ifparent_path=="":parent=self.rootelse:parent=self._get_node(self.root,self._split_path(parent_path))ifparentisNone:parent=FileSystemNode()self._create_node(se