软件工程师笔试面试题集含算法解析

2026年软件工程师笔试面试题集含算法解析一、编程语言基础（3题，每题10分）1.题目：请用Java实现一个方法，输入一个字符串，返回该字符串中所有唯一字符的列表。例如，输入`"leetcode"`，输出`["l","t","c","d","e"]`。答案：javaimportjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;publicclassUniqueChars{publicstaticList<Character>findUniqueChars(Strings){HashMap<Character,Integer>map=newHashMap<>();for(charc:s.toCharArray()){map.put(c,map.getOrDefault(c,0)+1);}List<Character>uniqueList=newArrayList<>();for(charc:map.keySet()){if(map.get(c)==1){uniqueList.add(c);}}returnuniqueList;}publicstaticvoidmain(String[]args){Stringinput="leetcode";System.out.println(findUniqueChars(input));//Output:[l,t,c,d,e]}}解析：首先，使用`HashMap`统计每个字符的出现次数。遍历字符串时，将字符作为键，出现次数作为值存入哈希表。然后，再次遍历哈希表，将出现次数为1的字符加入结果列表。时间复杂度为O(n)，空间复杂度为O(n)。2.题目：用Python编写一个函数，接收一个列表，返回一个新列表，其中包含原列表中所有不重复的偶数，按升序排列。例如，输入`[1,2,4,6,6,8,10]`，输出`[2,4,6,8,10]`。答案：pythondeffilter_unique_evens(nums):unique_evens=set()fornuminnums:ifnum%2==0:unique_evens.add(num)returnsorted(unique_evens)Exampleusageinput_list=[1,2,4,6,6,8,10]print(filter_unique_evens(input_list))#Output:[2,4,6,8,10]解析：使用集合`set`自动去重，且集合中只有偶数。最后使用`sorted()`函数对结果进行排序。时间复杂度为O(nlogn)，空间复杂度为O(n)。3.题目：请用C++实现一个函数，接收一个整数数组，返回数组中的最大连续子数组的和。例如，输入`{-2,1,-3,4,-1,2,1,-5,4}`，输出`6`（对应子数组`[4,-1,2,1]`）。答案：cppinclude<vector>include<algorithm>intmaxSubArraySum(conststd::vector<int>&nums){intmax_sum=nums[0];intcurrent_sum=nums[0];for(inti=1;i<nums.size();++i){current_sum=std::max(nums[i],current_sum+nums[i]);max_sum=std::max(max_sum,current_sum);}returnmax_sum;}//Exampleusageinclude<iostream>intmain(){std::vector<int>nums={-2,1,-3,4,-1,2,1,-5,4};std::cout<<maxSubArraySum(nums)<<std::endl;//Output:6return0;}解析：使用动态规划解法，`current_sum`记录当前子数组的最大和，`max_sum`记录全局最大和。每次遍历时，选择`nums[i]`或`current_sum+nums[i]`较大者作为新的`current_sum`，同时更新`max_sum`。时间复杂度为O(n)，空间复杂度为O(1)。二、数据结构与算法（5题，每题12分）1.题目：请解释快速排序（QuickSort）的基本思想，并给出其平均时间复杂度、最坏时间复杂度和空间复杂度。答案：快速排序的基本思想是：1.选择一个基准值（pivot），通常选择第一个或最后一个元素。2.将数组分为两部分，左边的元素都小于基准值，右边的元素都大于基准值（分区操作）。3.递归地对左右两部分进行排序，直到整个数组有序。时间复杂度：-平均：O(nlogn)-最坏：O(n²)（当基准值选择不均匀时，如已排序数组）空间复杂度：O(logn)（递归栈空间）。2.题目：用Java实现二叉搜索树（BST）的插入操作，并给出插入`[5,3,8,2,4,7,9]`后的树结构（前序遍历）。答案：javaclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicclassBST{publicTreeNodeinsert(TreeNoderoot,intval){if(root==null)returnnewTreeNode(val);if(val<root.val){root.left=insert(root.left,val);}elseif(val>root.val){root.right=insert(root.right,val);}returnroot;}publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>list=newArrayList<>();helper(root,list);returnlist;}privatevoidhelper(TreeNodenode,List<Integer>list){if(node==null)return;list.add(node.val);helper(node.left,list);helper(node.right,list);}publicstaticvoidmain(String[]args){BSTbst=newBST();TreeNoderoot=null;int[]values={5,3,8,2,4,7,9};for(intval:values){root=bst.insert(root,val);}System.out.println(bst.preorderTraversal(root));//Output:[5,3,2,4,8,7,9]}}解析：插入操作时，比较当前节点的值与待插入值的大小，递归地插入到左子树或右子树。前序遍历按`根-左-右`顺序输出。二叉搜索树的性质保证插入后仍满足有序性。3.题目：请解释堆（Heap）的基本性质，并说明如何用堆实现优先队列（PriorityQueue）。答案：堆的基本性质：-最大堆（MaxHeap）：父节点的值始终大于或等于子节点的值。-最小堆（MinHeap）：父节点的值始终小于或等于子节点的值。堆是完全二叉树，通常用数组实现，节点`i`的左子节点为`2i+1`，右子节点为`2i+2`，父节点为`(i-1)/2`。优先队列的实现：-插入时，将元素添加到数组末尾，然后通过上浮操作（Swim）调整堆。-删除时，返回堆顶元素，用数组末尾元素替换堆顶，然后通过下沉操作（Sink）调整堆。4.题目：用Python实现一个函数，判断一个字符串是否为回文（忽略大小写和空格）。例如，输入`"Aman,aplan,acanal:Panama"`，输出`True`。答案：pythondefisPalindrome(s:str)->bool:s=''.join(c.lower()forcinsifc.isalnum())returns==s[::-1]Exampleusageinput_str="Aman,aplan,acanal:Panama"print(isPalindrome(input_str))#Output:True解析：1.去除字符串中的非字母数字字符，并转换为小写。2.比较处理后的字符串与其反转字符串是否相同。时间复杂度为O(n)，空间复杂度为O(n)。5.题目：请解释图的邻接矩阵（AdjacencyMatrix）和邻接表（AdjacencyList）两种表示方法的优缺点。答案：-邻接矩阵：-优点：查找边是否存在的时间复杂度为O(1)，空间复杂度为O(V²)。-缺点：对于稀疏图，空间浪费严重。-邻接表：-优点：空间复杂度为O(V+E)，适用于稀疏图。-缺点：查找边是否存在的时间复杂度为O(E)。三、系统设计（2题，每题15分）1.题目：设计一个简单的短链接（TinyURL）系统，要求：-输入一个长链接，返回一个短链接。-输入一个短链接，能解析回原始长链接。-假设短链接长度限制为6位，可用字符为`[a-z0-9]`。答案：pythonimportstringimportrandomclassTinyURL:def__init__(self):self.base=string.ascii_lowercase+string.digitsself.url_map={}self.id_map={}defencode(self,long_url:str)->str:random_id=''.join(random.choices(self.base,k=6))whilerandom_idinself.id_map:random_id=''.join(random.choices(self.base,k=6))self.url_map[random_id]=long_urlself.id_map[long_url]=random_idreturnf"/{random_id}"defdecode(self,short_url:str)->str:id_part=short_url.split('/')[-1]returnself.url_map.get(id_part,"")Exampleusagetiny=TinyURL()long_url=""short_url=tiny.encode(long_url)print(short_url)#Output:/xyzabcprint(tiny.decode(short_url))#Output:解析：1.使用随机生成6位短码（如`xyzabc`）作为映射键。2.`url_map`存储短码到长链接的映射，`id_map`存储长链接到短码的映射（用于解析）。3.为避免冲突，生成短码时需检查是否已存在。2.题目：设计一个简单的消息队列（MessageQueue），要求支持：-生产者（Producer）向队列中发送消息。-消费者（Consumer）从队列中接收消息。-队列长度限制为100，满时阻塞生产者。答案：pythonimportthreadingimportcollectionsclassMessageQueue:def__init__(self,capacity=100):self.queue=collections.deque(maxlen=capacity)self.lock=threading.Lock()self.not_empty=threading.Condition(self.lock)self.not_full=threading.Condition(self.lock)defproduce(self,message:str):withself.not_full:whilelen(self.queue)==self.queue.maxlen:self.not_full.wait()self.queue.append(message)self.not_empty.notify()defconsume(self)->str:withself.not_empty:whilenotself.queue:self.not_empty.wait()message=self.queue.popleft()self.not_full.notify()returnmessageExampleusagedefproducer(q):foriinrange(120):duce(f"message{i}")defconsumer(q):for_inrange(120):print(q.consume())q=MessageQueue()p=threading.Thread(target=producer,args=(q,))c=threading.Thread(target=consumer,args=(q,))p.start()c.start()p.join()解析：1.使用`collections.deque`实现队列，限制长度为100。2.通过`threading.Condition`实现生产者阻塞和消费者唤醒。3.生产者满队列时等待，消费者空队列时等待。四、数据库与SQL（2题，每题10分）1.题目：请写出SQL查询，统计每个用户的订单总数和总金额（假设表名为`orders`，字段有`user_id`,`order_id`,`amount`）。答案：sqlSELECTuser_id,COUNT(order_id)AStotal_orders,SUM(amount)AStotal_amountFROMordersGROUPBYuser_id;解析：使用`GROUPBY`按`user_id`分组，`COUNT()`统计订单数，`SUM()`计算总金额。2.题目：请写出SQL查询，找出所有订单金额大于平均金额的用户及其订单金额。答案：sqlSELECTuser_id,amountFROMordersWHEREamount>(SELECTAVG(amount)FROMorders);解析：使用子查询计算平均金额，然后选择金额大于平均值的用户和金额。五、网络与系统（2题，每题12分）1.题目：请解释TCP的三次握手（Three-wayHandshake）过程及其作用。答案：三次握手过程：1.客户端发送SYN包（s