开发级面试题及答案

2026年开发级面试题及答案一、编程基础与数据结构（共5题，总分30分）题目1（6分）请实现一个函数，找出数组中重复次数超过数组长度一半的元素。假设数组非空，且一定存在这样的元素。pythondeffind_majority_element(nums):你的代码题目2（8分）给定一个链表，判断链表中是否存在环。如果存在环，请返回进入环的第一个节点。pythonclassListNode:def__init__(self,x):self.val=xself.next=Nonedefdetect_cycle(head):你的代码题目3（10分）实现一个LRU（最近最少使用）缓存，支持get和put操作。缓存容量为固定值。pythonclassLRUCache:def__init__(self,capacity:int):你的代码defget(self,key:int)->int:你的代码defput(self,key:int,value:int)->None:你的代码题目4（5分）请解释什么是时间复杂度和空间复杂度，并分析以下代码的时间和空间复杂度。pythondefsum_of_n(n):total=0foriinrange(n):total+=ireturntotal题目5（1分）什么是哈希碰撞？如何解决哈希碰撞问题？二、算法与问题解决（共4题，总分25分）题目6（6分）给定一个字符串，找出其中不重复的字符的最长子串长度。例如："abcabcbb"的答案是3（"abc"）。pythondeflength_of_longest_substring(s:str)->int:你的代码题目7（7分）实现快速排序算法，并分析其平均时间复杂度。pythondefquick_sort(arr):你的代码题目8（8分）设计一个算法，找出无序数组中第k大的元素。不要求完全排序，时间复杂度尽可能低。pythondeffind_kth_largest(nums,k):你的代码题目9（4分）什么是动态规划？请举例说明动态规划的应用场景。三、系统设计与架构（共3题，总分25分）题目10（8分）设计一个简单的微博系统，需要支持用户发布微博、关注/取消关注、查看关注列表微博的功能。请说明主要的数据结构和API设计。题目11（8分）设计一个高并发的短链接系统，需要考虑URL生成、存储、查询的效率。请说明系统架构和关键技术点。题目12（9分）设计一个分布式缓存系统，需要支持数据分片、缓存更新、一致性保证。请说明系统架构和实现方案。四、数据库与存储（共2题，总分15分）题目13（7分）请解释ACID特性，并说明事务在分布式数据库中如何保证一致性。题目14（8分）设计一个数据库表结构，用于存储用户订单信息，需要支持按用户ID和订单时间查询，并说明索引设计。五、编程语言与工具（共3题，总分15分）题目15（5分）请解释Python中的装饰器是什么，并给出一个实际应用场景。题目16（5分）什么是Git中的rebase？与merge有什么区别？题目17（5分）请解释RESTfulAPI的设计原则，并说明如何实现状态码的重用。答案与解析题目1答案（6分）pythondeffind_majority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：Boyer-Moore多数投票算法。由于多数元素出现次数超过一半，遍历数组时可以正负抵消，最终留下的候选者就是多数元素。需要两遍遍历：第一遍找出候选者，第二遍验证候选者是否真的是多数元素。题目2答案（8分）pythondefdetect_cycle(head):ifnotheadornothead.next:returnNoneslow=headfast=head.nextwhilefast!=slow:ifnotfastornotfast.next:returnNoneslow=slow.nextfast=fast.next.next找到环的入口slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslow解析：使用快慢指针法。快指针每次移动两步，慢指针每次移动一步。当存在环时，快慢指针最终会相遇。相遇后，将慢指针移回头部，再次每次移动一步，与快指针再次相遇的节点就是环的入口。题目3答案（10分）pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode(0)self.tail=ListNode(0)self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):添加节点到头部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):移除节点prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):移动节点到头部self._remove_node(node)self._add_node(node)defget(self,key:int)->int:node=self.cache.get(key)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnode:node.value=valueself._move_to_head(node)else:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:移除尾部节点lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]解析：使用双向链表+哈希表实现。双向链表维护最近使用的顺序，哈希表实现O(1)时间复杂度的查找。get操作将节点移动到头部，put操作将新节点添加到头部，如果超出容量则移除尾部节点。题目4答案（5分）时间复杂度：衡量算法执行时间随输入规模增长的变化趋势。例如sum_of_n函数是O(n)时间复杂度，因为有一个循环遍历n次。空间复杂度：衡量算法所需内存空间随输入规模增长的变化趋势。sum_of_n函数是O(1)空间复杂度，因为只使用了常数个额外变量。sum_of_n函数分析：-初始化total：O(1)-循环n次：每次操作是O(1)，总共O(n)-总体：O(1)+O(n)=O(n)解析：时间复杂度通常用大O表示法，如O(1)、O(logn)、O(n)、O(nlogn)、O(n²)等。空间复杂度同理。分析时需要找出算法中的基本操作和递归关系。题目5答案（1分）哈希碰撞：不同的键通过哈希函数计算出相同的哈希值。解决方法：1.链地址法：在冲突位置使用链表存储所有冲突的键2.开放寻址法：使用探测序列查找下一个空闲位置3.再哈希法：使用另一个哈希函数4.哈希函数优化：选择更好的哈希函数减少冲突概率解析：哈希碰撞是不可避免的，关键在于如何有效处理。链地址法是最常用的方法，但可能导致链表过长影响性能。题目6答案（6分）pythondeflength_of_longest_substring(s:str)->int:char_set=set()max_len=0start=0forendinrange(len(s)):whiles[end]inchar_set:char_set.remove(s[start])start+=1char_set.add(s[end])max_len=max(max_len,end-start+1)returnmax_len解析：使用滑动窗口技术。维护一个窗口[left,right]，扩展right直到遇到重复字符，然后收缩left。记录最大窗口大小。题目7答案（7分）pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：快速排序的平均时间复杂度是O(nlogn)。基本思想是选择基准值，将数组分为小于、等于、大于三部分，然后递归排序左右两部分。题目8答案（8分）pythondeffind_kth_largest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,k-1)解析：基于快速选择算法。时间复杂度平均为O(n)，比完全排序更高效。通过随机选择基准值减少最坏情况概率。题目9答案（4分）动态规划：通过将问题分解为子问题并存储子问题解来优化递归算法。适用于具有重叠子问题和最优子结构特性的问题。应用场景：背包问题、斐波那契数列、最长公共子序列等。解析：动态规划的核心是状态定义和状态转移方程。与分治法的区别在于动态规划处理重叠子问题，分治法不重叠。题目10答案（8分）微博系统设计：1.数据结构：-用户表：user_id,username,...-微博表：id,user_id,content,timestamp,...-关注关系表：follower_id,following_id2.API设计：-POST/api/tweets：发布微博-GET/api/tweets/{user_id}：获取用户微博-POST/api/follow：关注用户-DELETE/api/follow：取消关注-GET/api/tweets/following：获取关注列表微博架构：采用微服务架构，微博服务负责核心功能，用户服务负责用户管理，通过RPC或RESTfulAPI通信。解析：关键是关注关系的管理和微博的实时获取。需要考虑数据库索引和缓存优化。题目11答案（8分）短链接系统设计：1.架构：-前端服务：接收URL请求，返回短链接-后端服务：生成短ID，存储原始URL-数据库：存储短ID和原始URL映射2.关键技术：-Base62编码：将长ID转换为短字符串-分布式ID生成器-缓存层：缓存热点短链接-负载均衡：分发请求URL生成：使用随机算法或顺序算法生成短ID，通过Base62编码转换为短字符串。解析：关键在于ID生成效率和查询性能。需要考虑ID的唯一性和碰撞概率。题目12答案（9分）分布式缓存系统设计：1.架构：-分片机制：将数据分散到不同节点-一致性协议：确保数据一致性-缓存失效策略：定期过期、主动失效2.实现方案：-使用Redis集群或Memcached-实现本地缓存+远程缓存两级缓存-使用一致性哈希算法进行分片一致性保证：通过版本号、向量时钟或Paxos/Raft协议保证分布式系统中的数据一致性。解析：需要考虑数据一致性和可用性。分布式缓存通常采用主从复制或一致性哈希方案。题目13答案（7分）ACID特性：1.原子性：事务要么全部完成，要么全部不做2.一致性：事务必须保证数据库从一致性状态转移到另一个一致性状态3.隔离性：并发执行的事务之间互不干扰4.持久性：一旦事务提交，其结果就永久保存在数据库中分布式事务：通过两阶段提交(2PC)或三阶段提交(3PC)协议保证一致性。使用分布式锁或时间戳解决冲突。解析：ACID是数据库事务的基本特性。分布式事务比集中式事务更复杂，需要考虑网络延迟和节点故障。题目14答案（8分）订单表设计：sqlCREATETABLEorders(order_idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,order_timeDATETIMENOTNULL,total_amountDECIMAL(10,2)NOTNULL,statusVARCHAR(20)NOTNULL,INDEXidx_user_time(user_id,order_time));索引设计：1.主键索引：order_id2.联合索引：user_id+order_time（按用户ID和订单时间排序）3.索引覆盖：如果经常需要直接获取订单信息，可以创建覆盖索引解析：索引设计需要根据查询频率来定。联合索引可以同时优化多条件查询。题目15答案（5分）装饰器：一种设计模式，在不修改原函数代码的情况下增加函