2026年软件工程师面试预测题

2026年软件工程师面试预测题一、编程实现题（共3题，每题20分，总计60分）1.题1（20分）：设计一个高效的LRU（最近最少使用）缓存机制题目描述：请实现一个LRU缓存机制，支持以下操作：-`get(key)`:获取键`key`对应的值，如果键不存在，返回-1。-`put(key,value)`:插入或更新键值对，如果缓存容量已满，则删除最近最少使用的项。要求：-使用双向链表和哈希表实现，时间复杂度为O(1)。-假设缓存容量为`capacity`，初始为空。示例：plaintextLRUCachecache=newLRUCache(2);cache.put(1,1);//缓存是{1=1}cache.put(2,2);//缓存是{1=1,2=2}cache.get(1);//返回1cache.put(3,3);//去除键2，缓存是{1=1,3=3}cache.get(2);//返回-1(未找到)cache.put(4,4);//去除键1，缓存是{4=4,3=3}cache.get(1);//返回-1(未找到)cache.get(3);//返回3cache.get(4);//返回4答案与解析：javaclassLRUCache{//定义双向链表节点privateclassNode{intkey;intvalue;Nodeprev;Nodenext;Node(intkey,intvalue){this.key=key;this.value=value;}}privateHashMap<Integer,Node>map;privateintcapacity;privateNodehead,tail;publicLRUCache(intcapacity){this.capacity=capacity;map=newHashMap<>();head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicintget(intkey){Nodenode=map.get(key);if(node==null)return-1;//将节点移动到头部moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenode=map.get(key);if(node!=null){node.value=value;moveToHead(node);}else{NodenewNode=newNode(key,value);map.put(key,newNode);addToHead(newNode);if(map.size()>capacity){NodetoDel=tail.prev;map.remove(toDel.key);removeNode(toDel);}}}privatevoidaddToHead(Nodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}privatevoidremoveNode(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}}解析：-双向链表：用于记录访问顺序，头节点为最近访问，尾节点为最久未访问。-哈希表：用于O(1)时间查找节点，存储`key`到节点的映射。-核心操作：-`get`时，节点从链表中移动到头部（最近使用）。-`put`时，若`key`已存在，更新值并移动到头部；若不存在，添加新节点并移动到头部，如果超出容量，删除尾节点。2.题2（20分）：实现一个二叉树的最大深度（最大高度）计算题目描述：给定一个二叉树，请计算其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点数。要求：-使用递归或迭代方法实现。-假设二叉树节点定义如下：plaintextclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}示例：plaintext输入：[3,9,20,null,null,15,7]3/\920\/\157输出：3答案与解析：javapublicclassSolution{publicintmaxDepth(TreeNoderoot){if(root==null)return0;intleft=maxDepth(root.left);intright=maxDepth(root.right);returnMath.max(left,right)+1;}}解析：-递归方法：-递归计算左子树和右子树的最大深度，取较大值加1（当前节点）。-时间复杂度O(n)，n为节点数。-迭代方法（BFS）：-使用队列层序遍历，每层深度加1。3.题3（20分）：实现一个字符串的URL解码与编码题目描述：请分别实现URL的编码和编码功能。要求：-编码：将特殊字符（如`%20`表示空格）转换为`%`后跟两位十六进制数。-解码：将`%`后跟两位十六进制数转换为对应字符。示例：plaintext编码："HelloWorld!"->"Hello%20World%21"解码："Hello%20World%21"->"HelloWorld!"答案与解析：javaimportjava.util.;publicclassURLCodec{//URL编码publicstaticStringencode(Strings){StringBuildersb=newStringBuilder();for(charc:s.toCharArray()){if(c==''){sb.append("%20");}elseif(c=='!'){sb.append("%21");}elseif(c=='#'){sb.append("%23");}else{sb.append(c);}}returnsb.toString();}//URL解码publicstaticStringdecode(Strings){StringBuildersb=newStringBuilder();inti=0;while(i<s.length()){if(s.charAt(i)=='%'){if(i+2>=s.length())returnsb.toString();//格式错误Stringhex=s.substring(i+1,i+3);charc=(char)Integer.parseInt(hex,16);sb.append(c);i+=3;}else{sb.append(s.charAt(i));i++;}}returnsb.toString();}publicstaticvoidmain(String[]args){Stringoriginal="HelloWorld!";Stringencoded=encode(original);Stringdecoded=decode(encoded);System.out.println("Encoded:"+encoded);//Hello%20World%21System.out.println("Decoded:"+decoded);//HelloWorld!}}解析：-编码：遍历字符串，将空格替换为`%20`，其他特殊字符按需替换。-解码：遍历字符串，遇到`%`时读取后两位十六进制数并转换为字符，否则直接添加。二、系统设计题（共2题，每题20分，总计40分）1.题4（20分）：设计一个高并发的短链接生成系统题目描述：请设计一个短链接生成系统，要求：-输入长链接，输出短链接（如`/abc123`）。-支持高并发访问，秒级生成大量短链接。-短链接唯一且易于记忆。要求：-系统需支持分布式部署，可水平扩展。-需考虑短链接的生成、存储、查询和回源（将短链接解析为长链接）流程。答案与解析：plaintext1.系统架构：-前端服务：接收长链接请求，返回短链接。-短链接生成服务：生成唯一ID（如62进制编码）。-数据库：存储长链接与短链接的映射。-负载均衡器：分发请求到多个前端服务。2.短链接生成算法：-使用自增ID，转换为62进制（a-z,A-Z,0-9）：javaprivatestaticfinalchar[]ALPHABET="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();privatelongcounter=0;publicStringgenerateShortLink(){counter++;returnencode(counter);}privateStringencode(longnum){StringBuildersb=newStringBuilder();while(num>0){sb.append(ALPHABET[(int)(num%62)]);num/=62;}returnsb.reverse().toString();}-为提高并发性，可使用分布式ID生成器（如TwitterSnowflake算法）。3.数据存储：-使用Redis缓存热点短链接，降低数据库压力。-数据库使用分片或Sharding存储短链接映射。4.回源流程：-前端服务接收到短链接，查询数据库或缓存。-返回对应的长链接。5.高并发优化：-使用限流熔断机制防止过载。-异步处理生成和查询请求。解析：-短链接生成：使用62进制编码自增ID，确保唯一性和简洁性。-分布式部署：通过负载均衡和数据库分片支持高并发。-缓存优化：Redis缓存热点数据，加速查询。2.题5（20分）：设计一个实时消息推送系统（如微信、钉钉）题目描述：请设计一个实时消息推送系统，要求：-支持多用户、多设备消息推送。-消息可离线缓存，用户上线后推送未读消息。-支持消息优先级和重试机制。要求：-系统需支持消息的存储、分发和状态跟踪。-需考虑高可用性和可扩展性。答案与解析：plaintext1.系统架构：-消息中心：负责消息的接收、存储和分发。-消息队列：如Kafka或RabbitMQ，处理高并发消息。-用户设备服务：管理用户设备状态（在线/离线）。-数据库：存储用户信息、消息记录和状态。2.核心流程：-消息发送：plaintext发送者->消息中心（消息队列）消息中心存储消息，分配唯一ID和优先级。-消息推送：plaintext消息中心->用户设备服务（查询设备状态）如果在线，直接推送；离线则存入离线消息表。-离线消息处理：plaintext用户上线->用户设备服务（扫描离线消息）将离线消息推送给用户。3.数据存储：-消息表：存储消息内容、发送者、接收者、时间戳、状态（待推/已推）。-离线消息表：存储离线消息和用户ID。-用户设备表：存储用户ID和设备ID、状态（在线/离线）。4.高可用与扩展：-消息中心使用集群部署，负载均衡。-数据库读写分离，分片存储消息记录。-消息重试机制：未成功推送的消息重新入队。5.优先级与重试：-消息分配优先级（如紧急消息优先推送）。-使用定时任务或死信队列处理重试消息。解析：-消息队列：保证消息的顺序和可靠性。-离线缓存：存储未送达的消息，用户上线后补发。-优先级与重试：确保重要消息优先，失败重试。三、算法与数据结构题（共2题，每题20分，总计40分）1.题6（20分）：设计一个支持动态添加和删除节点的有序链表题目描述：请设计一个有序链表，支持以下操作：-`add(intval)`:添加节点，保持链表有序。-`remove(intval)`:删除指定值的节点。-`find(intval)`:查找节点，返回是否存在。要求：-链表节点定义如下：plaintextclassListNode{intval;ListNodenext;ListNode(intval){this.val=val;}}示例：plaintext有序链表初始为空：add(3)->3add(1)->1->3add(2)->1->2->3find(2)->trueremove(2)->1->3答案与解析：javaclassSortedLinkedList{privateListNodehead;publicSortedLinkedList(){head=null;}//添加节点publicvoidadd(intval){ListNodenewNode=newListNode(val);if(head==null||head.val>=newNode.val){newNode.next=head;head=newNode;}else{ListNodecurrent=head;while(current.next!=null&¤t.next.val<newNode.val){current=current.next;}newNode.next=current.next;current.next=newNode;}}//删除节点publicvoidremove(intval){if(head==null)return;if(head.val==val){head=head.next;return;}ListNodecurrent=head;while(current.next!=null&¤t.next.val!=val){current=current.next;}if(current.next!=null){current.next=current.next.next;}}//查找节点publicbooleanfind(intval){ListNodecurrent=head;while(current!=null){if(current.val==val)returntrue;current=current.next;}returnfalse;}}解析：-添加节点：遍历链表，找到插入位置。-删除节点：找到目标节点并断开连接。-查找节点：遍历链表判断是否存在。2.题7（20分）：设计一个有效的括号匹配算法题目描述：请实现一个函数，判断字符串中的括号（`()`,`[]`,`{}`）是否有效匹配。要求：-使用栈结构实现，时间复杂度O(n)。-括号必须以正确顺序匹配，如`{[()]}`有效，`{[(])}`无效。示例：plaintextisValid("()")->trueisValid("()[]{}")->tr