联想研发工程师面试题详解

2026年联想研发工程师面试题详解一、编程基础与算法（共5题，总分25分）题目1（5分）：问题描述：给定一个非负整数数组`nums`和一个目标值`target`，请找出数组中和为目标值`target`的两个数，并返回它们的索引。你可以假设每个输入都只对应一个解，并且不能重复使用同一个元素。示例：输入：`nums=[2,7,11,15]`,`target=9`输出：`[0,1]`（因为`nums[0]+nums[1]=2+7=9`）要求：-编写时间复杂度为O(n)的解决方案。-代码需支持Python或Java。答案（Python）：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[]解析：使用哈希表（字典）存储每个数字及其索引，遍历数组时，检查`target-num`是否已存在于哈希表中。若存在，返回对应索引；否则，将当前数字加入哈希表。时间复杂度为O(n)，空间复杂度为O(n)。题目2（5分）：问题描述：实现一个函数`reverse(x)`，输入一个32位的有符号整数`x`，返回其反转后的整数。如果反转后的整数超出了32位有符号整数的范围（即`-2^31<=x<=2^31-1`），则返回0。示例：输入：`x=123`输出：`321`输入：`x=-123`输出：`-321`输入：`x=1534236469`输出：`0`（因为反转后`964632435`超出范围）要求：-代码需处理整数溢出问题。-代码需支持Python或Java。答案（Python）：pythondefreverse(x):INT_MAX=231-1INT_MIN=-231result=0sign=-1ifx<0else1x=abs(x)whilex!=0:pop=x%10x//=10检查溢出ifresult>(INT_MAX-pop)//10:return0result=result10+popreturnsignresult解析：通过取模和整除操作逐位反转数字，同时检查反转过程中是否会发生溢出。若当前`result`超过`INT_MAX`的前导部分（即`(INT_MAX-pop)//10`），则直接返回0。最终结果需根据原数的符号还原。题目3（5分）：问题描述：给定一个包含`'a'`到`'z'`的字母异位词数组`words`，请返回所有字母异位词组。字母异位词指由相同字母重新排列组成的单词，如`"eat"`和`"tea"`是字母异位词。示例：输入：`words=["eat","tea","tan","ate","nat","bat"]`输出：[["eat","tea","ate"],["tan","nat"],["bat"]]要求：-编写时间复杂度为O(nk)的解决方案（k为单词平均长度）。-代码需支持Python或Java。答案（Python）：pythonfromcollectionsimportdefaultdictdefgroup_anagrams(words):anagrams=defaultdict(list)forwordinwords:sorted_word=''.join(sorted(word))anagrams[sorted_word].append(word)returnlist(anagrams.values())解析：通过将每个单词排序后作为键，将原单词加入对应列表。排序后的字母异位词会得到相同的键，从而将所有异位词分组。时间复杂度为O(nklogk)，其中n为单词数量，k为单词平均长度。题目4（5分）：问题描述：给定一个包含`mxn`列表格的`board`和一个字符串`word`，判断`word`是否存在于`board`中。你可以假设每个单元格中的字母只能访问一次。示例：输入：`board=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]``word="ABCCED"`输出：`True`要求：-编写深度优先搜索（DFS）解决方案。-代码需支持Python或Java。答案（Python）：pythondefexist(board,word):m,n=len(board),len(board[0])directions=[(0,1),(1,0),(0,-1),(-1,0)]defdfs(x,y,index):ifindex==len(word):returnTrueifnot(0<=x<mand0<=y<nandboard[x][y]==word[index]):returnFalsetemp,board[x][y]=board[x][y],'#'fordx,dyindirections:ifdfs(x+dx,y+dy,index+1):returnTrueboard[x][y]=tempreturnFalseforiinrange(m):forjinrange(n):ifdfs(i,j,0):returnTruereturnFalse解析：使用深度优先搜索遍历每个单元格，当找到匹配的字母时，递归检查四个方向（上下左右）。为防止重复访问，将当前字母标记为`#`，回溯时还原。若找到完整单词，返回`True`。题目5（5分）：问题描述：给定一个无重复元素的整数数组`nums`，返回该数组所有可能的子集（幂集）。示例：输入：`nums=[1,2,3]`输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]要求：-编写回溯算法解决方案。-代码需支持Python或Java。答案（Python）：pythondefsubsets(nums):res=[]subset=[]defbacktrack(start):res.append(subset.copy())foriinrange(start,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnres解析：通过回溯算法生成所有可能的子集。每次选择当前数字或跳过，递归遍历所有可能性。`subset`存储当前路径，`res`存储所有子集。时间复杂度为O(2^n)，空间复杂度为O(n)。二、数据结构与系统设计（共4题，总分20分）题目6（5分）：问题描述：设计一个LRU（最近最少使用）缓存机制。缓存应支持以下操作：-`get(key)`：获取键`key`对应的值。如果键存在，返回值并更新其使用时间；否则返回-1。-`put(key,value)`：插入或更新键`key`及其值`value`。如果键已存在，更新其值并更新使用时间；如果缓存已满，则删除最近最少使用的元素。要求：-使用双向链表和哈希表实现。-代码需支持Python或Java。答案（Python）：pythonclassNode: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,self.tail=Node(),Node()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-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnode:node.value=valueself._move_to_head(node)else:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]解析：LRU缓存通过双向链表维护访问顺序，哈希表实现O(1)时间复杂度的查找。`get`操作将节点移动到头部（最近使用），`put`操作插入新节点并移动到头部，若超出容量则删除尾部节点。题目7（5分）：问题描述：设计一个Trie（前缀树）数据结构，支持以下操作：-`insert(word)`：插入一个单词。-`search(word)`：如果单词完全匹配，返回`True`；否则返回`False`。-`startsWith(prefix)`：如果存在以`prefix`为前缀的单词，返回`True`；否则返回`False`。要求：-使用字典实现节点。-代码需支持Python或Java。答案（Python）：pythonclassTrieNode:def__init__(self):self.children={}self.is_end=FalseclassTrie:def__init__(self):self.root=TrieNode()definsert(self,word:str)->None:node=self.rootforcharinword:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.is_end=Truedefsearch(self,word:str)->bool:node=self._find(word)returnnodeisnotNoneandnode.is_enddefstartsWith(self,prefix:str)->bool:returnself._find(prefix)isnotNonedef_find(self,word:str):node=self.rootforcharinword:ifcharnotinnode.children:returnNonenode=node.children[char]returnnode解析：Trie树通过节点嵌套字典实现，每个节点存储子节点和是否为单词结尾的标志。`insert`操作逐字符插入，`search`检查完整匹配，`startsWith`检查前缀匹配。时间复杂度为O(m)，m为单词长度。题目8（5分）：问题描述：设计一个任务调度器，模拟CPU执行多个任务。任务用字母表示（如`A`,`B`,`C`），每个任务有一个执行时间`time`（单位为秒）。CPU按照以下规则执行：-每个时间单位，CPU可以执行一个任务。-如果多个任务可用，优先执行字典序最小的任务。-如果没有任务可用，CPU空闲（等待下一个任务）。示例：输入：`tasks=["A","A","A","B","B","B"]`,`time=2`输出：`["A","B","A","B","A","B"]`（每个任务执行2秒）要求：-编写队列或优先队列实现。-代码需支持Python或Java。答案（Python）：pythonimportheapqdefschedule_tasks(tasks,time):task_counts={}fortaskintasks:task_counts[task]=task_counts.get(task,0)+1max_heap=[(-count,task)fortask,countintask_counts.items()]heapq.heapify(max_heap)res=[]whilemax_heap:temp=[]for_inrange(time):ifnotmax_heap:fortintemp:heapq.heappush(max_heap,t)breakcount,task=heapq.heappop(max_heap)res.append(task)ifcount<-1:temp.append((count+1,task))whiletemp:heapq.heappush(max_heap,temp.pop())returnres解析：使用最大堆（优先队列）存储任务数量，优先执行数量最多的任务。每次执行`time`个任务，若堆为空则等待。时间复杂度为O(nlogm)，n为任务数量，m为最大执行时间。题目9（5分）：问题描述：设计一个分布式缓存系统，支持以下功能：-`get(key)`：获取键`key`对应的值。若键存在于本地，返回本地值；否则向其他节点请求。-`put(key,value)`：将键值对存储到本地缓存。若本地已存在，则更新值；否则向其他节点同步。要求：-节点间使用RPC（远程过程调用）通信。-代码需支持Python或Java。答案（概念性设计，Python示例）：python假设每个节点维护本地缓存和RPC客户端classCacheNode:def__init__(self,node_id):self.cache={}self.node_id=node_idself.rpcs={}#RPC客户端映射defget(self,key):ifkeyinself.cache:returnself.cache[key]向其他节点请求fornodeinself.rpcs:ifkeyinnode.cache:value=self.rpcs[node].get(key)self.cache[key]=valuereturnvaluereturnNonedefput(self,key,value):self.cache[key]=value同步到其他节点fornodeinself.rpcs:self.rpcs[node].put(key,value)解析：分布式缓存通过每个节点维护本地缓存和RPC客户端实现。`get`操作先查本地，若不存在则向其他节点请求；`put`操作更新本地并同步到其他节点。实际实现需考虑网络延迟和一致性协议（如Raft）。三、系统设计（共2题，总分15分）题目10（7分）：问题描述：设计一个高并发的短链接生成系统。要求：-每个请求生成一个唯一的短链接（如`/abc123`）。-高并发场景下，生成速度需满足每秒百万级请求。-支持快速跳转至原始长链接。要求：-说明设计思路，包括数据结构和算法。-考虑分布式部署和缓存优化。答案（设计思路）：1.短链接生成：-使用自增ID或Snowflake算法生成唯一标识符。-将ID转换为Base62编码（`a-z`,`A-Z`,`0-9`），减少链接长度。2.数据存储：-使用Redis或Memcached存储短链接和原始链接的映射，支持