软件工程师面试题及答案含算法

2026年软件工程师面试题及答案含算法一、编程语言基础（3题，每题10分，共30分）地域/行业针对性：大中华区互联网行业，注重Python和Java基础。题目1：请用Python编写一个函数，接收一个字符串列表，返回一个新列表，其中包含所有以大写字母开头的字符串，并按字母顺序排序。题目2：在Java中，解释`String`是不可变对象的原因，并给出一个示例说明不可变性带来的好处。题目3：假设使用Java的`HashMap`存储用户信息（键为用户ID，值为用户名），如何确保在多线程环境下线程安全？请写出代码示例。二、数据结构与算法（5题，每题12分，共60分）地域/行业针对性：阿里巴巴/腾讯风格，考察常用算法与数据结构。题目4：给定一个未排序的整数数组，设计一个时间复杂度为O(n)的算法，找出数组中出现次数超过一半的元素。题目5：用Python实现二叉搜索树（BST）的插入和查找操作，并解释BST的时间复杂度。题目6：编写一个算法，判断一个字符串是否是另一个字符串的子序列。例如，"abc"是"ahbgdc"的子序列。题目7：用Java实现快速排序（QuickSort），并说明其平均时间复杂度和空间复杂度。题目8：设计一个算法，找出无重复数字数组中和为特定值的三元组。例如，给定`[1,2,3,4,5]`，和为7的三元组有`[1,2,4]`和`[2,3,2]`（无重复）。三、系统设计（2题，每题20分，共40分）地域/行业针对性：微软/字节跳动风格，考察分布式与高并发设计。题目9：设计一个简单的微博关注系统，支持用户A关注用户B，并实时通知用户A有用户B的动态。要求说明数据存储方案、API设计及高并发处理思路。题目10：假设需要设计一个高并发的短链接服务（如tinyURL），请说明如何实现短链接生成、解析，并考虑分布式场景下的数据一致性。四、数据库与SQL（2题，每题15分，共30分）地域/行业针对性：大数据公司（如华为、美团）风格，考察MySQL与Redis。题目11：编写SQL查询，找出所有在2025年入职且月薪高于平均月薪的员工，假设表名为`employees`，字段包括`id`、`name`、`salary`、`hire_date`。题目12：解释MySQL中的事务特性（ACID），并说明在什么场景下需要使用事务。五、编程能力（1题，25分）地域/行业针对性：美团/滴滴风格，考察实际工程问题解决能力。题目13：编写一个Java程序，实现一个简单的LRU（LeastRecentlyUsed）缓存，支持get和put操作，要求使用链表和哈希表实现，并解释时间复杂度。答案与解析一、编程语言基础题目1答案：pythondeffilter_uppercase(lst):returnsorted([sforsinlstifsands[0].isupper()])解析：-列表推导式筛选以大写字母开头的字符串。-`sands[0].isupper()`确保字符串非空。-`sorted()`按字母顺序排序。题目2答案：javapublicclassImmutableExample{privatefinalStringvalue;publicImmutableExample(Stringvalue){this.value=value;}publicStringgetValue(){returnvalue;}}解析：-`final`修饰属性，不可修改。-构造器初始化，`getValue()`返回引用，不暴露修改能力。-不可变性优点：线程安全、缓存友好、简化设计（如String池）。题目3答案：javaimportjava.util.concurrent.ConcurrentHashMap;publicclassThreadSafeMap{privateConcurrentHashMap<String,String>map=newConcurrentHashMap<>();publicvoidput(Stringkey,Stringvalue){map.put(key,value);}publicStringget(Stringkey){returnmap.get(key);}}解析：-`ConcurrentHashMap`通过分段锁实现高并发安全性。-相比`Hashtable`，性能更优（非线程阻塞）。二、数据结构与算法题目4答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：-Boyer-Moore算法：遍历数组，候选者更新为当前多数元素。-多数元素定义：出现次数>n/2。题目5答案：pythonclassTreeNode:def__init__(self,key):self.left=Noneself.right=Noneself.val=keydefinsert(root,key):ifrootisNone:returnTreeNode(key)ifkey<root.val:root.left=insert(root.left,key)else:root.right=insert(root.right,key)returnrootdefsearch(root,key):ifrootisNoneorroot.val==key:returnrootreturnsearch(root.left,key)ifkey<root.valelsesearch(root.right,key)解析：-BST性质：左子树<根<右子树。-插入与查找时间复杂度：O(logn)，最坏O(n)。题目6答案：pythondefis_subsequence(s,t):it=iter(t)returnall(cinitforcins)解析：-迭代器`it`遍历`t`，`all()`检查`s`字符按顺序出现。-时间复杂度：O(n)。题目7答案：javapublicclassQuickSort{publicstaticvoidquickSort(int[]arr,intlow,inthigh){if(low<high){intpivot=partition(arr,low,high);quickSort(arr,low,pivot-1);quickSort(arr,pivot+1,high);}}privatestaticintpartition(int[]arr,intlow,inthigh){intpivot=arr[high];inti=low-1;for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(arr,i,j);}}swap(arr,i+1,high);returni+1;}privatestaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}解析：-分治思想：选择基准（pivot），分区交换。-平均时间复杂度：O(nlogn)，空间复杂度：O(logn)。题目8答案：pythondefthree_sum(nums):nums.sort()result=[]n=len(nums)foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnresult解析：-排序后双指针：固定一个数，其余两数用双指针查找。-时间复杂度：O(n²)。三、系统设计题目9答案：1.数据存储：-用户关系：`UserFollowers`表（`follower_id`,`followee_id`）。-动态：`Posts`表（`id`,`user_id`,`content`,`timestamp`）。-实时通知：使用RedisPub/Sub或Kafka。2.API设计：POST/followees/{user_id}#关注用户GET/notifications#获取通知3.高并发处理：-关注操作本地缓存+Redis分布式锁。-动态发布时批量写入Kafka，消费者异步推送到WebSocket。题目10答案：1.短链接生成：-Base62编码（a-z,A-Z,0-9）。-哈希算法：SHA-256+取前6位。2.分布式一致性：-RedisCluster存储短链接与原URL映射。-读写分离+事务保证原子性。四、数据库与SQL题目11答案：sqlSELECTFROMemployeesWHEREYEAR(hire_date)=2025ANDsalary>(SELECTAVG(salary)FROMemployees)解析：-子查询计算平均月薪，外层筛选高于平均值的2025年入职员工。题目12答案：-ACID特性：-原子性（Atomicity）：事务要么全部完成，要么全部回滚。-一致性（Consistency）：事务执行后数据库状态合法。-隔离性（Isolation）：并发事务互不干扰。-持久性（Durability）：事务提交后结果永久保存。-使用场景：账户转账、订单支付等金融操作。五、编程能力题目13答案：javaimportjava.util.HashMap;importjava.util.Map;classLRUCache<K,V>{privatefinalintcapacity;privateMap<K,Node>cache;privateNodehead,tail;publicLRUCache(intcapacity){this.capacity=capacity;cache=newHashMap<>();}publicVget(Kkey){Nodenode=cache.get(key);if(node==null)returnnull;moveToHead(node);returnnode.value;}publicvoidput(Kkey,Vvalue){Nodenode=cache.get(key);if(node!=null){node.value=value;moveToHead(node);}else{if(cache.size()==capacity){cache.remove(tail.key);removeNode(tail);}NodenewNode=newNode(key,value);cache.put(key,newNode);addNode(newNode);}}privatevoidaddNode(Nodenode){node.next=head;node.prev=null;if(head!=null)head.prev=node;head=node;if(tail==null)tail=node;}privatevoidremoveNode(Nodenode){if(node.prev!=null)node.prev.next=node.next;if(node.next!=null)node.next.prev=node.prev;if(node==head)head=node.next;if(node==tail)tail=node.prev;}p