字节跳动2026届秋季招聘面试备考手册与题库

字节跳动2026届秋季招聘面试备考手册与题库一、编程能力测试（共5题，每题10分，总分50分）1.题目：编写一个函数，实现判断一个字符串是否为“回文串”。回文串是指正序和倒序读都一样的字符串，例如“madam”或“racecar”。要求不使用额外的存储空间，时间复杂度尽可能低。答案：pythondefis_palindrome(s:str)->bool:left,right=0,len(s)-1whileleft<right:ifs[left].lower()!=s[right].lower():returnFalseleft+=1right-=1returnTrue解析：通过双指针法，从字符串两端向中间遍历，比较字符是否相同。忽略大小写，提高容错性。时间复杂度为O(n)，空间复杂度为O(1)。2.题目：给定一个链表，实现删除链表中的所有重复元素，保留一个重复元素。例如，链表为1->2->3->3->4->4->5，删除后为1->2->3->4->5。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefdelete_duplicates(head:ListNode)->ListNode:dummy=ListNode(0,head)prev,curr=dummy,headwhilecurr:ifcurr.nextandcurr.val==curr.next.val:whilecurr.nextandcurr.val==curr.next.val:curr=curr.nextprev.next=curr.nextelse:prev=prev.nextcurr=curr.nextreturndummy.next解析：使用虚拟头节点简化边界处理。通过快慢指针法，当发现重复时，跳过所有重复节点。时间复杂度为O(n)，空间复杂度为O(1)。3.题目：实现一个LRU（最近最少使用）缓存，支持get和put操作。LRU缓存最多容纳固定数量的元素，当缓存满时，删除最久未使用的元素。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=ListNode(0,0),ListNode(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=ListNode(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.head.nextself._remove(lru)delself.cache[lru.key]def_remove(self,node:ListNode)->None:delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node:ListNode)->None:node.next=self.tail.prevnode.next.prev=nodeself.tail.prev=nodenode.prev=self.tail.prev.prev解析：使用双向链表+哈希表实现。链表维护访问顺序，哈希表实现O(1)访问。get时将节点移到尾部，put时先删除旧节点，再添加新节点，若超出容量则删除头部节点。4.题目：给定一个非空数组，返回所有可能的全排列。例如，输入[1,2,3]，返回[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。答案：pythondefpermute(nums:List[int])->List[List[int]]:defbacktrack(path,used,res):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifnotused[i]:used[i]=Truepath.append(nums[i])backtrack(path,used,res)path.pop()used[i]=Falseres=[]used=[False]len(nums)backtrack([],used,res)returnres解析：回溯算法实现全排列。使用used数组记录元素是否被使用，避免重复。时间复杂度为O(n!)，空间复杂度为O(n)。5.题目：实现一个二叉树的最大深度（最大高度）计算。例如，给定二叉树[3,9,20,null,null,15,7]，最大深度为3。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_depth(root:TreeNode)->int:ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))解析：递归计算左右子树的最大深度，取较大值加1。时间复杂度为O(n)，空间复杂度为O(h)（h为树的高度）。二、算法设计题（共4题，每题15分，总分60分）1.题目：设计一个算法，实现LRU缓存的高效实现。要求支持get和put操作，且时间复杂度为O(1)。答案：参考第一题的LRUCache实现。使用双向链表维护访问顺序，哈希表实现O(1)访问。get时将节点移到尾部，put时先删除旧节点，再添加新节点，若超出容量则删除头部节点。解析：LRU缓存的核心在于高效更新访问顺序。双向链表提供O(1)的删除和插入操作，哈希表提供O(1)的节点查找。整体时间复杂度为O(1)，空间复杂度为O(capacity)。2.题目：设计一个算法，实现字符串的URL化。例如，输入"LeetCode%20is%20cool"，转换为"/LeetCode%20is%20cool"。答案：pythondefurlify(s:str,length:int)->str:returns[:length].replace("%20","")解析：直接截取前length个字符，将"%20"替换为""。时间复杂度为O(n)，空间复杂度为O(n)。3.题目：设计一个算法，实现二叉树的层序遍历（广度优先遍历）。例如，给定二叉树[3,9,20,null,null,15,7]，输出[[3],[9,20],[15,7]]。答案：pythondeflevel_order(root:TreeNode)->List[List[int]]:ifnotroot:return[]res,queue=[],[root]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres解析：使用队列实现层序遍历。每一层遍历所有节点，将子节点加入队列。时间复杂度为O(n)，空间复杂度为O(n)。4.题目：设计一个算法，实现判断一个无向图是否为二分图。二分图是指可以将节点分成两个集合，使得任意两个相邻节点不在同一集合。答案：pythondefis_bipartite(graph:List[List[int]])->bool:color={}defdfs(node,c):ifnodeincolor:returncolor[node]==ccolor[node]=creturnall(dfs(nei,notc)forneiingraph[node])fornodeinrange(len(graph)):ifnodenotincolor:ifnotdfs(node,True):returnFalsereturnTrue解析：使用深度优先搜索（DFS）进行二分图判断。使用color字典记录节点颜色，初始设为True或False。若存在相邻节点颜色相同，则不是二分图。时间复杂度为O(n+e)，空间复杂度为O(n)。三、系统设计题（共3题，每题20分，总分60分）1.题目：设计一个短链接（TinyURL）系统。输入一个长URL，生成一个短URL，并支持通过短URL解析回长URL。答案：pythonclassTinyURL:def__init__(self):self.base_url="/"self.url_map={}self.count=0def_encode(self,num:int)->str:chars="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"res=[]whilenum:res.append(chars[num%62])num//=62return''.join(res[::-1])definsert(self,long_url:str)->str:self.count+=1short_code=self._encode(self.count)self.url_map[short_code]=long_urlreturnself.base_url+short_codedefget(self,short_url:str)->str:short_code=short_url.split('/')[-1]returnself.url_map.get(short_code,"")解析：使用62进制编码生成短链接，避免冲突。哈希表存储短链接与长链接的映射关系。时间复杂度为O(1)，空间复杂度为O(n)。2.题目：设计一个微博（Twitter）系统，支持用户发布、关注、点赞和获取时间线。要求支持实时更新。答案：pythonclassTwitter:def__init__(self):self.timestamp=0self.user_follows=defaultdict(set)self.user_tweets=defaultdict(list)self.user_likes=defaultdict(set)defpost(self,user_id:int,tweet:str)->None:self.timestamp+=1self.user_tweets[user_id].append((self.timestamp,tweet))defget_timeline(self,user_id:int)->List[str]:tweets=self.user_tweets[user_id]return[tweetfor_,tweetinsorted(tweets,reverse=True)]deffollow(self,follower_id:int,followee_id:int)->None:self.user_follows[follower_id].add(followee_id)deflike(self,user_id:int,tweet_id:int)->None:self.user_likes[tweet_id].add(user_id)解析：使用哈希表存储用户关系和发