盛大技术岗笔试题及答案

盛大技术岗笔试题及答案考试时间：______分钟总分：______分姓名：______编程题（40分）1.实现一个函数，输入字符串s，输出反转后且去重（保留首次出现字符）的结果。示例：输入"hello"，输出"olleh"；输入"aabbcc"，输出"cbac"。2.给定一个整数数组nums和一个正整数k，求所有长度为k的滑动窗口中的最大和。示例：nums=[1,3,-1,-3,5,3,6,7],k=3，输出[3,3,5,5,6,7]。3.设计一个订单状态机类，订单有"待支付"、"已支付"、"已发货"、"已完成"、"已取消"5种状态。支持状态流转：待支付→已支付/已取消；已支付→已发货/已取消；已发货→已完成。要求实现状态流转方法，并校验非法流转。4.设计一个高并发计数器，支持多线程并发计数。要求计数器能正确处理并发增量，并返回当前计数值。算法与数据结构（30分）5.递归归并排序的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(2^n)6.关于哈希表和二叉搜索树，以下说法正确的是？A.哈希表支持有序遍历B.二叉搜索树查找平均时间复杂度为O(logn)C.哈希表冲突解决方式包括链地址法D.二叉搜索树插入操作最坏时间复杂度为O(n)7.给定一个非负整数数组nums和一个目标整数target，求从数组中选取若干个数（每个数可选多次），使得和等于target的组合数。设计动态规划的状态转移方程。8.实现Dijkstra算法，输入一个带权图（邻接矩阵表示）和起点，输出从起点到其他所有节点的最短路径长度。数据库与操作系统（20分）9.数据库B+树索引的适用场景包括？A.等值查询B.范围查询C.排序操作D.全表扫描10.简述数据库事务的4种隔离级别，并举例说明"幻读"在"读未提交"和"可重复读"级别下的表现。11.关于进程与线程的上下文切换开销，以下说法正确的是？A.线程切换开销比进程大B.进程切换需保存虚拟内存信息C.线程切换无需保存进程状态D.进程切换开销与线程相同12.解释内存管理中的分页机制，说明其如何实现虚拟内存。网络与系统设计（10分）13.TCP三次握手的主要作用是？A.提高传输效率B.确保双方收发能力正常C.防止重复连接D.减少网络延迟14.简述CAP定理的内容，并说明在订单系统中应优先保证CP还是AP，理由是什么？试卷答案编程题（40分）1.答案：```pythondefreverse_and_deduplicate(s:str)->str:seen=set()deduplicated=[]forcharins[::-1]:ifcharnotinseen:deduplicated.append(char)seen.add(char)return''.join(deduplicated)```解析思路：通过反向遍历字符串实现反转，同时使用集合记录已出现字符，确保每个字符仅保留首次出现（即原字符串末尾的字符优先）。2.答案：```pythondefsliding_window_max_sum(nums,k):current_sum=sum(nums[:k])max_sum=current_sumforiinrange(k,len(nums)):current_sum+=nums[i]-nums[i-k]max_sum=max(max_sum,current_sum)returnmax_sum```解析思路：使用滑动窗口技术，维护当前窗口和，每次移动窗口时减去最左元素并加上新元素，避免重复计算，时间复杂度O(n)。3.答案：```javaimportjava.util.HashMap;importjava.util.Map;publicclassOrderStateMachine{privateStringcurrentState;privatestaticfinalMap<String,String[]>TRANSITIONS=newHashMap<>();static{TRANSITIONS.put("待支付",newString[]{"已支付","已取消"});TRANSITIONS.put("已支付",newString[]{"已发货","已取消"});TRANSITIONS.put("已发货",newString[]{"已完成"});}publicOrderStateMachine(StringinitialState){this.currentState=initialState;}publicvoidtransition(StringtargetState){String[]allowedStates=TRANSITIONS.get(currentState);if(allowedStates==null||!List.of(allowedStates).contains(targetState)){thrownewIllegalStateException("非法状态流转:"+currentState+"→"+targetState);}this.currentState=targetState;}}```解析思路：使用Map存储状态转移规则，通过校验目标状态是否在允许转移列表中实现状态机校验，确保流转符合业务规则。4.答案：```javaimportjava.util.concurrent.atomic.AtomicLong;publicclassConcurrentCounter{privatefinalAtomicLongcount=newAtomicLong(0);publicvoidincrement(){count.incrementAndGet();}publiclonggetCount(){returncount.get();}}```解析思路：使用AtomicLong保证原子性操作，避免多线程竞争导致的数据不一致，通过CAS机制实现高并发安全计数。算法与数据结构（30分）5.答案：B解析思路：递归归并排序采用分治策略，每次将数组分成两半，递归排序后合并，时间复杂度为O(nlogn)。6.答案：B、C、D解析思路：哈希表不支持有序遍历（A错误）；二叉搜索树查找平均时间复杂度O(logn)（B正确）；哈希表冲突解决方式包括链地址法（C正确）；二叉搜索树插入最坏情况（如退化为链表）时间复杂度O(n)（D正确）。7.答案：设dp[i]表示和为i的组合数，状态转移方程：dp[i]=Σdp[i-nums[j]](当i≥nums[j]时)初始条件：dp[0]=1解析思路：完全背包问题，定义dp[i]为和为i的组合数，通过遍历每个数字更新状态，每个数字可重复使用。8.答案：```pythonimportheapqdefdijkstra(graph,start):n=len(graph)dist=[float('inf')]*ndist[start]=0heap=[(0,start)]whileheap:current_dist,u=heapq.heappop(heap)ifcurrent_dist>dist[u]:continueforv,weightingraph[u]:ifdist[v]>dist[u]+weight:dist[v]=dist[u]+weightheapq.heappush(heap,(dist[v],v))returndist```解析思路：使用优先队列（最小堆）实现贪心策略，每次选择当前最短路径节点更新邻居节点距离，确保最短路径非负。数据库与操作系统（20分）9.答案：A、B、C解析思路：B+树索引支持等值查询（A）、范围查询（B）、排序操作（C），全表扫描（D）不需要索引。10.答案：隔离级别：-读未提交：允许读取未提交数据，可能脏读/不可重复读/幻读-读已提交：只读已提交数据，避免脏读，可能不可重复读/幻读-可重复读：多次读取结果一致，避免脏读/不可重复读，可能幻读-串行化：事务串行执行，避免所有问题，性能低幻读示例：-读未提交：事务A查询3条记录，事务B插入1条未提交，事务A再查询得4条-可重复读：事务A首次查询3条，事务B插入并提交，事务A再查询仍3条（MVCC机制）解析思路：通过隔离级别定义和具体场景说明不同级别下的数据一致性问题。11.答案：B、C解析思路：进程切换需保存虚拟内存等资源（B正确），线程切换只需保存寄存器等轻量级状态（C正确）；线程切换开销小于进程（A错误）；两者切换机制不同（D错误）。12.答案：分页机制将虚拟地址空间划分为固定大小的页，物理内存划分为同样大小的帧。通过页表映射虚拟页到物理帧，实现虚拟内存。当访问的页不在内存时，触发缺页中断，从磁盘调入。解析思路：通过页表建立虚拟地址与物理地址的映射关系，支持内存按需分配和虚拟内存管理。网