2026年计算机工程师面试题及答案

2026年计算机工程师面试题及答案一、编程实现题（共3题，每题20分）1.题目（20分）：编写一个函数，实现将一个非负整数转换为罗马数字。罗马数字由以下字符组成：`I`(1),`V`(5),`X`(10),`L`(50),`C`(100),`D`(500),`M`(1000)。要求：-输入：非负整数（0≤n≤3999）。-输出：对应的罗马数字字符串。-示例：-输入：3→输出："III"-输入：58→输出："LVIII"-输入：1994→输出："MCMXCIV"2.题目（20分）：给定一个二叉树，判断其是否是平衡二叉树。平衡二叉树的定义：对于任意节点，其左右子树的高度差不超过1。要求：-使用递归方法实现。-返回布尔值结果。-示例：-输入：[3,9,20,null,null,15,7]→输出：true-输入：[1,2,2,3,null,null,3,4,null,null,4]→输出：false3.题目（20分）：实现一个LRU（最近最少使用）缓存。缓存容量为`capacity`，使用哈希表和双向链表实现。要求：-支持get和put操作。-get：返回键对应的值，如果不存在返回-1。-put：插入或更新键值对，如果超出容量则删除最久未使用的项。-示例：-输入：capacity=2,["LRUCache","put","put","get","put","get","get"]→输出：[null,null,null,1,-1,3,4]二、算法设计题（共2题，每题25分）1.题目（25分）：设计一个算法，找出数组中未排序的“最小”和“最大”元素。假设数组中至少有两个元素。要求：-时间复杂度O(n)。-示例：-输入：[3,1,2,5,4]→输出：[1,5]-输入：[2,3,1,4,5]→输出：[1,5]2.题目（25分）：给定一个字符串`s`，判断其是否可以通过回溯法拆分为至少两个回文子字符串。回溯法需要遍历所有可能的拆分方式。要求：-返回布尔值结果。-示例：-输入："aab"→输出：true（拆分为"a"和"ab"或"aab"）-输入："aabba"→输出：false三、系统设计题（共1题，40分）1.题目（40分）：设计一个高并发的短链接服务。要求：-支持将长URL转换为短URL，并支持反向解析。-高可用、高扩展性。-需要说明：1.数据存储方案（如Redis+分布式缓存）。2.短链接生成算法（如Base62编码）。3.负载均衡和容灾方案。4.伪代码或流程图（可选）。答案及解析一、编程实现题1.题目答案：pythondefint_to_roman(num):val=[1000,900,500,400,100,90,50,40,10,9,5,4,1]syms=["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]roman_num=""i=0whilenum>0:for_inrange(num//val[i]):roman_num+=syms[i]num-=val[i]i+=1returnroman_num解析：-使用两个列表`val`和`syms`分别存储罗马数字的数值和符号。-从最大值开始，逐个匹配并减去对应数值，拼接符号。-时间复杂度O(1)，因为罗马数字的符号数量固定。2.题目答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：-使用递归计算左右子树的高度，同时判断平衡性。-若高度差超过1或子树不平衡，则整棵树不平衡。-时间复杂度O(n)，每个节点遍历一次。3.题目答案：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.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]returndef_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_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_pop_tail(self):node=self.tail.prevself._remove_node(node)returnnode解析：-使用双向链表维护访问顺序，头为最近访问，尾为最久未访问。-哈希表`cache`实现O(1)的get和put操作。-超出容量时删除链表尾部节点。二、算法设计题1.题目答案：pythondeffind_min_max(nums):min_val,max_val=float('inf'),float('-inf')fornuminnums:ifnum<min_val:min_val=numifnum>max_val:max_val=numreturn[min_val,max_val]解析：-遍历数组一次，分别记录最小和最大值。-时间复杂度O(n)，空间复杂度O(1)。2.题目答案：pythondefcan_split(s:str)->bool:defis_palindrome(sub):returnsub==sub[::-1]defbacktrack(start):ifstart==len(s):returnTrueforendinrange(start+1,len(s)+1):ifis_palindrome(s[start:end])andbacktrack(end):returnTruereturnFalsereturnbacktrack(0)解析：-使用回溯法枚举所有可能的拆分方式。-检查当前子串是否为回文，如果是则继续递归剩余部分。-若能找到至少一个有效拆分，返回true。三、系统设计题1.题目答案：方案概述：-数据存储：-使用Redis存储短链接和长链接的映射，支持高并发读写。-分布式缓存（如Memcached）减轻Redis压力。-短链接生成：-使用Base62编码（0-9,a-z,A-Z）将ID转换为6位短链接。-ID可通过自增ID或分布式ID生成器（如Snowflake算法）获取。-负载均衡：-使用Nginx或HAProxy分发请求到多个后端服务。-配置读写分离，主节点负责写，从节点负责读。-容灾方案：-Redis集群模式，避免单点故障。-定期备份短链接映射关系。伪代码示例：python短链接生成defgenerate_short_id(long_id):base=62digits="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"short_id