2026年技术工程师面试题及答案集

2026年技术工程师面试题及答案集一、编程语言与数据结构（5题，每题10分，共50分）1.题目（10分）：请用Python实现一个函数，输入一个非负整数n，返回其二进制表示中1的个数。例如，输入5（二进制为101），返回2。答案与解析：pythondefcount_bits(n):returnbin(n).count('1')示例print(count_bits(5))#输出：2解析：-`bin(n)`将数字转换为二进制字符串（如5转为'0b101'）。-`.count('1')`统计字符串中'1'的个数。-时间复杂度O(1)，因为整数二进制位数固定（Python中为64位）。2.题目（10分）：给定一个链表，设计算法删除其中重复的元素，保留每个元素一次。假设链表节点定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next答案与解析：pythondefdelete_duplicates(head):dummy=ListNode(0,head)prev,curr=dummy,headwhilecurr:ifcurr.nextandcurr.val==curr.next.val:whilecurr.nextandcurr.val==curr.next.val:curr=curr.nextprev.next=curr.nextelse:prev=currcurr=curr.nextreturndummy.next解析：-使用虚拟头节点`dummy`简化边界处理。-`prev`始终指向当前无重复节点的最后一个节点。-通过快指针`curr`跳过所有重复节点，时间复杂度O(N)，空间复杂度O(1)。3.题目（10分）：请解释快速排序的时间复杂度，并说明如何优化其最坏情况下的性能。答案与解析：-时间复杂度：-最好/平均：O(NlogN)，每次分区均匀。-最坏：O(N²)，当分区不均匀（如已排序数组）。-优化方法：1.随机化分区：选择基准为随机元素，降低最坏概率。2.三数取中法：用头、中、尾三数的中值作为基准。3.非递归实现：使用栈替代递归，避免栈溢出。4.题目（10分）：用Java实现一个方法，判断一棵二叉树是否为平衡二叉树（左右子树高度差不超过1）。答案与解析：javaclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicbooleanisBalanced(TreeNoderoot){returncheckHeight(root)!=-1;}privateintcheckHeight(TreeNodenode){if(node==null)return0;intleft=checkHeight(node.left);if(left==-1)return-1;intright=checkHeight(node.right);if(right==-1||Math.abs(left-right)>1)return-1;returnMath.max(left,right)+1;}解析：-后序遍历计算左右子树高度，若任一子树不平衡（返回-1），则整棵树不平衡。-时间复杂度O(N)，空间复杂度O(H)（H为树高）。5.题目（10分）：请解释哈希表冲突的两种主要解决方法及其优缺点。答案与解析：-链地址法：-将冲突的键存储在同一个链表中。-优点：实现简单，支持大量冲突。-缺点：查找效率随链表长度增加而下降。-开放寻址法（如线性探测）：-若发生冲突，按固定规则（如+1）寻找下一个空槽。-优点：空间利用率高，无额外指针开销。-缺点：容易产生聚集，降低效率。二、算法与设计（4题，每题12分，共48分）1.题目（12分）：设计一个算法，找出无序数组中第三大的数。假设数组长度至少为3，且所有数互不相同。答案与解析：pythondefthird_max(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:third,second,first=second,first,numelifnum>second:third,second=second,numelifnum>third:third=numreturnthird解析：-维护三个变量记录前三大的数。-时间复杂度O(N)，空间复杂度O(1)。2.题目（12分）：实现一个LRU（最近最少使用）缓存，支持get和put操作。假设缓存容量为3。答案与解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：-使用哈希表记录缓存，列表维护访问顺序。-get时移动元素到末尾，put时移除最旧元素（若满）。3.题题（12分）：设计一个算法，统计一个字符串中所有子字符串的长度为k的回文串数量。例如，输入"abcba"，k=3，输出3（"aba"、"aba"、"bab"）。答案与解析：pythondefcount_palindromic_substrings(s:str,k:int)->int:count=0n=len(s)foriinrange(n):forjinrange(i+k-1,n):substring=s[i:j+1]ifsubstring==substring[::-1]:count+=1returncount解析：-双层循环枚举所有长度为k的子串，检查回文。-时间复杂度O(N²)，空间复杂度O(1)。4.题目（12分）：给定一个m×n的矩阵，设计算法将矩阵顺时针旋转90度。例如：输入：[[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]答案与解析：pythondefrotate(matrix):m=len(matrix)foriinrange(m//2):forjinrange(i,m-i-1):temp=matrix[i][j]matrix[i][j]=matrix[m-j-1][i]matrix[m-j-1][i]=matrix[m-i-1][m-j-1]matrix[m-i-1][m-j-1]=matrix[j][m-i-1]matrix[j][m-i-1]=temp解析：-分层旋转（外层→内层）。-按顺时针方向依次交换四个角的元素。三、系统设计（3题，每题20分，共60分）1.题目（20分）：设计一个高并发的短链接生成服务。假设每天有10亿次访问，每个链接需要唯一且可逆转换（如a-z、0-9）。答案与解析：-方案：1.短码生成：使用62进制（a-z、0-9、A-Z）将ID映射为6位短码（62^6≈56亿）。2.分布式ID生成器：使用Snowflake算法（时间戳+机器ID+序列号）确保唯一性。3.缓存层：Redis缓存热点短链接的原始URL，降低数据库压力。4.数据库设计：sqlCREATETABLEshort_links(short_codeVARCHAR(6)PRIMARYKEY,original_urlTEXT,redirect_countINTDEFAULT0);-性能优化：-短链接查询走内存缓存，数据库仅用于更新计数。-压缩URL前缀（如`/s/`），避免重复DNS解析。2.题目（20分）：设计一个实时消息推送系统（如微信、抖音）。假设支持百万级用户在线，消息需低延迟（<100ms）。答案与解析：-架构：1.接入层：Nginx负载均衡，防DDoS攻击。2.消息队列：Kafka/RabbitMQ处理高并发消息。3.存储层：Redis缓存用户在线状态（Hash结构：`online:uid`）。4.推送服务：gofuncpushMessage(userIDs[]int,msgstring){for_,uid:=rangeuserIDs{ifisOnline(uid){sendToClient(uid,msg)}}}5.客户端长连接：WebSocket或QUIC协议，心跳检测超时。-优化：-离线推送：消息暂存MQ，用户上线后重发。-群聊优化：使用布隆过滤器快速判断用户是否在群内。3.题目（20分）：设计一个分布式限流系统，支持全局限流（如每秒1000请求）。假设服务部署在100台机器上。答案与解析：-方案：1.令牌桶算法：-每台机器维护本地桶（令牌按固定速率生成）。-查询本地桶，若无令牌则拒绝请求，否则消耗令牌。2.Redis实现：pythonimportredisimporttimer=redis.Redis()RATE=1000/1#每秒1000个令牌BUCKET="rate_limit"defis_allowed(user_id):now=int(time.time())withr.pipeline()aspipe:pipe.multi()pipe.incr(BUCKET)pipe.expire(BUCKET,1)pipe.ge