2026年软件开发招聘面试编程题

2026年软件开发招聘面试编程题一、算法与数据结构（共3题，每题15分，总分45分）1.题目：给定一个非空字符串`s`，其中仅包含小写字母，请找出并返回字符串的最长“回文子串”的长度。示例：输入：`"babad"`输出：`3`（最长回文子串为`"bab"`或`"aba"`）要求：-时间复杂度：O(n²)-空间复杂度：O(n)2.题目：设计一个无重复元素的`nums`数组，请在不使用额外数据结构的情况下，找出数组中第三大的数。如果数组中的不同元素少于三个，则返回最大的数。示例：输入：`[3,2,1,2]`输出：`1`（第三大为`1`）输入：`[1,2]`输出：`2`（不同元素少于三个，返回最大值`2`）要求：-不能使用排序-时间复杂度：O(n)3.题目：实现一个函数，将一个链表中的节点每`k`个一组翻转，返回翻转后的链表头节点。如果链表中的节点数不是`k`的倍数，则最后不足`k`个节点保持原样。示例：输入：`1->2->3->4->5`，`k=2`输出：`2->1->4->3->5`要求：-不能修改节点值-时间复杂度：O(n)二、动态规划（共2题，每题20分，总分40分）1.题目：给定一个由`'.'`和`'#'#`组成的二维网格，其中`'.'`表示空地，`'#`表示障碍物。机器人只能向下或向右移动，且不能穿过障碍物。请计算从左上角`(0,0)`到右下角`(m-1,n-1)`的不同路径数量。示例：输入：[[0,0,0],[0,1,0],[0,0,0]]输出：`2`（路径为右→右→下和右→下→右）要求：-使用动态规划解决-时间复杂度：O(mn)2.题目：给定一个正整数`n`，计算`1`到`n`中所有数字的数字和。例如：输入：`38`输出：`36`（1+2+3+4+5+6+7+8+9+1+0+2+3+4=36）要求：-不能直接转换成字符串计算-时间复杂度：O(n)三、数据库与SQL（共2题，每题20分，总分40分）1.题目：假设有一个`Orders`表，包含以下字段：-`order_id`（订单ID，主键）-`customer_id`（客户ID）-`order_date`（订单日期）-`total_amount`（订单总金额）请编写SQL查询，统计每个客户的订单总金额，并只显示订单总金额超过1000的客户信息（按总金额降序排列）。要求：-使用`GROUPBY`和`HAVING`-不使用子查询2.题目：假设有一个`Employees`表，包含以下字段：-`employee_id`（员工ID，主键）-`name`（姓名）-`department`（部门）-`salary`（薪水）请编写SQL查询，找出每个部门薪水最低的员工信息。要求：-使用窗口函数或自连接-不使用临时表四、系统设计（共1题，40分）1.题目：设计一个简单的短链接系统。用户可以输入一个长链接，系统返回一个短链接，点击短链接后自动跳转到原始的长链接。要求：-短链接长度应尽可能短（如`/abcd`）-需要考虑链接唯一性和高并发处理-描述主要数据结构和算法五、编程语言与基础（共2题，每题15分，总分30分）1.题目：用Python实现一个函数，检查一个字符串是否为有效的括号组合（只考虑`'()[]{}'`）。示例：输入：`"()"`输出：`True`输入：`"([)]"`输出：`False`要求：-使用栈实现-时间复杂度：O(n)2.题目：用Java实现一个简单的LRU（最近最少使用）缓存，支持`get`和`put`操作。要求：-使用双向链表和哈希表实现-`get`操作返回值存在则更新使用时间，否则返回-1-`put`操作插入新元素时若容量已满则删除最久未使用的元素答案与解析一、算法与数据结构1.最长回文子串思路：使用中心扩展法，对于每个字符（或两个字符的中间），向两边扩展，记录最大回文子串长度。代码（Python）：pythondeflongest_palindrome(s:str)->int:ifnots:return0n=len(s)max_len=1foriinrange(n):奇数长度回文left,right=i,iwhileleft>=0andright<nands[left]==s[right]:max_len=max(max_len,right-left+1)left-=1right+=1偶数长度回文left,right=i,i+1whileleft>=0andright<nands[left]==s[right]:max_len=max(max_len,right-left+1)left-=1right+=1returnmax_len解析：-中心扩展法的时间复杂度为O(n²)，因为对于每个字符都可能进行多次扩展。-空间复杂度为O(1)，因为只使用常数额外空间。2.第三大数思路：维护三个变量`first`、`second`、`third`，遍历数组时更新这三个变量。代码（Java）：javapublicintthirdMax(int[]nums){Longfirst=Long.MIN_VALUE,second=Long.MIN_VALUE,third=Long.MIN_VALUE;for(intnum:nums){if(num>first){third=second;second=first;first=num;}elseif(num>second&&num!=first){third=second;second=num;}elseif(num>third&&num!=second&&num!=first){third=num;}}returnthird==Long.MIN_VALUE?first:(int)third;}解析：-使用`Long.MIN_VALUE`避免整数溢出。-时间复杂度为O(n)，空间复杂度为O(1)。3.链表每k个翻转思路：使用哑节点简化边界处理，每次翻转k个节点，记录前驱和后继节点。代码（Python）：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_k_group(head:ListNode,k:int)->ListNode:dummy=ListNode(0)dummy.next=headprev_group_end=dummywhileTrue:kth=get_kth_node(prev_group_end,k)ifnotkth:breakgroup_start=prev_group_end.nextnext_group_start=kth.next翻转k个节点prev,curr=kth.next,group_startwhilecurr!=next_group_start:tmp=curr.nextcurr.next=prevprev=currcurr=tmp重连tmp=prev_group_end.nextprev_group_end.next=kthprev_group_end=tmpreturndummy.nextdefget_kth_node(start:ListNode,k:int)->ListNode:whilestartandk>0:start=start.nextk-=1returnstart解析：-时间复杂度为O(n)，因为每个节点最多被遍历两次。-空间复杂度为O(1)。二、动态规划1.不同路径数量思路：使用动态规划数组`dp[i][j]`表示到达`(i,j)`的路径数，状态转移方程为：`dp[i][j]=dp[i-1][j]+dp[i][j-1]`（若不越界）代码（SQL）：sqlSELECTSUM(CASEWHENobstacle(i,j)=0THENpath_count(i,j)ELSE0END)AStotal_pathsFROM(SELECTi,j,SUM(CASEWHENi=1ANDj=1THEN1ELSEpath_count(i-1,j)+path_count(i,j-1)END)ASpath_countFROM(SELECTDISTINCTi,jFROMgridORDERBYi,j)ASall_pointsGROUPBYi,j)ASdpWHEREi=mANDj=n;解析：-时间复杂度为O(mn)，空间复杂度为O(mn)。-可优化为滚动数组降低空间复杂度。2.数字和思路：对于每个数字，计算其各位数的和。代码（Java）：javapublicintsumOfDigits(intn){intsum=0;while(n>0){sum+=n%10;n/=10;}returnsum;}publicintdigitSum(intn){inttotal=0;for(inti=1;i<=n;i++){total+=sumOfDigits(i);}returntotal;}解析：-时间复杂度为O(n)，空间复杂度为O(1)。三、数据库与SQL1.订单总金额统计SQL：sqlSELECTcustomer_id,SUM(total_amount)AStotalFROMOrdersGROUPBYcustomer_idHAVINGSUM(total_amount)>1000ORDERBYtotalDESC;解析：-`GROUPBY`按客户分组，`HAVING`筛选总金额超过1000的客户。2.部门薪水最低员工SQL：sqlSELECTe1.employee_id,,e1.department,e1.salaryFROMEmployeese1WHERE(SELECTCOUNT(DISTINCTe2.salary)FROMEmployeese2WHEREe2.department=e1.departmentANDe2.salary>e1.salary)=0;解析：-子查询统计每个部门比当前员工薪水高的员工数量，若为0则当前员工为最低薪水。四、系统设计短链接系统设计1.数据结构：-使用哈希表`short_to_long`存储短链接到长链接的映射。-使用自增ID或随机生成短码（如62进制）。2.算法：-长链接经过哈希函数生成短码（如MD5截取前6位）。-点击短链接时，通过哈希表查找到原始长链接并返回。3.高并发处理：-使用Redis缓存热点短链接。-分布式部署时，短链接ID可使用分布式ID生成器。五、编程语言与基础1.有效括号检查Python：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：-使用栈匹配括号，时间复杂度O(n)。2.LRU缓存Java：javaclassLRUCache{privateMap<Integer,Integer>cache;privateDeque<Integer>deque;privateintcapacity;publicLRUCache(intcapacity){this.capacity=capacity;cache=newHashMap<>();deque=newLinkedList<>();}publicintget(intkey){if(cache.containsKey(key)){deque.remove(key);deque.offerLast(key);returncache.get(key);}return