2026年互联网公司技术面试题详解

2026年互联网公司技术面试题详解一、编程实现题（共3题，每题15分，总分45分）题目1：字符串反转（15分）题目描述：实现一个函数，将输入的字符串反转。例如，输入`"abcdef"`，输出`"fedcba"`。要求不使用额外的字符串变量，原地修改字符串。答案与解析：pythondefreverse_string(s:str)->str:s=list(s)#将字符串转换为列表（Python中字符串不可变）left,right=0,len(s)-1whileleft<right:s[left],s[right]=s[right],s[left]#交换首尾字符left+=1right-=1return''.join(s)#将列表转换回字符串解析：1.字符串不可变：Python中字符串是immutable的，不能直接修改。因此需要先转换为列表。2.双指针法：使用左右指针分别指向字符串的首尾，逐步交换字符，直到指针相遇。3.时间复杂度：O(n)，需要遍历整个字符串一次。4.空间复杂度：O(1)，仅使用常数个额外空间。题目2：最长回文子串（15分）题目描述：给定一个字符串，找出其中最长的回文子串。例如，输入`"babad"`，输出`"bab"`或`"aba"`。答案与解析：pythondeflongest_palindrome(s:str)->str:ifnots:return''start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)#奇数长度回文len2=expand_from_center(s,i,i+1)#偶数长度回文max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpand_from_center(s:str,left:int,right:int)->int:whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：1.中心扩展法：对于每个字符，分别以它自身和它与其后一个字符为中心，扩展回文子串。2.时间复杂度：O(n²)，每个字符都可能扩展n次。3.空间复杂度：O(1)，仅使用常数个额外空间。4.优化：可以预处理字符串，添加分隔符避免奇偶长度判断的重复逻辑。题目3：合并区间（15分）题目描述：给定一个区间的集合，合并所有重叠的区间。例如，输入`[[1,3],[2,6],[8,10]]`，输出`[[1,6],[8,10]]`。答案与解析：pythondefmerge_intervals(intervals:list[list[int]])->list[list[int]]:ifnotintervals:return[]按区间的起始位置排序intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:#重叠last[1]=max(last[1],current[1])else:merged.append(current)returnmerged解析：1.排序：按区间的起始位置升序排序，便于合并。2.合并逻辑：遍历排序后的区间，若当前区间与前一个区间重叠（即当前区间的起始≤前一个区间的终止），则合并；否则，直接添加到结果中。3.时间复杂度：O(nlogn)，主要由排序决定。4.空间复杂度：O(n)，可能需要存储所有合并后的区间。二、算法与数据结构题（共4题，每题10分，总分40分）题目4：二叉树的最大深度（10分）题目描述：给定一个二叉树，返回其最大深度。例如，输入`[3,9,20,null,null,15,7]`，输出`3`。答案与解析：python定义二叉树节点classTreeNode: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.递归法：最大深度等于左子树和右子树深度的最大值加1。2.时间复杂度：O(n)，遍历所有节点。3.空间复杂度：O(h)，递归栈的深度等于二叉树的高度。题目5：有效的括号（10分）题目描述：给定一个字符串，判断其中括号`()`、`[]`、`{}`是否有效匹配。例如，输入`"()[]{}"`，输出`True`；输入`"([)]"`，输出`False`。答案与解析：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：1.栈的应用：遇到左括号入栈，遇到右括号时与栈顶比较，匹配则出栈，否则无效。2.时间复杂度：O(n)，遍历字符串一次。3.空间复杂度：O(n)，栈可能存储所有字符。题目6：LRU缓存机制（10分）题目描述：设计LRU（LeastRecentlyUsed）缓存机制，支持`get`和`put`操作。`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=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：1.双向链表+哈希表：哈希表存储键值对，双向链表维护访问顺序。2.get操作：若键存在，将其移动到链表末尾（表示最近使用）。3.put操作：若键已存在，更新值并移动到末尾；若不存在且缓存已满，删除链表头部（最久未使用）的键，插入新键到末尾。3.时间复杂度：O(1)。题目7：N皇后问题（10分）题目描述：给定一个棋盘大小`n`，输出所有有效的N皇后摆法。例如，`n=4`，输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]答案与解析：pythondefsolveNQueens(n:int)->list[list[str]]:defis_safe(row,col,diagonals,anti_diagonals,cols):returnnot(cols[col]ordiagonals[row-col]oranti_diagonals[row+col])defplace_queens(row,state):ifrow==n:board=[''.join(row)forrowinstate]result.append(board)returnforcolinrange(n):ifis_safe(row,col,diagonals,anti_diagonals,cols):cols[col]=Truediagonals[row-col]=Trueanti_diagonals[row+col]=Truestate[row][col]='Q'place_queens(row+1,state)state[row][col]='.'cols[col]=Falsediagonals[row-col]=Falseanti_diagonals[row+col]=Falseresult=[]state=[['.'for_inrange(n)]for_inrange(n)]cols=[False]ndiagonals=[False](2n-1)anti_diagonals=[False](2n-1)place_queens(0,state)returnresult解析：1.回溯法：逐行放置皇后，确保每行、每列、每对角线无冲突。2.冲突检测：使用三个数组分别记录列、主对角线（`row-col`）、副对角线（`row+col`）是否已有皇后。3.时间复杂度：O(n!)，最坏情况下需要尝试所有可能的摆法。4.空间复杂度：O(n²)，用于存储棋盘状态。三、系统设计题（共2题，每题25分，总分50分）题目8：设计微博系统（25分）题目描述：设计一个微博系统，支持以下功能：1.用户注册/登录；2.发布/获取微博；3.关注/取关用户；4.获取某用户的动态（包含关注用户的微博）。答案与解析：1.数据模型：-`User`：`id`,`username`,`password`,`followees`（关注列表）,`followers`（粉丝列表）-`Tweet`：`id`,`user_id`,`content`,`timestamp`,`likes`（点赞数）-`Follow`：`follower_id`,`followee_id`（多对多关系）2.核心接口：-发布微博：插入`Tweet`记录，更新用户`latest_tweet_id`。-获取微博：分页查询`Tweet`，按`timestamp`降序排列。-关注/取关：更新`Follow`表，`User`的`followees`和`followers`。-获取动态：先获取用户自己的`Tweet`，再获取关注用户的`Tweet`，合并并按`timestamp`排序。3.技术选型：-数据库：PostgreSQL（支持ACID，适合关系型数据）。-缓存：Redis（存储热点用户动态、点赞数）。-消息队列：Kafka（异步处理点赞、关注等事件）。4.性能优化：-索引：`Tweet`的`user_id`和`timestamp`，`Follow`的`follower_id`和`followee_id`。-分页：使用游标或`limit`+`offset`获取动态。题目9：设计短链接系统（25分）题目描述：设计一个短链接系统，实现以下功能：1.将长链接转换为短链接；2.通过短链接跳转到原始长链接；3.支持统计短链接的访问次数。答案与解析：1.数据模型：-`ShortLink`：`id`,`long_url`,`short_code`,`created_at`,`hit_count`2.核心算法：-生成短码：使用哈希算法（如SHA256）或自定义62进制编码（a-z、A-Z、0-9）。-映射关系：将短码存储在哈希表（内存或Redis）中，关联长链接。3.实现步骤：-生成短链接：1.对