软件开发工程师面试题及编程问题含答案

2026年软件开发工程师面试题及编程问题含答案一、编程题（共5题，每题20分，总分100分）1.题目（20分）：实现一个函数，输入一个正整数`n`，返回一个包含所有小于或等于`n`的质数的列表。要求时间复杂度低于`O(n^2)`。示例：输入：`n=10`输出：`[2,3,5,7]`答案：pythondefsieve_of_eratosthenes(n):ifn<2:return[]is_prime=[True](n+1)is_prime[0]=is_prime[1]=Falseforiinrange(2,int(n0.5)+1):ifis_prime[i]:forjinrange(ii,n+1,i):is_prime[j]=Falsereturn[ifori,primeinenumerate(is_prime)ifprime]示例测试print(sieve_of_eratosthenes(10))#输出:[2,3,5,7]解析：使用埃拉托斯特尼筛法，时间复杂度为`O(nloglogn)`，优于`O(n^2)`。通过标记非质数来筛选出所有质数。2.题目（20分）：设计一个无锁（lock-free）队列，使用Python实现。假设系统支持原子操作（如`CAS`，可通过`threading.atomic`模拟）。要求：-支持队列的`push`和`pop`操作。-保证线程安全，避免数据竞争。答案：pythonimportthreadingclassLockFreeQueue:def__init__(self):self.head=threading.atomic(0)self.tail=threading.atomic(0)self.queue={}defpush(self,item):whileTrue:next_tail=self.tail.value+1ifself.queue.get(next_tail,None)isNone:ifpare_and_set(self.tail.value,next_tail):self.queue[next_tail]=itemreturndefpop(self):whileTrue:current_head=self.head.valueifself.queue.get(current_head,None)isnotNone:item=self.queue[current_head]ifpare_and_set(current_head,current_head+1):delself.queue[current_head]returnitemelse:returnNone示例测试queue=LockFreeQueue()queue.push(1)queue.push(2)print(queue.pop())#输出:1print(queue.pop())#输出:2解析：通过原子操作`compare_and_set`实现无锁队列，避免使用锁，提高并发性能。队列使用字典存储元素，`head`和`tail`分别表示头尾指针。3.题目（20分）：给定一个字符串`s`，包含数字和字母，返回其中最长的回文子串的长度。示例：输入：`s="abcbad"`输出：`3`（最长回文子串为"bcb"）答案：pythondeflongest_palindrome(s):ifnots:return0n=len(s)dp=[[False]nfor_inrange(n)]max_len=1foriinrange(n):dp[i][i]=Trueforiinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truemax_len=2forlengthinrange(3,n+1):foriinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truemax_len=lengthreturnmax_len示例测试print(longest_palindrome("abcbad"))#输出:3解析：使用动态规划解决，`dp[i][j]`表示`s[i..j]`是否为回文。逐步扩展子串长度，时间复杂度为`O(n^2)`。4.题目（20分）：实现一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。缓存容量为`capacity`。要求：-`get(key)`：返回键对应的值，若不存在返回-1。-`put(key,value)`：插入或更新键值对，若超出容量则删除最久未使用的键。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)示例测试cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#输出:1cache.put(3,3)#删除键1print(cache.get(2))#输出:2print(cache.get(1))#输出:-1print(cache.get(3))#输出:3解析：使用哈希表存储键值对，双向链表维护访问顺序。`get`操作将键移至队尾，`put`操作按需删除最久未使用键。5.题目（20分）：编写一个函数，输入一个链表的头节点`head`，返回其反转后的头节点。示例：输入：`1->2->3->None`输出：`3->2->1->None`答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev示例测试head=ListNode(1,ListNode(2,ListNode(3)))reversed_head=reverse_list(head)print(reversed_head.val)#输出:3print(reversed_head.next.val)#输出:2print(reversed_head.next.next.val)#输出:1解析：迭代反转链表，使用三个指针`prev`、`current`和`next_node`，逐步将节点反转。时间复杂度为`O(n)`。二、选择题（共10题，每题2分，总分20分）1.题目：以下哪种数据结构适合实现LRU缓存？A.哈希表B.队列C.堆D.双向链表答案：D解析：双向链表可以快速插入和删除节点，结合哈希表实现O(1)时间复杂度的LRU缓存。2.题目：快速排序的平均时间复杂度是？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)答案：B解析：快速排序采用分治法，平均时间复杂度为`O(nlogn)`。3.题目：以下哪个不是多线程的常见问题？A.竞态条件B.死锁C.活锁D.负载均衡答案：D解析：负载均衡是分布式系统问题，不属于多线程问题。4.题目：HTTP状态码`404`表示什么？A.请求成功B.未授权C.服务器错误D.未找到资源答案：D解析：`404NotFound`表示请求的资源不存在。5.题目：以下哪种加密方式属于非对称加密？A.AESB.RSAC.DESD.Blowfish答案：B解析：RSA使用公钥和私钥，属于非对称加密。6.题目：SQL中，`INNERJOIN`和`LEFTJOIN`的区别是什么？A.INNERJOIN返回匹配的行，LEFTJOIN返回左侧所有行B.INNERJOIN返回左侧所有行，LEFTJOIN返回匹配的行C.两者完全相同D.INNERJOIN不支持条件答案：A解析：`INNERJOIN`只返回匹配的行，`LEFTJOIN`返回左侧所有行及右侧匹配行（若无匹配则返回NULL）。7.题目：以下哪种算法适用于最短路径问题？A.DijkstraB.快速排序C.堆排序D.冒泡排序答案：A解析：Dijkstra算法用于求解单源最短路径问题。8.题目：Git中，`gitpull`和`gitfetch`的区别是什么？A.`pull`合并远程分支，`fetch`仅获取远程分支B.`fetch`合并远程分支，`pull`仅获取远程分支C.两者完全相同D.`pull`删除本地分支答案：A解析：`gitpull`=`gitfetch`+`gitmerge`，`gitfetch`仅获取远程数据。9.题目：以下哪种设计模式属于创建型模式？A.观察者模式B.工厂模式C.策略模式D.装饰器模式答案：B解析：工厂模式用于创建对象，属于创建型模式。10.题目：Redis的默认持久化方式是？A.RDBB.AOFC.两者都不是D.永久不持久化答案：C解析：Redis默认不开启持久化，可通过配置启用RDB或AOF。三、简答题（共5题，每题4分，总分20分）1.题目：简述线程和进程的区别。答案：-进程是资源分配的基本单位，拥有独立的内存空间；线程是执行的基本单位，共享进程内存。-进程间通信复杂，线程间通信简单。-进程切换开销大，线程切换开销小。2.题目：解释RESTfulAPI的核心原则。答案：-无状态：服务器不存储客户端状态。-统一接口：使用标准HTTP方法（GET/POST/PUT/DELETE）。-资源导向：以资源为中心设计URI。-可缓存：响应可被缓存。3.题目：什么是数据库索引？为什么使用它？答案：索引是帮助快速查找数据的结构（如B-Tree）。使用它可以：-提高查询效率（避免全表扫描）。-加速排序和分组操作。4.题目：简述JWT的工作原理。答案：JWT（JSONWebToken）包含三部分（Header、Payload、Signature）：-Header：算法和类型。-Payload：用户信息和自定义字段。-Signature：签名验证完整性。通过Base64编码传输，无需服务器存储。5.题目：什么是微服务架构？答案：微服务是一种架构风格，将应用拆分为小型、独立服务，通过轻量级通信（如HTTP）协作。优点：-独立部署和扩展。-技术异构性。四、编程题（含代码和解析）1.题目（10分）：实现一个函数，输入一个列表`nums`，返回其中最大回文子序列的长度。示例：输入：`nums=[1,2,3,2,1]`输出：`5`（整个列表是回文）答案：pythondeflongest_palindromic_subseq(nums):n=len(nums)dp=[[0]nfor_inrange(n)]foriinrange(n-1,-1,-1):dp[i][i]=1forjinrange(i+1,n):ifnums[i]==nums[