软件开发工程师面试题及算法能力测试含答案

2026年软件开发工程师面试题及算法能力测试含答案一、编程语言基础（共5题，每题2分）考察内容：Java语言基础、面向对象编程、集合框架、异常处理等。题目1（2分）：编写Java代码，实现一个自定义的`MyArrayList`类，继承自`java.util.ArrayList`，并添加一个方法`removeDuplicates()`，用于删除列表中的重复元素（保持唯一性，顺序不变）。请写出类的定义和`removeDuplicates()`方法的核心代码。题目2（2分）：在Java中，以下哪个关键字用于声明一个不可变类（ImmutableClass）？请解释其作用原理。题目3（2分）：请解释`HashMap`和`TreeMap`的主要区别，并说明在什么场景下优先选择使用`HashMap`。题目4（2分）：Java中的`volatile`关键字有什么作用？它与`synchronized`有什么不同？题目5（2分）：编写Java代码，实现一个方法`reverseWords`，输入一个字符串，输出单词顺序反转后的字符串（如输入"helloworld"，输出"worldhello"）。要求不使用额外的字符串拼接方法。二、数据结构与算法（共8题，每题3分）考察内容：数组、链表、树、图、排序、查找、动态规划等。题目6（3分）：给定一个无重复元素的整数数组`nums`，返回所有可能的子集（集合）。例如，输入`[1,2,3]`，输出`[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`。请使用递归方法实现。题目7（3分）：请实现一个`LruCache`（最近最少使用缓存）类，使用双向链表和哈希表实现，支持`get`和`put`操作。要求`get`和`put`的时间复杂度为O(1)。题目8（3分）：编写代码，实现快速排序（QuickSort）算法，要求使用递归方式实现，并说明其时间复杂度和稳定性。题目9（3分）：给定一个二叉树，判断其是否是平衡二叉树（左右子树高度差不超过1）。请写出核心判断逻辑。题目10（3分）：请解释动态规划（DynamicProgramming）的核心思想，并举例说明如何解决背包问题（KnapsackProblem）。题目11（3分）：给定一个字符串`s`和一个字典`wordDict`，判断`s`是否可以由字典中的单词拼接而成（不要求字典顺序）。例如，`s="leetcode"`,`wordDict=["leet","code"]`，返回`true`。请使用回溯法实现。题目12（3分）：编写代码，实现二分查找（BinarySearch）算法，要求处理目标值不存在的情况，返回最接近目标值的索引。题目13（3分）：给定一个包含`n`个整数的数组，设计一个算法，找到和最大的连续子数组（如输入`[-2,1,-3,4,-1,2,1,-5,4]`，输出`6`，对应子数组`[4,-1,2,1]`）。请使用动态规划方法解决。三、系统设计与数据库（共5题，每题4分）考察内容：分布式系统、缓存、数据库设计、高并发等。题目14（4分）：设计一个简单的微博系统，需要支持用户发布动态、关注/取消关注、获取关注者动态流等功能。请说明主要的数据表设计（至少3张表）和核心接口逻辑。题目15（4分）：请解释Redis和Memcached的区别，并说明在高并发场景下如何使用Redis实现秒杀系统的核心逻辑。题目16（4分）：设计一个数据库表，存储用户的订单信息，包含订单ID、用户ID、商品ID、数量、价格、下单时间等字段。请说明主键、外键、索引的设计思路。题目17（4分）：如何解决分布式系统中的CAP问题？请解释BASE理论的核心思想。题目18（4分）：在MySQL中，`InnoDB`和`MyISAM`存储引擎的主要区别是什么？在什么场景下优先选择`InnoDB`？四、编程实践（共3题，每题6分）考察内容：实际编码能力、问题解决能力。题目19（6分）：编写代码，实现一个简单的LRU（LeastRecentlyUsed）缓存，使用Java实现。缓存容量为`capacity`，支持`get(key)`和`put(key,value)`操作。当缓存满时，需要删除最久未使用的元素。请写出核心逻辑。题目20（6分）：给定一个字符串`s`，找到其中最长的回文子串（如输入"babad"，输出"bab"或"aba"）。请使用动态规划方法实现。题目21（6分）：设计一个简单的秒杀系统，用户点击秒杀按钮后，系统需要验证库存、扣减库存并返回结果。请说明核心逻辑，并考虑高并发下的优化方案（如分布式锁、限流等）。答案与解析一、编程语言基础（答案）题目1（Java）：javaimportjava.util.ArrayList;publicclassMyArrayList<E>extendsArrayList<E>{publicvoidremoveDuplicates(){Set<E>seen=newHashSet<>();Iterator<E>it=this.iterator();while(it.hasNext()){Eitem=it.next();if(seen.contains(item)){it.remove();}else{seen.add(item);}}}}解析：使用`HashSet`记录已出现元素，遍历列表时删除重复项。时间复杂度O(n)。题目2（Java）：`final`关键字。不可变类要求所有字段均为`final`且不可修改，并提供所有getter方法，不提供setter方法。其原理是通过不修改对象状态来保证线程安全。题目3（HashMapvsTreeMap）：-`HashMap`：基于哈希表，时间复杂度O(1)；无排序顺序。-`TreeMap`：基于红黑树，时间复杂度O(logn)；按键自然顺序排序。优先选择`HashMap`的场景：需要快速查找、插入、删除；不需要排序。题目4（volatilevssynchronized）：-`volatile`：保证内存可见性，禁止指令重排，但不保证原子性。-`synchronized`：保证原子性和内存可见性，但性能较低。区别：`volatile`适用于轻量级同步，`synchronized`适用于复杂状态同步。题目5（Java反转单词）：javapublicStringreverseWords(Strings){String[]words=s.trim().split("\\s+");StringBuildersb=newStringBuilder();for(inti=words.length-1;i>=0;i--){sb.append(words[i]);if(i>0)sb.append("");}returnsb.toString();}解析：按空格拆分字符串，反转单词顺序后拼接。二、数据结构与算法（答案）题目6（子集递归）：javapublicList<List<Integer>>subsets(int[]nums){List<List<Integer>>res=newArrayList<>();backtrack(nums,0,newArrayList<>(),res);returnres;}voidbacktrack(int[]nums,intstart,List<Integer>temp,List<List<Integer>>res){res.add(newArrayList<>(temp));for(inti=start;i<nums.length;i++){temp.add(nums[i]);backtrack(nums,i+1,temp,res);temp.remove(temp.size()-1);}}解析：递归遍历所有选择，回溯时撤销选择。题目7（LRUCache）：javaclassLRUCache{privateMap<Integer,Node>map;privateNodehead,tail;privateintcapacity;classNode{intkey,val;Nodeprev,next;Node(intkey,intval){this.key=key;this.val=val;}}publicLRUCache(intcapacity){this.capacity=capacity;map=newHashMap<>();head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicintget(intkey){if(map.containsKey(key)){Nodenode=map.get(key);moveToHead(node);returnnode.val;}return-1;}publicvoidput(intkey,intvalue){if(map.containsKey(key)){Nodenode=map.get(key);node.val=value;moveToHead(node);}else{if(map.size()==capacity){map.remove(tail.prev.key);removeNode(tail.prev);}NodenewNode=newNode(key,value);map.put(key,newNode);addNode(newNode);}}privatevoidmoveToHead(Nodenode){removeNode(node);addNode(node);}privatevoidaddNode(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;}}解析：使用双向链表维护最近使用顺序，哈希表实现O(1)查找。题目8（快速排序）：javapublicvoidquickSort(int[]arr,intleft,intright){if(left<right){intpivotIndex=partition(arr,left,right);quickSort(arr,left,pivotIndex-1);quickSort(arr,pivotIndex+1,right);}}intpartition(int[]arr,intleft,intright){intpivot=arr[right];inti=left-1;for(intj=left;j<right;j++){if(arr[j]<=pivot){i++;swap(arr,i,j);}}swap(arr,i+1,right);returni+1;}voidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}解析：时间复杂度O(nlogn)，平均情况；不稳定排序。题目9（平衡二叉树）：javapublicbooleanisBalanced(TreeNoderoot){returncheckHeight(root)!=-1;}intcheckHeight(TreeNodenode){if(node==null)return0;intleft=checkHeight(node.left);if(left==-1)return-1;intright=checkHeight(node.right);if(right==-1)return-1;if(Math.abs(left-right)>1)return-1;returnMath.max(left,right)+1;}解析：递归检查左右子树高度差，若不平衡返回-1。题目10（动态规划）：核心思想：将问题分解为子问题，存储子问题解避免重复计算。背包问题：javaintknapsack(intW,int[]weights,int[]values){intn=weights.length;int[][]dp=newint[n+1][W+1];for(inti=1;i<=n;i++){for(intw=1;w<=W;w++){if(weights[i-1]<=w){dp[i][w]=Math.max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1]);}else{dp[i][w]=dp[i-1][w];}}}returndp[n][W];}解析：状态转移方程：`dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])`。题目11（回溯法）：javapublicbooleanwordBreak(Strings,List<String>wordDict){boolean[]dp=newboolean[s.length()+1];dp[0]=true;for(inti=1;i<=s.length();i++){for(Stringword:wordDict){intlen=word.length();if(i>=len&&s.substring(i-len,i).equals(word)&&dp[i-len]){dp[i]=true;break;}}}returndp[s.length()];}解析：动态规划预处理前缀是否在字典中。题目12（二分查找）：javapublicintbinarySearch(int[]arr,inttarget){intleft=0,right=arr.length-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target)returnmid;elseif(arr[mid]<target)left=mid+1;elseright=mid-1;}returnleft;//返回最接近的索引}解析：处理目标不存在时返回插入位置。题目13（最大子数组和）：javapublicintmaxSubArray(int[]nums){intmaxSum=nums[0];intcurrentSum=nums[0];for(inti=1;i<nums.length;i++){currentSum=Math.max(nums[i],currentSum+nums[i]);maxSum=Math.max(maxSum,currentSum);}returnmaxSum;}解析：Kadane算法，动态维护当前最大和。三、系统设计与数据库（答案）题目14（微博系统设计）：-数据表：1.`users`：`user_id`(PK),`name`,`email`,`created_at`2.`tweets`：`tweet_id`(PK),`user_id`(FK),`content`,`created_at`3.`follows`：`follower_id`(FK),`followee_id`(FK)-核心接口：-`publishTweet(user_id,content)`：插入到`tweets`表。-`getFollowersFeed(user_id)`：按时间倒序查询`follows`中`followee_id==user_id`的用户的`tweets`。题目15（RedisvsMemcached）：-区别：Redis支持持久化、多种数据类型（列表、集合）；Memcached仅支持键值对。-秒杀逻辑：使用Redis`setnx`锁库存，`EXPIRE`设置过期时间。题目16（订单表设计）：sqlCREATETABLEorders(order_idINTAUTO_INCREMENTPRIMARYKEY,user_idINTNOTNULL,product_idINTNOTNULL,quantityINTNOTNULL,priceDECIMAL(10,2)NOTNULL,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(user_id),FOREIGNKEY(product_id)REFERENCESproducts(product_id),INDEXidx_user_time(user_id,order_time));解析：主键+外键+索引优化查询。题目17（分布式CAP）：-CAP理论：一致性（Consistency）、可用性（Availability）、分区容错性（PartitionTolerance）。-BASE理论：基本可用（BasicallyAvailable）、软状态（Softstate）、最终一致性（Eventualconsistency）。解决方案：优先选择CP，牺牲部分可用性（如分布式锁）。题目18（InnoDBvsMyISAM）：-InnoDB