软件开发工程师面试题及解析

2026年软件开发工程师面试题及解析一、编程题（共3题，每题15分，总分45分）题目1（Java编程题，15分）：编写一个Java方法，实现以下功能：给定一个整数数组，返回其中所有和为给定目标值的三元组。要求不重复的三元组，且三元组内的数字顺序从小到大排列。示例：输入：nums=[-1,0,1,2],target=0输出：[[-1,0,1],[-1,2,1]]要求：1.不能使用相同的元素多次（即每个元素只能用一次）。2.返回的三元组按升序排列，且三元组之间不能重复。参考代码：javaimportjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;publicclassThreeSumSolution{publicList<List<Integer>>threeSum(int[]nums,inttarget){List<List<Integer>>result=newArrayList<>();if(nums==null||nums.length<3){returnresult;}Arrays.sort(nums);intn=nums.length;for(inti=0;i<n-2;i++){if(i>0&&nums[i]==nums[i-1]){continue;//跳过重复元素}intleft=i+1;intright=n-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==target){result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(left<right&&nums[left]==nums[left+1]){left++;//跳过重复元素}while(left<right&&nums[right]==nums[right-1]){right--;//跳过重复元素}left++;right--;}elseif(sum<target){left++;}else{right--;}}}returnresult;}publicstaticvoidmain(String[]args){ThreeSumSolutionsolution=newThreeSumSolution();int[]nums={-1,0,1,2};inttarget=0;System.out.println(solution.threeSum(nums,target));}}解析：1.排序：首先对数组进行排序，便于使用双指针法查找三元组，同时避免重复解。2.固定第一个数：使用外层循环固定第一个数`nums[i]`，并跳过重复元素以避免重复解。3.双指针法：使用左指针`left`和右指针`right`分别从`i+1`和`n-1`开始遍历，计算三数之和：-若和等于目标值，则添加到结果中，并移动左右指针跳过重复元素。-若和小于目标值，则左指针右移以增加和。-若和大于目标值，则右指针左移以减少和。4.时间复杂度：排序为`O(nlogn)`，双指针法为`O(n^2)`，整体复杂度为`O(n^2)`。题目2（Python编程题，15分）：编写一个Python函数，实现字符串的KMP（Knuth-Morris-Pratt）算法实现。给定一个主字符串`text`和一个模式字符串`pattern`，返回模式字符串在主字符串中的起始索引位置（若有多个匹配，返回第一个匹配的索引）。若未匹配，返回-1。示例：输入：text="ABABDABACDABABCABAB",pattern="ABABCABAB"输出：10要求：1.实现KMP算法的核心部分——前缀表（部分匹配表）的构建。2.使用前缀表避免重复比较，提高匹配效率。参考代码：pythondefkmp_search(text,pattern):ifnotpattern:return0构建前缀表defbuild_prefix_table(pattern):prefix_table=[0]len(pattern)j=0foriinrange(1,len(pattern)):whilej>0andpattern[i]!=pattern[j]:j=prefix_table[j-1]ifpattern[i]==pattern[j]:j+=1prefix_table[i]=jreturnprefix_tableprefix_table=build_prefix_table(pattern)j=0#pattern的指针foriinrange(len(text)):whilej>0andtext[i]!=pattern[j]:j=prefix_table[j-1]iftext[i]==pattern[j]:j+=1ifj==len(pattern):returni-(j-1)#匹配成功，返回起始索引return-1测试text="ABABDABACDABABCABAB"pattern="ABABCABAB"print(kmp_search(text,pattern))#输出：10解析：1.前缀表构建：-前缀表记录了模式字符串中每个前缀的最长相等前后缀的长度。-例如，模式`"ABABCABAB"`的前缀表为`[0,0,1,2,0,1,2,3,4]`。-构建过程：初始化`j=0`，遍历模式字符串，若当前字符匹配，则`j++`并记录；若不匹配，则根据前缀表回溯。2.匹配过程：-使用两个指针分别遍历`text`和`pattern`，初始`j=0`。-若`text[i]==pattern[j]`，则`j++`；若不匹配，根据前缀表移动`j`。-若`j`到达`pattern`的长度，则匹配成功，返回起始索引。3.时间复杂度：前缀表构建为`O(m)`，匹配过程为`O(n)`，整体为`O(n+m)`。题目3（JavaScript编程题，15分）：编写一个JavaScript函数，实现一个简单的LRU（LeastRecentlyUsed）缓存。LRU缓存支持以下操作：1.`get(key)`：获取键`key`对应的值，若存在则返回值，并更新该键为最近使用；若不存在则返回-1。2.`put(key,value)`：插入或更新键值对，若容量已满，则删除最久未使用的键值对（LRU规则）。示例：LRU缓存容量为2：-put(1,1)→缓存是{1:1}-put(2,2)→缓存是{1:1,2:2}-get(1)→返回1，缓存是{2:2,1:1}（1是最新的）-put(3,3)→去除键2，缓存是{1:1,3:3}（2是最久未使用的）-get(2)→返回-1（未找到）要求：1.使用哈希表和双向链表实现，哈希表记录键到节点的映射，双向链表记录访问顺序。参考代码：javascriptclassListNode{constructor(key,value){this.key=key;this.value=value;this.prev=null;this.next=null;}}classLRUCache{constructor(capacity){this.capacity=capacity;this.cache=newMap();this.head=newListNode(0,0);this.tail=newListNode(0,0);this.head.next=this.tail;this.tail.prev=this.head;}get(key){if(!this.cache.has(key)){return-1;}constnode=this.cache.get(key);this._remove(node);this._add(node);returnnode.value;}put(key,value){if(this.cache.has(key)){this._remove(this.cache.get(key));}constnode=newListNode(key,value);this.cache.set(key,node);this._add(node);if(this.cache.size>this.capacity){constlru=this.head.next;this._remove(lru);this.cache.delete(lru.key);}}_remove(node){this.cache.delete(node.key);node.prev.next=node.next;node.next.prev=node.prev;}_add(node){node.next=this.tail.prev;node.next.prev=node;this.tail.prev=node;node.prev=this.tail.prev;}}//测试constlru=newLRUCache(2);lru.put(1,1);lru.put(2,2);console.log(lru.get(1));//输出：1lru.put(3,3);console.log(lru.get(2));//输出：-1解析：1.双向链表：-使用双向链表记录访问顺序，头节点`head`和尾节点`tail`为哑节点。-新节点插入到`tail`前（最近使用），最久未使用的节点在`head`后。2.哈希表：-使用`Map`记录键到链表节点的映射，实现`O(1)`的`get`和`put`操作。3.操作流程：-`get(key)`：若存在，则移动节点到链表尾部（最近使用），返回值；若不存在，返回-1。-`put(key,value)`：若存在，则更新值并移动到链表尾部；若不存在，插入新节点并移动到链表尾部。-若超出容量，则删除`head`后的节点（最久未使用）。4.时间复杂度：`get`和`put`均为`O(1)`。二、算法题（共3题，每题15分，总分45分）题目4（数学与逻辑题，15分）：给定一个正整数`n`，判断它是否是一个完全平方数。若是的，返回它的平方根；若不是，返回-1。示例：输入：n=16输出：4要求：1.不使用内置函数（如`Math.sqrt`）。2.采用二分查找法实现。参考代码（Python）：pythondefisPerfectSquare(n):ifn<2:return1ifn==1else-1left,right=2,n//2whileleft<=right:mid=(left+right)//2square=midmidifsquare==n:returnmidelifsquare<n:left=mid+1else:right=mid-1return-1测试print(isPerfectSquare(16))#输出：4print(isPerfectSquare(14))#输出：-1解析：1.特殊情况：若`n=0`或`n=1`，直接返回`1`或`-1`。2.二分查找：-初始区间为`[2,n//2]`，因为平方根不会超过`n//2`（对于`n>1`）。-计算中间值`mid`的平方：-若等于`n`，则返回`mid`。-若小于`n`，则左指针右移。-若大于`n`，则右指针左移。3.无解情况：若查找结束仍未找到，返回`-1`。题目5（动态规划题，15分）：给定一个字符串`s`，判断它是否可以由两个相等的字符串拼接而成（即`s=t+t`，其中`t`是某个非空字符串）。示例：输入：s="abab"输出：True要求：1.使用动态规划或中心扩展法解决。参考代码（Python）：pythondefrepeatedSubstringPattern(s):n=len(s)ifn<2:returnFalseforiinrange(1,n//2+1):ifn%i==0:t=s[:i]ift(n//i)==s:returnTruereturnFalse测试print(repeatedSubstringPattern("abab"))#输出：Trueprint(repeatedSubstringPattern("abcabcabc"))#输出：Trueprint(repeatedSubstringPattern("abcdef"))#输出：False解析：1.遍历可能的子串长度：从`1`到`n//2`，因为重复至少需要两个子串。2.检查是否可以重复：若`s`的长度能被`i`整除，则将`s[:i]`重复`n//i`次，若等于`s`，则返回`True`。3.无解情况：若遍历结束未找到，返回`False`。4.时间复杂度：`O(n^2)`（遍历所有可能的子串长度并检查）。题目6（图论题，15分）：给定一个无向图，用邻接矩阵表示。判断该图是否是二分图（即可以将图分成两个不相交的集合，使得每条边的两个顶点分别属于不同的集合）。示例：邻接矩阵：[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]输出：True（可分成集合{0,2}和{1,3}）要求：1.使用深度优先搜索（DFS）或广度优先搜索（BFS）实现。参考代码（Python）：pythondefisBipartite(graph):n=len(graph)color=[-1]n#-1表示未染色，0和1表示两种颜色defdfs(node,c):color[node]=cforneighborinrange(n):ifgraph[node][neighbor]==1:ifcolor[neighbor]==-1:ifnotdfs(neighbor,1-c):returnFalseelifcolor[neighbor]==color[node]:returnFalsereturnTrueforiinrange(n):ifcolor[i]==-1:ifnotdfs(i,0):returnFalsereturnTrue测试graph=[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]print(isBipartite(graph))#输出：True解析：1.染色法：-使用`color`数组记录每个节点的颜色，初始为`-1`（未染色）。-选择一个未染色的节点，使用DFS或BFS染色，并确保相邻节点的颜色相反。2.DFS过程：-对每个未染色的节点，尝试染一种颜色（如`0`），并递归染色所有相邻节点（染相反颜色）。-若发现相邻节点颜色相同，则不是二分图。3.无解情况：若所有节点染色完成且无冲突，则图是二分图。4.时间复杂度：`O(n+m)`，其中`n`是节点数，`m`是边数。三、系统设计题（共1题，25分）题目7（分布式系统设计题，25分）：设计一个简单的分布式URL短链接服务（如tinyURL）。该服务应支持以下功能：1.将长URL转换为短URL。2.将短URL解析为原始长URL。3.要求系统高可用、可扩展，并支持高并发访问。要求：1.描述系统架构、主要组件及其职责。2.说明URL生成和解析的算法。3.讨论高可用、可扩展和并发处理方案。参考答案：1.系统架构：-前端服务（APIGateway）：接收用户请求，负载均衡