2026年高级软件工程师面试宝典及参考答案

2026年高级软件工程师面试宝典及参考答案一、编程题（共5题，每题20分，总分100分）1.编程题1（20分）：设计一个高效的算法，找出数组中第K个最大的元素。要求不使用排序，时间复杂度不超过O(n)。javaimportjava.util.Random;publicclassKthLargestElement{publicstaticintfindKthLargest(int[]nums,intk){if(nums==null||nums.length<k){thrownewIllegalArgumentException("Invalidinput");}intleft=0,right=nums.length-1;Randomrand=newRandom();while(true){intpivotIndex=left+rand.nextInt(right-left+1);intnewPivotIndex=partition(nums,left,right,pivotIndex);if(newPivotIndex==k-1){returnnums[newPivotIndex];}elseif(newPivotIndex>k-1){right=newPivotIndex-1;}else{left=newPivotIndex+1;}}}privatestaticintpartition(int[]nums,intleft,intright,intpivotIndex){intpivot=nums[pivotIndex];swap(nums,pivotIndex,right);intstoreIndex=left;for(inti=left;i<right;i++){if(nums[i]>pivot){swap(nums,storeIndex,i);storeIndex++;}}swap(nums,right,storeIndex);returnstoreIndex;}privatestaticvoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}publicstaticvoidmain(String[]args){int[]nums={3,2,1,5,6,4};intk=2;System.out.println("The"+k+"thlargestelementis"+findKthLargest(nums,k));}}答案解析：该算法采用随机化快速选择算法，通过随机选择一个枢轴元素进行划分，从而在期望线性时间内找到第K个最大的元素。具体步骤如下：1.在数组中选择一个随机枢轴元素，并将其与数组末尾元素交换。2.将数组划分为两部分，左边部分的所有元素都大于枢轴元素，右边部分的所有元素都小于等于枢轴元素。3.根据枢轴元素的位置与K的关系，递归地在左边或右边部分继续查找。时间复杂度为O(n)，空间复杂度为O(1)。2.编程题2（20分）：实现一个LRU（LeastRecentlyUsed）缓存，支持get和put操作，要求时间复杂度为O(1)。javaimportjava.util.HashMap;importjava.util.Map;publicclassLRUCache{privatestaticclassNode{intkey;intvalue;Nodeprev;Nodenext;Node(intkey,intvalue){this.key=key;this.value=value;}}privateMap<Integer,Node>cache;privateNodehead,tail;privateintcapacity;publicLRUCache(intcapacity){this.capacity=capacity;cache=newHashMap<>();head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicintget(intkey){Nodenode=cache.get(key);if(node==null){return-1;}moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenode=cache.get(key);if(node!=null){node.value=value;moveToHead(node);}else{NodenewNode=newNode(key,value);cache.put(key,newNode);addToHead(newNode);if(cache.size()>capacity){NodetoRemove=tail.prev;removeNode(toRemove);cache.remove(toRemove.key);}}}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}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;}publicstaticvoidmain(String[]args){LRUCachelru=newLRUCache(2);lru.put(1,1);lru.put(2,2);System.out.println(lru.get(1));//returns1lru.put(3,3);//evictskey2System.out.println(lru.get(2));//returns-1(notfound)lru.put(4,4);//evictskey1System.out.println(lru.get(1));//returns-1(notfound)System.out.println(lru.get(3));//returns3System.out.println(lru.get(4));//returns4}}答案解析：LRU缓存通过双向链表和哈希表实现，确保get和put操作的时间复杂度为O(1)。具体步骤如下：1.使用双向链表维护元素的访问顺序，头节点表示最近访问的元素，尾节点表示最久未访问的元素。2.使用哈希表存储键和链表节点的映射关系，以便快速访问节点。3.get操作时，将访问的节点移动到链表头部，并返回其值。4.put操作时，如果键已存在，更新其值并移动到链表头部；如果键不存在，创建新节点并添加到链表头部，如果超出容量则删除链表尾部的节点。3.编程题3（20分）：实现一个简单的分布式锁，要求在高并发环境下保证互斥性和顺序性。javaimportjava.util.concurrent.ConcurrentHashMap;importjava.util.concurrent.locks.Lock;importjava.util.concurrent.locks.ReentrantLock;publicclassDistributedLock{privatestaticfinalConcurrentHashMap<String,Lock>lockMap=newConcurrentHashMap<>();publicstaticLockgetLock(Stringresource){returnlockMputeIfAbsent(resource,k->newReentrantLock());}publicstaticvoidmain(String[]args){Stringresource="resource1";Locklock=getLock(resource);Threadthread1=newThread(()->{try{lock.lock();System.out.println("Thread1acquiredthelock");Thread.sleep(1000);}catch(InterruptedExceptione){e.printStackTrace();}finally{lock.unlock();System.out.println("Thread1releasedthelock");}});Threadthread2=newThread(()->{try{lock.lock();System.out.println("Thread2acquiredthelock");Thread.sleep(1000);}catch(InterruptedExceptione){e.printStackTrace();}finally{lock.unlock();System.out.println("Thread2releasedthelock");}});thread1.start();thread2.start();}}答案解析：分布式锁通过ConcurrentHashMap和ReentrantLock实现，确保在高并发环境下保证互斥性和顺序性。具体步骤如下：1.使用ConcurrentHashMap存储资源与锁的映射关系，确保线程安全。2.获取锁时，先从哈希表中获取对应的锁，如果不存在则创建新的ReentrantLock。3.ReentrantLock确保同一时间只有一个线程可以持有锁，从而实现互斥性。4.通过ReentrantLock的默认行为，确保锁的获取顺序性。4.编程题4（20分）：实现一个简单的分布式队列，要求支持异步入队和出队操作。javaimportjava.util.concurrent.BlockingQueue;importjava.util.concurrent.LinkedBlockingQueue;publicclassDistributedQueue{privatestaticfinalBlockingQueue<String>queue=newLinkedBlockingQueue<>();publicstaticvoidenqueue(Stringitem){try{queue.put(item);System.out.println("Enqueued:"+item);}catch(InterruptedExceptione){Thread.currentThread().interrupt();e.printStackTrace();}}publicstaticStringdequeue(){try{Stringitem=queue.take();System.out.println("Dequeued:"+item);returnitem;}catch(InterruptedExceptione){Thread.currentThread().interrupt();e.printStackTrace();returnnull;}}publicstaticvoidmain(String[]args){Threadproducer=newThread(()->{for(inti=0;i<10;i++){enqueue("Item"+i);try{Thread.sleep(100);}catch(InterruptedExceptione){e.printStackTrace();}}});Threadconsumer=newThread(()->{for(inti=0;i<10;i++){dequeue();try{Thread.sleep(150);}catch(InterruptedExceptione){e.printStackTrace();}}});producer.start();consumer.start();}}答案解析：分布式队列通过BlockingQueue实现，支持异步入队和出队操作。具体步骤如下：1.使用LinkedBlockingQueue作为队列实现，确保线程安全。2.入队操作使用put方法，出队操作使用take方法，这两个方法都支持阻塞。3.生产者线程通过put方法将元素入队，消费者线程通过take方法将元素出队。4.通过BlockingQueue的阻塞特性，确保队列的先进先出顺序性和线程安全。5.编程题5（20分）：设计一个简单的分布式事务管理器，要求支持跨多个节点的原子性操作。javaimportjava.util.HashMap;importjava.util.Map;importjava.util.concurrent.ConcurrentHashMap;publicclassDistributedTransactionManager{privatestaticfinalMap<String,Boolean>transactionMap=newConcurrentHashMap<>();publicstaticvoidbeginTransaction(StringtransactionId){transactionMap.put(transactionId,false);System.out.println("Transaction"+transactionId+"started");}publicstaticvoidcommitTransaction(StringtransactionId){if(transactionMap.getOrDefault(transactionId,false)){transactionMap.remove(transactionId);System.out.println("Transaction"+transactionId+"committed");}else{System.out.println("Transaction"+transactionId+"cannotbecommitted,somenodesfailed");}}publicstaticvoidabortTransaction(StringtransactionId){transactionMap.remove(transactionId);System.out.println("Transaction"+transactionId+"aborted");}publicstaticvoidperformOperation(StringtransactionId,Stringnode,booleansuccess){if(success){transactionMap.put(transactionId,true);}else{transactionMap.put(transactionId,false);}}publicstaticvoidmain(String[]args){StringtransactionId="tx1";beginTransaction(transactionId);performOperation(transactionId,"node1",true);performOperation(transactionId,"node2",true);performOperation(transactionId,"node3",false);commitTransaction(transactionId);}}答案解析：分布式事务管理器通过ConcurrentHashMap实现，支持跨多个节点的原子性操作。具体步骤如下：1.使用ConcurrentHashMap存储事务ID和操作成功状态，确保线程安全。2.beginTransaction方法用于开始事务，将事务ID和初始状态存储在哈希表中。3.performOperation方法用于执行操作，根据操作是否成功更新事务状态。4.commitTransaction方法用于提交事务，只有当所有操作都成功时才提交事务。5.abortTransaction方法用于中止事务，将事务ID从哈希表中移除。二、系统设计题（共3题，每题33分，总分99分）1.系统设计题1（33分）：设计一个高并发的短链接系统，要求支持高并发访问、快速生成和解析短链接，并支持自定义短链接。答案解析：高并发短链接系统设计需要考虑以下几个关键点：1.短链接生成与解析：-使用哈希算法（如MD5、SHA-256）将长链接进行哈希处理，生成固定长度的短链接。-为了支持自定义短链接，可以提供一个映射表将自定义短链接与长链接关联。2.高并发访问：-使用分布式缓存（如Redis）存储短链接与长链接的映射关系，提高访问速度。-使用负载均衡器（如Nginx）分发请求到多个后端服务器，提高系统吞吐量。3.数据存储：-使用分布式数据库（如Cassandra、HBase）存储短链接与长链接的映射关系，确保数据的高可用性和可扩展性。4.API设计：-提供RESTfulAPI接口，支持短链接生成、解析和自定义短链接功能。-接口示例：-POST`/shorten`：生成短链接。-GET`/{shortLink}`：解析短链接。-POST`/shorten/{customShortLink}`：自定义短链接。2.系统设计题2（33分）：设计一个高并发的实时消息推送系统，要求支持多端同步、消息离线存储和消息推送可靠性。答案解析：高并发实时消息推送系统设计需要考虑以下几个关键点：1.消息存储：-使用消息队列（如Kafka、RabbitMQ）存储消息，确保消息的可靠性和顺序性。-使用分布式数据库（如Cassandra、HBase）存储用户与设备关系，确保消息的精准