2026年聯(lián)想集團(tuán)研發(fā)工程師面試題及答案詳解一、編程題（共3題，每題20分，總分60分）1.編程題1（20分）：題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)字符串，返回該字符串中所有唯一字符的列表（按出現(xiàn)順序）。例如，輸入`"leetcode"`，返回`[l,e,t,c,o,d,e]`（注意`e`出現(xiàn)了兩次，不應(yīng)包含在結(jié)果中）。要求：-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度O(1)（假設(shè)字符集固定，如ASCII）答案與解析：pythondefunique_chars(s:str)->list:假設(shè)字符集為ASCII，使用兩個(gè)固定長度的數(shù)組記錄字符出現(xiàn)情況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']解析：-使用固定長度的布爾數(shù)組`seen`記錄每個(gè)ASCII字符是否出現(xiàn)過，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。-遍歷字符串，對(duì)于每個(gè)字符，檢查其ASCII值是否已記錄，若未記錄則添加到結(jié)果列表中。-最終返回按順序出現(xiàn)的唯一字符。2.編程題2（20分）：題目：設(shè)計(jì)一個(gè)無鎖（lock-free）隊(duì)列，支持`enqueue`和`dequeue`操作。假設(shè)使用Python實(shí)現(xiàn)，需考慮多線程環(huán)境下的并發(fā)問題。要求：-使用`threading`模塊實(shí)現(xiàn)多線程-隊(duì)列使用列表存儲(chǔ)元素-確保并發(fā)安全答案與解析：pythonimportthreadingfromcollectionsimportdequeclassLockFreeQueue:def__init__(self):self.queue=deque()self.lock=threading.Lock()#Python中無鎖實(shí)現(xiàn)較復(fù)雜，此處用鎖模擬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本身不支持無鎖編程，此處用鎖模擬。實(shí)際工業(yè)級(jí)實(shí)現(xiàn)需使用原子操作（如CAS）。-`enqueue`將元素添加到隊(duì)列末尾，`dequeue`從隊(duì)首移除元素。-若要嚴(yán)格無鎖實(shí)現(xiàn)，需使用原子操作（如`threading.atomic`或C語言中的CAS），但Python不支持。3.編程題3（20分）：題目：給定一個(gè)二叉樹，請(qǐng)實(shí)現(xiàn)`serialize`和`deserialize`函數(shù)，將樹序列化為字符串，并能從字符串反序列化回樹。假設(shè)使用前序遍歷序列化。要求：-樹節(jié)點(diǎn)定義如下：`classTreeNode:def__init__(self,val=0,left=None,right=None)`-序列化格式為`"root.left.val,root.right.val,..."`，如`1,2,#,#,3,4,#,#,#`（#表示空節(jié)點(diǎn)）答案與解析：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`使用前序遍歷，空節(jié)點(diǎn)用`#`表示。-`deserialize`反向解析字符串，使用迭代器處理節(jié)點(diǎn)。-避免遞歸棧溢出，采用迭代方式反序列化。二、系統(tǒng)設(shè)計(jì)題（共2題，每題20分，總分40分）1.系統(tǒng)設(shè)計(jì)題1（20分）：題目：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接生成系統(tǒng)，要求：-輸入任意URL，輸出6位短鏈接（如`/a1b2c3`）-支持高并發(fā)請(qǐng)求（如每秒百萬請(qǐng)求）-鏈接唯一且可快速生成要求：-說明核心組件設(shè)計(jì)-描述數(shù)據(jù)結(jié)構(gòu)-優(yōu)化高并發(fā)方案答案與解析：核心組件設(shè)計(jì)：1.URL入庫模塊：-使用Redis或內(nèi)存緩存，存儲(chǔ)`(長URL,短碼)`映射。-短碼使用自增ID或隨機(jī)算法生成。2.反查模塊：-接收短鏈接請(qǐng)求，從緩存中查詢長URL。3.負(fù)載均衡：-使用Nginx或HAProxy分發(fā)請(qǐng)求到多個(gè)后端節(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)：-Redis哈希表：`{"a1b2c3":"/oldurl"}`-短碼生成：使用Base62（a-z、A-Z、0-9，共62個(gè)字符）。高并發(fā)優(yōu)化：-緩存穿透：Redis設(shè)置過期時(shí)間，避免熱點(diǎn)數(shù)據(jù)失效。-限流：使用令牌桶算法控制請(qǐng)求速率。-異步處理：使用消息隊(duì)列（如Kafka）異步生成短碼。偽代碼示例：pythondefgenerate_short_url(long_url):short_code=base62_encode(increment_id())redis.set(short_code,long_url)returnf"/{short_code}"2.系統(tǒng)設(shè)計(jì)題2（20分）：題目：設(shè)計(jì)一個(gè)實(shí)時(shí)數(shù)據(jù)監(jiān)控平臺(tái)，要求：-支持百萬級(jí)設(shè)備接入-實(shí)時(shí)收集設(shè)備上報(bào)數(shù)據(jù)（如溫度、濕度）-數(shù)據(jù)存儲(chǔ)支持查詢和統(tǒng)計(jì)要求：-說明數(shù)據(jù)流架構(gòu)-描述存儲(chǔ)方案-優(yōu)化實(shí)時(shí)性答案與解析：數(shù)據(jù)流架構(gòu)：1.數(shù)據(jù)采集層：-使用MQTT或WebSocket接收設(shè)備數(shù)據(jù)，支持發(fā)布/訂閱模式。-設(shè)備接入時(shí)分配唯一ID。2.數(shù)據(jù)處理層：-使用Flink或SparkStreaming實(shí)時(shí)處理數(shù)據(jù)，過濾異常值。3.數(shù)據(jù)存儲(chǔ)層：-時(shí)序數(shù)據(jù)存入InfluxDB，關(guān)系型數(shù)據(jù)存入MySQL。存儲(chǔ)方案：-InfluxDB：時(shí)序數(shù)據(jù)庫，支持毫秒級(jí)查詢。-MySQL：存儲(chǔ)設(shè)備元數(shù)據(jù)（ID、類型等）。實(shí)時(shí)性優(yōu)化：-批處理與流處理結(jié)合：熱點(diǎn)數(shù)據(jù)實(shí)時(shí)處理，冷數(shù)據(jù)離線統(tǒng)計(jì)。-數(shù)據(jù)分區(qū)：按設(shè)備ID或時(shí)間范圍分區(qū)，加速查詢。偽代碼示例：pythondefprocess_device_data(device_id,data):ifvalidate_data(data):influxdb.write(data)mysql.update_device_status(device_id)三、算法題（共2題，每題20分，總分40分）1.算法題1（20分）：題目：給定一個(gè)無序數(shù)組，包含重復(fù)元素，請(qǐng)找到數(shù)組中不重復(fù)的子數(shù)組的最長長度（子數(shù)組內(nèi)元素不重復(fù)）。要求：-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度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解析：-使用滑動(dòng)窗口（`left`和`right`指針）遍歷數(shù)組。-`seen`字典記錄元素上一次出現(xiàn)的位置。-若當(dāng)前元素已存在，則移動(dòng)`left`指針到重復(fù)元素后一位。2.算法題2（20分）：題目：設(shè)計(jì)一個(gè)算法，判斷一個(gè)無向圖是否是二分圖（BipartiteGraph）。二分圖定義：可將頂點(diǎn)分成兩個(gè)集合，使任意邊連接的頂點(diǎn)分別屬于不同集合。要求：-使用DFS或BFS實(shí)現(xiàn)-時(shí)間復(fù)雜度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