2026年互联网公司程序员技术面试题库与算法解析

2026年互联网公司程序员技术面试题库与算法解析1.数据结构与算法（共5题，每题20分）1.1（20分）题目：给定一个非空字符串`s`，最多删除`k`个字符，使得剩余字符串为字典序最小。请返回删除后的字符串。示例：输入：`s="baab"`,`k=2`输出：`"ba"`解析要求：-使用贪心算法，从左到右遍历字符串，每次选择删除当前字符或前一个字符以保持字典序最小。-需要考虑边界情况，如`k`为0或`s`长度为1。1.2（20分）题目：设计一个`LRUCache`（最近最少使用缓存）类，支持以下操作：-`LRUCache(intcapacity)`：初始化缓存容量。-`intget(intkey)`：获取键`key`对应的值，如果不存在返回-1。-`voidput(intkey,intvalue)`：写入键值对，如果键已存在则更新值，如果超出容量则删除最久未使用的键。解析要求：-使用双向链表+哈希表实现，哈希表存储键到链表节点的映射，链表维护访问顺序。-`get`操作需移动节点到链表头部，`put`操作需处理容量超出情况。1.3（20分）题目：给定一个整数数组`nums`和一个整数`target`，返回所有和为`target`的不重复三元组。示例：输入：`nums=[-1,0,1,2]`,`target=0`输出：`[[-1,0,1]]`解析要求：-使用排序+双指针法，先排序数组，然后固定第一个数，用双指针在剩余部分查找补数。-需要跳过重复元素以避免重复解。1.4（20分）题目：给定一个字符串`s`，找到其中最长的回文子串。示例：输入：`s="babad"`输出：`"bab"`或`"aba"`解析要求：-动态规划法：定义`dp[i][j]`表示`s[i..j]`是否为回文，状态转移为`dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]`。-中心扩展法更高效，时间复杂度O(n²)。1.5（20分）题目：给定一个`n`叉树，返回其后序遍历的结果。示例：输入：1/\23/\45输出：`[4,5,2,3,1]`解析要求：-递归法：先遍历所有子节点，再访问根节点。-迭代法：使用栈模拟递归，需调整访问顺序。2.面向对象与设计模式（共4题，每题25分）2.1（25分）题目：实现一个`Singleton`单例模式，确保一个类只有一个实例，并提供全局访问点。解析要求：-双重校验锁（DCL）实现，解决多线程安全问题。-静态内部类实现，利用类加载机制保证线程安全。2.2（25分）题目：设计一个`Observer`观察者模式，实现事件监听与通知功能。示例：-`Subject`存储观察者，`notifyObservers()`通知所有观察者。解析要求：-使用列表或哈希表存储观察者，支持动态注册/注销。2.3（25分）题目：用工厂模式设计一个简单的咖啡店系统，支持`Coffee`（如`Latte`、`Espresso`）的创建。解析要求：-抽象产品`Coffee`，具体产品`Latte`、`Espresso`继承自它。-工厂类根据参数创建对应产品。2.4（25分）题目：解释装饰者模式，并设计一个`Component`（如`Window`）及其装饰类（如`BorderDecorator`、`ScrollbarDecorator`）。解析要求：-装饰类继承自`Component`或抽象装饰者，持有被装饰对象引用。-动态添加功能而不修改原始类。3.数据库与SQL（共3题，每题30分）3.1（30分）题目：给定以下表结构，写出SQL查询：sqlCREATETABLEOrders(OrderIDINT,CustomerIDINT,OrderDateDATE,TotalAmountDECIMAL);CREATETABLECustomers(CustomerIDINT,NameVARCHAR(50),CityVARCHAR(50));查询：返回每个城市的客户总数及其平均订单金额（订单金额为0的订单不计入）。解析要求：-使用`GROUPBY`和`HAVING`过滤条件，关联表时注意`LEFTJOIN`避免遗漏无订单客户。3.2（30分）题目：设计一个分页查询SQL，返回`Employees`表的前`5`页数据（每页`10`条）。解析要求：-使用`LIMIT`和`OFFSET`，但需考虑`OFFSET`可能导致性能问题（可优化为`WHERE`条件）。3.3（30分）题目：解释事务的ACID特性，并举例说明为何需要事务。解析要求：-ACID分别代表原子性、一致性、隔离性、持久性。-示例：银行转账需保证原子性，防止资金重复扣款。4.系统设计（共2题，每题35分）4.1（35分）题目：设计一个高并发的短链系统，要求：-输入长URL，返回短URL（如`/abc123`）。-支持分布式存储，高可用。解析要求：-使用哈希算法（如Base62编码）将长URL映射为短ID。-关联短链ID与长链的数据库设计，可使用Redis缓存热点数据。4.2（35分）题目：设计一个微博的实时消息推送系统，要求：-用户发布动态时，实时推送给关注者。-支持离线推送和消息去重。解析要求：-使用WebSocket或MQ（如Kafka）实现实时推送。-关系存储表设计，支持多对多关注关系。答案与解析1.数据结构与算法1.1：pythondefdeleteKchars(s:str,k:int)->str:stack=[]fori,cinenumerate(s):whilestackandk>0andstack[-1]>c:stack.pop()k-=1stack.append(c)return''.join(stack[:len(stack)-k])解析：贪心算法，用栈维护当前最小字典序，遇到比栈顶大的字符时删除前一个字符。1.2：pythonclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next,self.tail.prev=self.tail,self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:iflen(self.cache)==self.capacity:self._remove_tail()new_node=Node(key,value)self.cache[key]=new_nodeself._add_to_head(new_node)解析：双向链表+哈希表，链表头为最新使用，尾为最久未使用。1.3：pythondefthreeSum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n):ifi>0andnums[i]==nums[i-1]:continuej,k=i+1,n-1whilej<k:s=nums[i]+nums[j]+nums[k]ifs==target:res.append([nums[i],nums[j],nums[k]])j+=1k-=1whilej<kandnums[j]==nums[j-1]:j+=1whilej<kandnums[k]==nums[k+1]:k-=1elifs<target:j+=1else:k-=1returnres解析：排序后双指针，跳过重复元素避免重复解。1.4：pythondeflongestPalindrome(s:str)->str:ifnots:return""start,end=0,0foriinrange(len(s)):len1=self._expandAroundCenter(s,i,i)len2=self._expandAroundCenter(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]def_expandAroundCenter(self,s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：中心扩展法，枚举所有可能的中心，计算最大回文长度。1.5：pythondefpostorder(root):ifnotroot:return[]res=[]forchildinroot.children:res.extend(postorder(child))res.append(root.val)returnres解析：递归遍历所有子节点，最后访问根节点。2.面向对象与设计模式2.1：pythonimportthreadingclassSingleton:_instance=None_lock=threading.Lock()def__new__(cls,args,kwargs):withcls._lock:ifcls._instanceisNone:cls._instance=super().__new__(cls)returncls._instance解析：双重校验锁，先判断实例是否存在，再加锁创建。2.2：pythonclassSubject:def__init__(self):self.observers=[]defregister(self,observer):ifobservernotinself.observers:self.observers.append(observer)defunregister(self,observer):self.observers.remove(observer)defnotify(self):forobserverinself.observers:observer.update(self)解析：观察者模式，`Subject`管理观察者，`notify`触发更新。2.3：pythonfromabcimportABC,abstractmethodclassCoffee(ABC):@abstractmethoddefget_name(self):passclassLatte(Coffee):defget_name(self):return"Latte"classEspresso(Coffee):defget_name(self):return"Espresso"classCoffeeFactory:defcreate_coffee(type):iftype=="latte":returnLatte()eliftype=="espresso":returnEspresso()解析：工厂模式，根据类型创建不同产品。2.4：pythonclassComponent(ABC):@abstractmethoddefoperation(self):passclassWindow(Component):defoperation(self):return"Window"classDecorator(Component):def__init__(self,component):ponent=componentdefoperation(self):returnponent.operation()classBorderDecorator(Decorator):defoperation(self):returnf"Border({ponent.operation()})"解析：装饰者模式，动态添加功能而不修改原类。3.数据库与SQL3.1：sqlSELECTCity,COUNT(DISTINCTCustomerID)ASCustomerCount,AVG(TotalAmount)ASAvgAmountFROMCustomersCJOINOrdersOONC.CustomerID=