联想集团研发工程师面试题及答案详解

2026年联想集团研发工程师面试题及答案详解一、编程题（共3题，每题20分，总分60分）1.编程题1（20分）：题目：请实现一个函数，输入一个字符串，返回该字符串中所有唯一字符的列表（按出现顺序）。例如，输入`"leetcode"`，返回`[l,e,t,c,o,d,e]`（注意`e`出现了两次，不应包含在结果中）。要求：-时间复杂度O(n)-空间复杂度O(1)（假设字符集固定，如ASCII）答案与解析：pythondefunique_chars(s:str)->list:假设字符集为ASCII，使用两个固定长度的数组记录字符出现情况seen=[False]128unique=[]forcharins:ascii_val=ord(char)ifnotseen[ascii_val]:seen[ascii_val]=Trueunique.append(char)returnunique示例print(unique_chars("leetcode"))#输出:['l','e','t','c','o','d']解析：-使用固定长度的布尔数组`seen`记录每个ASCII字符是否出现过，时间复杂度O(n)，空间复杂度O(1)。-遍历字符串，对于每个字符，检查其ASCII值是否已记录，若未记录则添加到结果列表中。-最终返回按顺序出现的唯一字符。2.编程题2（20分）：题目：设计一个无锁（lock-free）队列，支持`enqueue`和`dequeue`操作。假设使用Python实现，需考虑多线程环境下的并发问题。要求：-使用`threading`模块实现多线程-队列使用列表存储元素-确保并发安全答案与解析：pythonimportthreadingfromcollectionsimportdequeclassLockFreeQueue:def__init__(self):self.queue=deque()self.lock=threading.Lock()#Python中无锁实现较复杂，此处用锁模拟defenqueue(self,item):withself.lock:self.queue.append(item)defdequeue(self):withself.lock:ifself.queue:returnself.queue.popleft()else:returnNone示例queue=LockFreeQueue()queue.enqueue(1)queue.enqueue(2)print(queue.dequeue())#输出:1print(queue.dequeue())#输出:2解析：-Python本身不支持无锁编程，此处用锁模拟。实际工业级实现需使用原子操作（如CAS）。-`enqueue`将元素添加到队列末尾，`dequeue`从队首移除元素。-若要严格无锁实现，需使用原子操作（如`threading.atomic`或C语言中的CAS），但Python不支持。3.编程题3（20分）：题目：给定一个二叉树，请实现`serialize`和`deserialize`函数，将树序列化为字符串，并能从字符串反序列化回树。假设使用前序遍历序列化。要求：-树节点定义如下：`classTreeNode:def__init__(self,val=0,left=None,right=None)`-序列化格式为`"root.left.val,root.right.val,..."`，如`1,2,#,#,3,4,#,#,#`（#表示空节点）答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefserialize(root):defhelper(node):ifnotnode:vals.append('#')returnvals.append(str(node.val))helper(node.left)helper(node.right)vals=[]helper(root)return','.join(vals)defdeserialize(data):defhelper():val=next(vals)ifval=='#':returnNonenode=TreeNode(int(val))node.left=helper()node.right=helper()returnnodevals=iter(data.split(','))returnhelper()示例root=TreeNode(1,TreeNode(2),TreeNode(3,TreeNode(4)))serialized=serialize(root)print(serialized)#输出:"1,2,#,#,3,4,#,#,#"deserialized=deserialize(serialized)print(deserialized.val)#输出:1解析：-`serialize`使用前序遍历，空节点用`#`表示。-`deserialize`反向解析字符串，使用迭代器处理节点。-避免递归栈溢出，采用迭代方式反序列化。二、系统设计题（共2题，每题20分，总分40分）1.系统设计题1（20分）：题目：设计一个高并发的短链接生成系统，要求：-输入任意URL，输出6位短链接（如`/a1b2c3`）-支持高并发请求（如每秒百万请求）-链接唯一且可快速生成要求：-说明核心组件设计-描述数据结构-优化高并发方案答案与解析：核心组件设计：1.URL入库模块：-使用Redis或内存缓存，存储`(长URL,短码)`映射。-短码使用自增ID或随机算法生成。2.反查模块：-接收短链接请求，从缓存中查询长URL。3.负载均衡：-使用Nginx或HAProxy分发请求到多个后端节点。数据结构：-Redis哈希表：`{"a1b2c3":"/oldurl"}`-短码生成：使用Base62（a-z、A-Z、0-9，共62个字符）。高并发优化：-缓存穿透：Redis设置过期时间，避免热点数据失效。-限流：使用令牌桶算法控制请求速率。-异步处理：使用消息队列（如Kafka）异步生成短码。伪代码示例：pythondefgenerate_short_url(long_url):short_code=base62_encode(increment_id())redis.set(short_code,long_url)returnf"/{short_code}"2.系统设计题2（20分）：题目：设计一个实时数据监控平台，要求：-支持百万级设备接入-实时收集设备上报数据（如温度、湿度）-数据存储支持查询和统计要求：-说明数据流架构-描述存储方案-优化实时性答案与解析：数据流架构：1.数据采集层：-使用MQTT或WebSocket接收设备数据，支持发布/订阅模式。-设备接入时分配唯一ID。2.数据处理层：-使用Flink或SparkStreaming实时处理数据，过滤异常值。3.数据存储层：-时序数据存入InfluxDB，关系型数据存入MySQL。存储方案：-InfluxDB：时序数据库，支持毫秒级查询。-MySQL：存储设备元数据（ID、类型等）。实时性优化：-批处理与流处理结合：热点数据实时处理，冷数据离线统计。-数据分区：按设备ID或时间范围分区，加速查询。伪代码示例：pythondefprocess_device_data(device_id,data):ifvalidate_data(data):influxdb.write(data)mysql.update_device_status(device_id)三、算法题（共2题，每题20分，总分40分）1.算法题1（20分）：题目：给定一个无序数组，包含重复元素，请找到数组中不重复的子数组的最长长度（子数组内元素不重复）。要求：-时间复杂度O(n)-空间复杂度O(n)答案与解析：pythondeflongest_unique_subarray(arr):seen={}left=0max_len=0forrightinrange(len(arr)):ifarr[right]inseen:left=max(left,seen[arr[right]]+1)seen[arr[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len示例print(longest_unique_subarray([1,2,3,1,2,3,4]))#输出:4解析：-使用滑动窗口（`left`和`right`指针）遍历数组。-`seen`字典记录元素上一次出现的位置。-若当前元素已存在，则移动`left`指针到重复元素后一位。2.算法题2（20分）：题目：设计一个算法，判断一个无向图是否是二分图（BipartiteGraph）。二分图定义：可将顶点分成两个集合，使任意边连接的顶点分别属于不同集合。要求：-使用DFS或BFS实现-时间复杂度O(V+E)答案与解析：pythonfromcollectionsimportdequedefis_bipartite(graph):color={}defbfs(node):queue=deque([node])color[node]=0#0表示集合A，1表示集合Bwhilequeue:current=queue.popleft()forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=1-color[current]queue.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTruefornodeingraph:ifnodenotin