2026年互联网大厂校招编程题库

2026年互联网大厂校招编程题库1.数值计算题（共3题，每题10分）背景：针对北京、上海、深圳等一线互联网城市，考察算法工程师的基础数值处理能力。1.1题目：给定一个非负整数数组`nums`，返回其中和为`target`的两个数的组合的个数。假设每个数字只能使用一次。示例：输入：`nums=[1,2,3,4,5]`,`target=5`输出：`2`（组合为(1,4)和(2,3)）解析：-双指针法：排序后，左右指针向中间移动，时间复杂度O(nlogn)。-哈希表法：遍历时记录`target-num`，时间复杂度O(n)。1.2题目：实现一个函数`power(x,n)`，计算`x`的`n`次幂。要求不使用库函数，且当`n<0`时返回`1/power(x,-n)`。示例：输入：`x=2.00000`,`n=10`输出：`1024.00000`解析：-快速幂算法：分治思想，将`n`拆分为二进制位，时间复杂度O(logn)。-注意边界处理：`x=0`,`n=0`等。1.3题目：设计一个`Solution`类，支持`add`和`find`两个操作：-`add(key)`：将`key`添加到集合中。-`find(key)`：返回`key`是否存在于集合中。要求`add`和`find`的平均时间复杂度均为O(1)。示例：pythonsol=Solution()sol.add(1)print(sol.find(1))#Trueprint(sol.find(2))#False解析：-使用哈希集合（如Python的`set`），确保O(1)复杂度。-考察对数据结构的掌握。2.字符串处理题（共4题，每题10分）背景：针对杭州、成都等新一线城市的算法岗位，考察字符串操作能力。2.1题目：给定一个字符串`s`，找到其中不重复的最长子串的长度。示例：输入：`s="abcabcbb"`输出：`3`（最长子串为"abc"）解析：-滑动窗口法：左右指针维护子串，哈希表记录字符上一次出现的位置。-时间复杂度O(n)，空间复杂度O(128)。2.2题目：实现一个函数`reverseWords(s)`，将字符串`s`中的单词顺序反转，但单词内部字符顺序不变。示例：输入：`s="theskyisblue"`输出：`"blueisskythe"`解析：-分步反转：整体反转+单词反转。-注意空格和标点处理。2.3题目：判断一个字符串是否是有效的括号组合（只包含`()[]{}`）。示例：输入：`s="{[]()}"`输出：`True`解析：-栈结构：左括号入栈，右括号匹配弹出。-时间复杂度O(n)，空间复杂度O(n)。2.4题目：实现一个函数`replaceSpace(s)`，将字符串中的空格`''`替换为`%20`。示例：输入：`s="Wearehappy."`输出：`"We%20are%20happy."`解析：-双指针法：从后向前替换，避免覆盖。-时间复杂度O(n)，空间复杂度O(n)。3.数据结构题（共5题，每题12分）背景：针对南京、武汉等二线城市算法岗位，考察链表、栈等基础数据结构。3.1题目：反转链表。示例：输入：`1->2->3->4->5`输出：`5->4->3->2->1`解析：-迭代法：遍历时改变指针方向。-递归法：递归到末尾再反转。3.2题目：判断链表是否存在环。示例：输入：`3->2->0->-4->3`（`3`指向`2`，存在环）输出：`True`解析：-快慢指针法（Floyd判环算法）。-时间复杂度O(n)，空间复杂度O(1)。3.3题目：实现一个`MyStack`类，使用两个队列实现栈的功能（`push`,`pop`,`top`）。示例：pythonstack=MyStack()stack.push(1)stack.push(2)print(stack.pop())#2print(stack.top())#1解析：-队列`q1`和`q2`交替使用：`push`时入`q1`，`pop`时将`q1`除最后一个外全部转`q2`，再取`q2`队首。3.4题目：实现一个`MinStack`类，支持`push`,`pop`,`top`,`getMin`操作。示例：pythonmin_stack=MinStack()min_stack.push(-2)min_stack.push(0)min_stack.push(-3)print(min_stack.getMin())#-3min_stack.pop()print(min_stack.getMin())#-2解析：-使用辅助栈记录最小值。-时间复杂度O(1)，空间复杂度O(n)。3.5题目：设计一个`LRUCache`类，实现最近最少使用缓存。示例：pythoncache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#1cache.put(3,3)#去除key=2print(cache.get(2))#-1解析：-双向链表+哈希表：链表维护访问顺序，哈希表O(1)查找。4.算法设计题（共3题，每题15分）背景：针对北京、上海等高线城市算法岗，考察复杂度较高的设计题。4.1题目：设计一个`WordDictionary`类，支持`addWord(word)`和`search(word)`：-`addWord(word)`：添加单词到字典。-`search(word)`：支持`.`通配符（如`"a.c"`匹配`"abc"`或`"arc"`）。示例：pythondict=WordDictionary()dict.addWord("bad")dict.addWord("dad")dict.addWord("mad")print(dict.search("pad"))#Falseprint(dict.search("bad"))#Trueprint(dict.search(".ad"))#Trueprint(dict.search("b.."))#True解析：-前缀树（Trie）：每个节点存储子节点和是否为单词结尾。-`search`时递归匹配通配符。4.2题目：实现一个`MedianFinder`类，支持`addNum(num)`和`findMedian()`操作：-`addNum(num)`：添加一个数字。-`findMedian()`：返回中位数。要求`addNum`和`findMedian`的平均时间复杂度均为O(logn)。示例：pythonmedian_finder=MedianFinder()median_finder.addNum(1)median_finder.addNum(2)print(median_finder.findMedian())#1.5median_finder.addNum(3)print(median_finder.findMedian())#2解析：-使用两个堆：小顶堆存储较大的一半，大顶堆存储较小的一半。-两个堆大小差不超过1。4.3题目：设计一个`LRUReplacement`类，支持`put(key,value)`和`get(key)`：-当容量满时，淘汰最久未使用（LRU）的元素。-`get`操作返回值，`put`操作插入或更新。示例：pythonlru=LRUReplacement(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#1lru.put(3,3)#去除key=2print(lru.get(2))#-1解析：-双向链表+哈希表：链表维护访问顺序，哈希表O(1)查找。-`get`时移动到链表末尾，`put`时若已存在则更新，否则删除最久未使用元素。答案与解析1.1答案：pythondeftwoSum(nums,target):seen={}fornuminnums:iftarget-numinseen:return2seen[num]=1return01.2答案：pythonclassSolution:defpower(self,x:float,n:int)->float:ifn==0:return1.0ifn<0:returnself.power(1/x,-n)res=1.0whilen:ifn&1:res=xx=xn>>=1returnres1.3答案：pythonclassSolution:def__init__(self):self.set=set()defadd(self,key:int)->None:self.set.add(key)deffind(self,key:int)->bool:returnkeyinself.set2.1答案：pythondeflengthOfLongestSubstring(s:str)->int:left,right=0,0max_len=0seen={}whileright<len(s):ifs[right]inseenandseen[s[right]]>=left:left=seen[s[right]]+1seen[s[right]]=rightmax_len=max(max_len,right-left+1)right+=1returnmax_len2.2答案：pythondefreverseWords(s:str)->str:s=s.strip()words=s.split()return''.join(reversed(words))2.3答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:ifnotstackorstack[-1]!=mapping[char]:returnFalsestack.pop()else:stack.append(char)returnnotstack2.4答案：pythondefreplaceSpace(s:str)->str:returns.replace('','%20')3.1答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head:ListNode)->ListNode:prev,curr=None,headwhilecurr:temp=curr.nextcurr.next=prevprev=currcurr=tempreturnprev3.2答案：pythondefhasCycle(head:ListNode)->bool:slow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse3.3答案：pythonfromcollectionsimportdequeclassMyStack:def__init__(self):self.q1=deque()self.q2=deque()defpush(self,x:int)->None:self.q1.append(x)defpop(self)->int:whilelen(self.q1)>1:self.q2.append(self.q1.popleft())top=self.q1.popleft()self.q1,self.q2=self.q2,self.q1returntopdeftop(self)->int:whilelen(self.q1)>1:self.q2.append(self.q1.popleft())top=self.q1[0]self.q1,self.q2=self.q2,self.q1returntop3.4答案：pythonclassMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,x:int)->None:self.stack.append(x)ifnotself.min_stackorx<=self.min_stack[-1]:self.min_stack.append(x)defpop(self)->int:x=self.stack.pop()ifx==self.min_stack[-1]:self.min_stack.pop()returnxdeftop(self)->int:returnself.stack[-1]defgetMin(self)->int:returnself.min_stack[-1]3.5答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=ListNode(0,0),ListNode(0,0)self.head.next,self.tail.prev=self.tail,self.headdef_add_node(self,node):node.prev,node.next=self.head,self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev,next=node.prev,node.nextprev.next,next.prev=next,prevdef_move_to_head(self,node):self._remove_node(node)self._add_node(node)defget(self,key:int)->int:ifkeyinself.cache:self._move_to_head(self.cache[key])returnself.cache[key].valreturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache[key].val=valueself._move_to_head(self.cache[key])else:node=ListNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]4.1答案：pythonclassTrieNode:def__init__(self):self.children={}self.is_end=FalseclassWordDictionary:def__init__(self):self.root=TrieNode()defaddWord(self,word:str)->None:node=self.rootforcharinword:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.is_end=Truedefsearch(self,word:str)->bool:defdfs(node,index):ifindex==len(word):returnnode.is_endchar=word[index]ifchar=='.':forchildinnode.children.values():ifdfs(child,index+1):returnTruereturnFalseelse:ifcharnotinnode.children:returnFalsereturndfs(node.children[char],index+1)returndfs(self.root,0)4.2答案：pythonimportheapqclassMedianFinder:def__init__(self):self.left=[]#maxheapself.right=[]#minheapdefaddNum(self,num:int)->None:ifnotself.leftornum<=-self.left[0]:heapq.heappush(self.left,-num)else:heapq.heappush(self.right,num)iflen(self.left)>len(self.right)+1:heapq.heappush(self.right,-heapq.heappop(self.left))eliflen(self.right)>len(self.left):heapq.heappush(self.left,-heapq.heappop(self.right))deffindMedian(self)->float:iflen(self.left)>len(self.right):return-self.left[0]return(-self.left[0]+self.right[0])/2.04.3答案：pythonclassLRUCache:def__init__(self,