2026年IT巨头面试技巧软件开发人员笔试面试全攻略

2026年IT巨头面试技巧：软件开发人员笔试面试全攻略编程能力测试（15题，共75分）1.数组与字符串操作（3题，每题25分）题目1（25分）：给定一个字符串`s`和一个整数`k`，将字符串`s`中所有长度为`k`的子串反转，其余字符保持不变。请实现该功能，并分析时间复杂度。示例输入：`s="abcdefg",k=2`示例输出：`"badcfeg"`要求：-不能使用额外的字符串或数组存储空间-考虑`k`等于1和`s`为空的情况题目2（25分）：实现一个函数，找出数组中最长的连续递增子数组，并返回其长度。如果存在多个最长连续递增子数组，返回任意一个的长度。示例输入：`arr=[1,3,5,4,7,9,2,6,8]`示例输出：`5`（对应子数组[4,7,9,2,6]）要求：-不能使用递归-考虑数组为空或所有元素相同的情况题目3（25分）：实现一个函数，判断一个字符串是否是有效的括号组合。字符串中可能包含`'()[]{}'`四种括号。示例输入：`"()[]{}"`示例输出：`true`要求：-时间复杂度不超过O(n)-可以使用栈实现2.数据结构与算法（6题，每题12分）题目4（12分）：实现一个LRU（最近最少使用）缓存，支持get和put操作。缓存容量为`capacity`，超出容量时需要删除最久未使用的元素。示例输入：`capacity=2``["LRUCache","put","put","get","put","get","get"]``[[],[1,1],[2,2],[1],[3,3],[2],[4]]`示例输出：`[null,null,null,1,null,-1,-1]`要求：-使用哈希表和双向链表实现-get和put操作的平均时间复杂度为O(1)题目5（12分）：给定一个整数数组，返回所有和为`target`的三个数的组合。结果中不能有重复的三元组。示例输入：`nums=[2,7,11,15],target=9`示例输出：`[[2,7,0]]`（假设索引从0开始）要求：-可以假设每个输入只对应一个解-不能使用重复的元素题目6（12分）：实现快速排序算法，并分析其平均时间复杂度和最坏情况时间复杂度。示例输入：`arr=[3,6,8,10,1,2,1]`示例输出：`[1,1,2,3,6,8,10]`要求：-不能使用递归-分析时间复杂度变化条件题目7（12分）：设计一个算法，找出二叉树中的最大路径和。路径可以从任意节点开始，到任意节点结束，但必须至少包含一个节点。示例输入：1/\23示例输出：`6`（路径1-2-3）要求：-可以使用递归-考虑负数节点的情况题目8（12分）：实现一个函数，判断一个链表是否有环。如果有环，返回进入环的第一个节点；如果没有环，返回null。示例输入：3->2->0->-4^|||示例输出：`节点2`要求：-可以使用快慢指针-不能使用额外的存储空间题目9（12分）：实现二分查找算法，并说明其适用条件。示例输入：`arr=[1,2,3,4,5,6,7,8,9],target=4`示例输出：`3`（索引从0开始）要求：-处理target不存在的情况-分析时间复杂度题目10（12分）：实现一个函数，将32位无符号整数反转。如果反转后数值超出32位整数的范围，返回0。示例输入：`x=123456789`示例输出：`987654321`要求：-考虑整数溢出情况-时间复杂度为O(log(x))题目11（12分）：实现一个函数，检查一个字符串是否是回文串。可以忽略非字母数字字符和大小写。示例输入：`"Aman,aplan,acanal:Panama"`示例输出：`true`要求：-可以使用双指针方法-考虑空字符串情况题目12（12分）：给定一个链表，将其反转，并返回反转后的链表头节点。示例输入：`1->2->3->4->5`示例输出：`5->4->3->2->1`要求：-不能使用递归-分析时间复杂度3.系统设计（3题，每题25分）题目13（25分）：设计一个简单的URL短链接系统。需要支持：1.将长URL转换为短URL2.将短URL解析为原始长URL3.每个长URL对应唯一短URL要求：-说明核心数据结构-描述算法流程-分析性能瓶颈题目14（25分）：设计一个简单的消息队列系统。需要支持：1.生产者发送消息2.消费者接收消息3.保证消息至少被消费一次要求：-说明核心组件-描述消息存储方式-分析高并发场景下的解决方案题目15（25分）：设计一个简单的用户登录系统。需要支持：1.用户注册（用户名唯一）2.用户登录（验证密码）3.密码加密存储要求：-说明核心数据结构-描述密码加密方式-分析安全漏洞及防护措施答案与解析编程能力测试答案题目1（25分）：pythondefreverse_substrings(s:str,k:int)->str:ifnotsork<=1:returnsarr=list(s)n=len(arr)foriinrange(0,n,k):ifi+k<=n:arr[i:i+k]=arr[i:i+k][::-1]return''.join(arr)解析：-时间复杂度：O(n)，每个字符被访问一次-空间复杂度：O(1)，仅使用常数额外空间-处理k=1时，无需反转-处理s为空时，直接返回空字符串-每次处理长度为k的子串，如果剩余长度小于k则不处理题目2（25分）：pythondeffind_longest_increasing_subarray(arr:List[int])->int:ifnotarr:return0max_len=1current_len=1foriinrange(1,len(arr)):ifarr[i]>arr[i-1]:current_len+=1max_len=max(max_len,current_len)else:current_len=1returnmax_len解析：-时间复杂度：O(n)，遍历数组一次-空间复杂度：O(1)，仅使用常数额外空间-初始化两个计数器，分别记录当前和最大长度-遍历时比较相邻元素，如果递增则增加当前长度，否则重置-处理数组为空或所有元素相同的情况题目3（25分）：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：-时间复杂度：O(n)，每个字符被访问一次-空间复杂度：O(n)，最坏情况下栈存储所有字符-使用栈存储左括号，遇到右括号时匹配栈顶-初始化一个特殊字符作为哨兵，避免空栈时出错-最后检查栈是否为空题目4（12分）：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:self.cache[key]=valueself.cache.move_to_end(key)iflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：-使用OrderedDict实现LRU，保持插入顺序-get操作将访问的键移动到末尾-put操作同样将键移动到末尾，如果超出容量则删除第一个元素-时间复杂度：O(1)-空间复杂度：O(capacity)题目5（12分）：pythondefthreeSum(nums:List[int],target:int)->List[List[int]]:nums.sort()n=len(nums)result=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target: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<target:left+=1else:right-=1returnresult解析：-首先排序，便于跳过重复元素-使用固定指针+双指针方法-每次固定一个数，然后使用双指针找另外两个数-跳过重复元素避免重复三元组-时间复杂度：O(n²)-空间复杂度：O(1)（如果忽略输出空间）题目6（12分）：pythondefquick_sort(arr:List[int])->List[int]:def_quick_sort(nums,low,high):iflow<high:pivot=_partition(nums,low,high)_quick_sort(nums,low,pivot-1)_quick_sort(nums,pivot+1,high)def_partition(nums,low,high):pivot=nums[high]i=low-1forjinrange(low,high):ifnums[j]<=pivot:i+=1nums[i],nums[j]=nums[j],nums[i]nums[i+1],nums[high]=nums[high],nums[i+1]returni+1_quick_sort(arr,0,len(arr)-1)returnarr解析：-平均时间复杂度：O(nlogn)-最坏情况时间复杂度：O(n²)（当每次选择的枢轴都是最小或最大元素时）-使用递归实现，但题目要求非递归版本-非递归实现可以使用栈模拟递归调用栈-空间复杂度：O(logn)（递归栈）题目7（12分）：pythondefmaxPathSum(root:TreeNode)->int:def_maxPathSum(node):ifnotnode:returnfloat('-inf')left=max(_maxPathSum(node.left),0)right=max(_maxPathSum(node.right),0)current_max=node.val+left+rightnonlocalmax_summax_sum=max(max_sum,current_max)returnnode.val+max(left,right)max_sum=float('-inf')_maxPathSum(root)returnmax_sum解析：-使用后序遍历（左右中）-每个节点计算以该节点为根的最大路径和-更新全局最大值-返回值表示以该节点为根的子树最大路径和（可以延伸到一侧）-时间复杂度：O(n)-空间复杂度：O(h)（递归栈）题目8（12分）：pythondefdetectCycle(head:ListNode)->ListNode:slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:找到交点后，移动slow到头节点slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：-使用快慢指针法-快指针每次走两步，慢指针每次走一步-如果有环，快慢指针最终会相遇-相遇后，将慢指针移到头节点，再次以相同速度移动，相遇点即为入口-时间复杂度：O(n)-空间复杂度：O(1)题目9（12分）：pythondefbinary_search(arr:List[int],target:int)->int:left,right=0,len(arr)-1whileleft<=right:mid=left+(right-left)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid-1return-1解析：-适用于已排序数组-每次将搜索范围减半-时间复杂度：O(logn)-空间复杂度：O(1)-适用条件：数组必须有序-处理target不存在的情况返回-1题目10（12分）：pythondefreverse(x:int)->int:INT_MAX=231-1INT_MIN=-231rev=0whilex!=0:pop=x%10x//=10ifrev>INT_MAX//10or(rev==INT_MAX//10andpop>7):return0ifrev<INT_MIN//10or(rev==INT_MIN//10andpop<-8):return0rev=rev10+popreturnrev解析：-逐位反转数字-每次处理最后一位，然后更新剩余数字-检查反转后是否溢出-时间复杂度：O(logx)-空间复杂度：O(1)题目11（12分）：pythondefisPalindrome(s:str)->bool:left,right=0,len(s)-1whileleft<right:whileleft<rightandnots[left].isalnum():left+=1whileleft<rightandnots[right].isalnum():right-=1ifs[left].lower()!=s[right].lower():returnFalseleft,right=left+1,right-1returnTrue解析：-使用双指针法-跳过非字母数字字符-比较对应字符是否相等（忽略大小写）-时间复杂度：O(n)-空间复杂度：O(1)题目12（12分）：pythondefreverseList(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurr