游戏开发部游戏开发工程师面试题及答案

2026年游戏开发部游戏开发工程师面试题及答案一、编程基础（共5题，每题10分，总分50分）1.题目：请用C++实现一个函数，输入一个整数数组，返回该数组中所有子数组的和的最大值。例如，输入`{1,-2,3,5,-1,2}`，输出`12`（子数组`{3,5,-1,2}`）。答案：cppinclude<vector>include<algorithm>usingnamespacestd;intmaxSubArraySum(constvector<int>&nums){intmaxSum=nums[0];intcurrentSum=nums[0];for(size_ti=1;i<nums.size();++i){currentSum=max(nums[i],currentSum+nums[i]);maxSum=max(maxSum,currentSum);}returnmaxSum;}解析：采用动态规划思想，`currentSum`记录以当前元素结尾的最大子数组和，`maxSum`记录全局最大值。时间复杂度O(n)，空间复杂度O(1)。2.题目：用Python实现一个函数，输入一个字符串，返回该字符串中所有重复字符的频率（字典形式）。例如，输入`"hello"`，输出`{'e':1,'l':2,'o':1}`。答案：pythondefchar_frequency(s):freq={}forcharins:freq[char]=freq.get(char,0)+1return{char:countforcharinfreqifcount>1}解析：使用字典统计字符频率，过滤掉只出现一次的字符。3.题目：用Java实现一个方法，判断一个整数是否为完全平方数。例如，输入`16`，返回`true`；输入`14`，返回`false`。答案：javapublicbooleanisPerfectSquare(intnum){if(num<0)returnfalse;longleft=0,right=num;while(left<=right){longmid=left+(right-left)/2;if(midmid==num)returntrue;if(midmid<num)left=mid+1;elseright=mid-1;}returnfalse;}解析：二分查找法判断平方根是否为整数，避免溢出用`long`类型。4.题目：用C#实现一个方法，输入一个字符串，返回该字符串的所有子集（不重复）。例如，输入`"abc"`，输出`{"","a","b","ab","c","ac","bc","abc"}`。答案：csharpusingSystem.Collections.Generic;publicclassSolution{publicIList<string>Subsets(strings){List<string>result=newList<string>();char[]chars=s.ToCharArray();Array.Sort(chars);//保证顺序一致intn=chars.Length;for(inti=0;i<(1<<n);i++){stringsubset="";for(intj=0;j<n;j++){if((i&(1<<j))!=0)subset+=chars[j];}result.Add(subset);}returnresult;}}解析：使用位运算枚举所有子集，时间复杂度O(2^n)。5.题目：用JavaScript实现一个函数，输入一个数组，返回一个新数组，其中每个元素为原数组中该元素之前所有比它小的数的和。例如，输入`[3,1,2,4]`，输出`[0,3,3,8]`。答案：javascriptfunctionsmallerNumbersThanCurrent(nums){constsorted=nums.slice().sort((a,b)=>a-b);constmap=newMap();for(leti=0;i<sorted.length;i++){if(!map.has(sorted[i])){map.set(sorted[i],i);}}returnnums.map(num=>map.get(num));}解析：先排序并记录每个数的较小数个数，再映射回原数组顺序。二、数据结构与算法（共5题，每题10分，总分50分）1.题目：用Python实现快速排序算法，输入一个乱序数组，返回排序后的数组。答案：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)解析：分治思想，选择枢轴划分左右子数组，递归排序。2.题目：用Java实现二叉树的层序遍历（广度优先搜索），返回遍历结果列表。例如，输入`[3,9,20,null,null,15,7]`（对应二叉树），输出`[3,9,20,15,7]`。答案：javaimportjava.util.;publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicList<Integer>levelOrder(TreeNoderoot){List<Integer>result=newArrayList<>();if(root==null)returnresult;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodenode=queue.poll();result.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}returnresult;}解析：使用队列实现BFS，按层遍历二叉树。3.题目：用C++实现深度优先搜索（DFS）遍历一个无向图，输入邻接表，返回遍历顺序。例如，输入`{{1,2},{0,3},{0,3},{1,2}}`（表示节点0连1、2，节点1连0、3等），输出`[0,1,3,2]`。答案：cppinclude<vector>include<iostream>usingnamespacestd;voiddfs(intnode,vector<bool>&visited,vector<int>&result,constvector<vector<int>>&adj){visited[node]=true;result.push_back(node);for(intneighbor:adj[node]){if(!visited[neighbor]){dfs(neighbor,visited,result,adj);}}}vector<int>dfsTraversal(constvector<vector<int>>&adj){intn=adj.size();vector<bool>visited(n,false);vector<int>result;for(inti=0;i<n;++i){if(!visited[i]){dfs(i,visited,result,adj);}}returnresult;}解析：递归实现DFS，标记已访问节点，避免重复遍历。4.题目：用Java实现拓扑排序（Kahn算法），输入有向图的邻接表和入度数组，返回拓扑顺序。例如，输入`adj={{1},{2},{3},{}}`，`inDegree={0,1,1,0}`，输出`[0,1,2,3]`。答案：javaimportjava.util.;publicclassTopologicalSort{publicint[]topologicalSort(intnumCourses,int[][]prerequisites){List<List<Integer>>adj=newArrayList<>();int[]inDegree=newint[numCourses];for(inti=0;i<numCourses;i++)adj.add(newArrayList<>());for(int[]pre:prerequisites){adj.get(pre[1]).add(pre[0]);inDegree[pre[0]]++;}Queue<Integer>queue=newLinkedList<>();for(inti=0;i<numCourses;i++){if(inDegree[i]==0)queue.offer(i);}List<Integer>result=newArrayList<>();while(!queue.isEmpty()){intcourse=queue.poll();result.add(course);for(intneighbor:adj.get(course)){inDegree[neighbor]--;if(inDegree[neighbor]==0)queue.offer(neighbor);}}if(result.size()!=numCourses)returnnewint[0];//无环图returnresult.stream().mapToInt(i->i).toArray();}}解析：Kahn算法基于BFS，每次选入度为0的节点并减去邻接节点入度。5.题目：用Python实现最小生成树（MST）的Kruskal算法，输入边列表（权重、起点、终点），返回MST的边集合。例如，输入`[(1,0,1),(3,1,2),(3,0,2),(6,2,3),(4,1,3)]`，输出`[(1,0,1),(3,1,2),(4,1,3)]`。答案：pythonclassUnionFind:def__init__(self,n):self.parent=list(range(n))self.rank=[0]ndeffind(self,u):ifself.parent[u]!=u:self.parent[u]=self.find(self.parent[u])returnself.parent[u]defunion(self,u,v):root_u=self.find(u)root_v=self.find(v)ifroot_u!=root_v:ifself.rank[root_u]>self.rank[root_v]:self.parent[root_v]=root_uelifself.rank[root_u]<self.rank[root_v]:self.parent[root_u]=root_velse:self.parent[root_v]=root_uself.rank[root_u]+=1returnTruereturnFalsedefkruskal(n,edges):edges.sort()uf=UnionFind(n)mst=[]forweight,u,vinedges:ifuf.union(u,v):mst.append((weight,u,v))returnmst解析：按权重排序边，使用并查集判断是否形成环，选择无环边构建MST。三、数据库与SQL（共3题，每题10分，总分30分）1.题目：用SQL查询出`employees`表中工资高于平均工资的员工姓名和工资。假设表结构为`name(varchar),salary(int)`。答案：sqlSELECTname,salaryFROMemployeesWHEREsalary>(SELECTAVG(salary)FROMemployees);解析：子查询计算平均工资，外层查询筛选高于平均值的记录。2.题目：用SQL查询出`orders`表中每个客户的订单总数，按订单数降序排列。假设表结构为`customer_id(int),order_id(int)`。答案：sqlSELECTcustomer_id,COUNT(order_id)AStotal_ordersFROMordersGROUPBYcustomer_idORDERBYtotal_ordersDESC;解析：GROUPBY分组统计每个客户的订单数，ORDERBY降序排列。3.题目：用SQL查询出`students`表中所有性别为`'male'`且年龄大于18岁的学生姓名和班级，结果按班级升序排列。假设表结构为`name(varchar),gender(varchar),age(int),class(varchar)`。答案：sqlSELECTname,classFROMstudentsWHEREgender='male'ANDage>18ORDERBYclassASC;解析：直接筛选条件，按班级升序排列。四、系统设计（共2题，每题15分，总分30分）1.题目：设计一个简单的在线游戏排行榜系统，要求支持以下功能：-实时更新玩家分数。-查询前N名玩家。-分数相同不重复计入排名。要求：-写出核心表结构设计。-说明使用的数据结构和算法。答案：表结构：sqlCREATETABLErankings(player_idINTPRIMARYKEY,scoreINT,last_updatedTIMESTAMPDEFAULTCURRENT_TIMESTAMPONUPDATECURRENT_TIMESTAMP);数据结构和算法：-使用`player_id`和`score`主键索引，`last_updated`保证实时性。-查询前N名时，按`score`降序排序，相同分数去重（如`scoreDESC,player_idASC`）。-使用堆（如RedisZSET）优化实时更新和查询性能。解析：分布式场景下，RedisZSET存储玩家分数和ID，`SCORE`命令快速排序和查询。2.题目：设计一个简单的聊天系统，支持以下功能：-多用户实时聊天。-消息历史存储。-消息已读未读标记。要求：-写出核心表结构设计。-说明如何实现实时消息推送。答案：表结构：sqlCREATETABLEmessages(msg_idBIGINTAUTO_INCREMENTPRIMARYKEY,sender_idINT,receiver_idINT,contentTEXT,timestampTIMESTAMPDEFAULTCURRENT_TIMESTAMP,is_readBOOLEANDEF