2026年游戲公司程序員的面試題目與解答一、編程基礎(chǔ)（共5題，每題10分，總分50分）1.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)整數(shù)數(shù)組，返回其中和為特定值的最長子數(shù)組的長度。例如，輸入`[1,-2,3,5,-1,2]`，和為`3`，最長子數(shù)組為`[1,-2,3,5,-1,2]`，長度為`6`。答案：cppinclude<vector>include<unordered_map>usingnamespacestd;intmaxSubArrayLen(vector<int>&nums,inttarget){unordered_map<int,int>memo;//key:前綴和,value:索引intmaxLen=0,sum=0;memo[0]=-1;//初始化前綴和為0時(shí)索引為-1for(inti=0;i<nums.size();++i){sum+=nums[i];if(memo.find(sum-target)!=memo.end()){maxLen=max(maxLen,i-memo[sum-target]);}if(memo.find(sum)==memo.end()){memo[sum]=i;}}returnmaxLen;}解析：使用前綴和+哈希表解決。遍歷數(shù)組時(shí)記錄前綴和`sum`，若`sum-target`存在于哈希表中，則表示子數(shù)組和為`target`，更新最大長度。初始化哈希表`memo[0]=-1`是為了處理從數(shù)組開頭開始的子數(shù)組。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(n)`。2.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，檢查一個(gè)二叉樹是否是完全二叉樹。例如：1/\23/\\456是完全二叉樹。答案：cppinclude<queue>usingnamespacestd;structTreeNode{intval;TreeNodeleft,right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};boolisCompleteTree(TreeNoderoot){if(!root)returntrue;queue<TreeNode>q;q.push(root);boolend=false;//標(biāo)記是否遇到不完整的節(jié)點(diǎn)while(!q.empty()){TreeNodenode=q.front();q.pop();if(!node){end=true;//遇到空節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)必須全部為空}else{if(end)returnfalse;//如果之前有空節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)不能非空q.push(node->left);q.push(node->right);}}returntrue;}解析：層序遍歷二叉樹。使用隊(duì)列逐層遍歷，一旦遇到空節(jié)點(diǎn)，后續(xù)所有節(jié)點(diǎn)必須為空。若遇到非空節(jié)點(diǎn)，但之前已有空節(jié)點(diǎn)，則不是完全二叉樹。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(n)`。3.題目：請(qǐng)實(shí)現(xiàn)快速排序算法，并分析其時(shí)間復(fù)雜度。答案：cppinclude<vector>usingnamespacestd;voidquickSort(vector<int>&arr,intleft,intright){if(left>=right)return;intpivot=arr[left+(right-left)/2];inti=left,j=right;while(i<=j){while(arr[i]<pivot)i++;while(arr[j]>pivot)j--;if(i<=j){swap(arr[i],arr[j]);i++;j--;}}quickSort(arr,left,j);quickSort(arr,i,right);}解析：快速排序是分治算法，選擇基準(zhǔn)值`pivot`，將數(shù)組分為兩部分，遞歸排序。平均時(shí)間復(fù)雜度`O(nlogn)`，最壞`O(n^2)`（如已排序數(shù)組），空間復(fù)雜度`O(logn)`（遞歸棧）。4.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)字符串是否是有效的括號(hào)組合，例如：`"()[]{}"`是有效的，`"([)]"`無效。答案：cppinclude<stack>include<unordered_map>usingnamespacestd;boolisValid(strings){unordered_map<char,char>pairs={{'(',')'},{'[',']'},{'{','}'}};stack<char>st;for(charc:s){if(pairs.find(c)!=pairs.end()){st.push(c);}else{if(st.empty()||pairs[st.top()]!=c)returnfalse;st.pop();}}returnst.empty();}解析：使用棧匹配括號(hào)。遍歷字符串，左括號(hào)入棧，右括號(hào)與棧頂匹配，不匹配則無效。最后棧為空則有效。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(n)`。5.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，合并兩個(gè)有序鏈表，返回合并后的有序鏈表。答案：cppinclude<iostream>usingnamespacestd;structListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodemergeTwoLists(ListNodel1,ListNodel2){ListNodedummy(0);ListNodetail=&dummy;while(l1&&l2){if(l1->val<l2->val){tail->next=l1;l1=l1->next;}else{tail->next=l2;l2=l2->next;}tail=tail->next;}tail->next=l1?l1:l2;returndummy.next;}解析：使用虛擬頭節(jié)點(diǎn)簡化操作。遍歷兩個(gè)鏈表，按順序合并到新鏈表。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(n)`。二、數(shù)據(jù)結(jié)構(gòu)與算法（共5題，每題10分，總分50分）6.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找出數(shù)組中第三大的數(shù)。例如，輸入`[1,2,2,5,3,5]`，返回`2`。答案：cppinclude<vector>include<set>usingnamespacestd;intthirdMax(vector<int>&nums){set<int>top3;for(intnum:nums){top3.insert(num);if(top3.size()>3)top3.erase(top3.begin());}returntop3.size()<3?max_element(nums.begin(),nums.end()):top3.begin();}解析：使用集合維護(hù)前三大的數(shù)。遍歷數(shù)組，插入集合，若集合超過3個(gè)則刪除最小值。最后根據(jù)集合大小返回第三大或最大值。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(1)`（固定大?。?.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)數(shù)是否是快樂數(shù)（每次將該數(shù)替換為各位數(shù)字的平方和，若最終變?yōu)?則是快樂數(shù)）。例如，19是快樂數(shù)：1^2+9^2=82，8^2+2^2=68，6^2+8^2=100，1^2+0^2+0^2=1。答案：cppinclude<unordered_set>usingnamespacestd;intgetSum(intn){intsum=0;while(n>0){sum+=(n%10)(n%10);n/=10;}returnsum;}boolisHappy(intn){unordered_set<int>seen;while(n!=1&&seen.find(n)==seen.end()){seen.insert(n);n=getSum(n);}returnn==1;}解析：使用哈希表記錄出現(xiàn)過的數(shù)，避免無限循環(huán)。若出現(xiàn)重復(fù)數(shù)或變?yōu)?則結(jié)束。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(n)`。8.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找出鏈表的中間節(jié)點(diǎn)。例如：1->2->3->4->5返回`3`。答案：cppinclude<iostream>usingnamespacestd;structListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodemiddleNode(ListNodehead){ListNodeslow=head,fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}returnslow;}解析：使用快慢指針。快指針每次走兩步，慢指針走一步，快指針到末尾時(shí)慢指針在中間。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(1)`。9.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找出數(shù)組中重復(fù)次數(shù)超過`n/2`的元素。例如，輸入`[2,2,1,1,1,2,2]`，返回`2`。答案：cppinclude<vector>usingnamespacestd;intmajorityElement(vector<int>&nums){intcount=0,candidate=0;for(intnum:nums){if(count==0)candidate=num;count+=(num==candidate)?1:-1;}returncandidate;}解析：Boyer-Moore投票算法。維護(hù)候選者和計(jì)數(shù)，遍歷數(shù)組調(diào)整計(jì)數(shù)，最終候選者為答案。時(shí)間復(fù)雜度`O(n)`，空間復(fù)雜度`O(1)`。10.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)非負(fù)整數(shù)`num`轉(zhuǎn)換為羅馬數(shù)字。例如，`1994`轉(zhuǎn)換為`MCMXCIV`。答案：cppinclude<string>usingnamespacestd;stringintToRoman(intnum){vector<pair<int,string>>valueSymbols={{1000,"M"},{900,"CM"},{500,"D"},{400,"CD"},{100,"C"},{90,"XC"},{50,"L"},{40,"XL"},{10,"X"},{9,"IX"},{5,"V"},{4,"IV"},{1,"I"}};stringroman;for(auto&pair:valueSymbols){while(num>=pair.first){roman+=pair.second;num-=pair.first;}}returnroman;}解析：使用映射表將數(shù)字映射為羅馬數(shù)字。從大到小依次匹配，拼接結(jié)果。時(shí)間復(fù)雜度`O(1)`，空間復(fù)雜度`O(1)`。三、系統(tǒng)設(shè)計(jì)（共3題，每題20分，總分60分）11.題目：設(shè)計(jì)一個(gè)簡單的微博系統(tǒng)，支持發(fā)布微博、獲取用戶關(guān)注者的最新動(dòng)態(tài)、獲取用戶粉絲數(shù)。答案：plaintext1.數(shù)據(jù)結(jié)構(gòu)：-User：用戶表（id,name,followers[],following[]）-Tweet：微博表（id,user_id,content,timestamp）2.功能實(shí)現(xiàn)：-發(fā)布微博：-用戶創(chuàng)建Tweet對(duì)象，插入到Tweet表，記錄時(shí)間戳。-獲取關(guān)注者動(dòng)態(tài)：-遍歷用戶的followers，按時(shí)間降序返回其最新N條Tweet。-獲取粉絲數(shù)：-返回User表的followers數(shù)組長度。解析：核心是用戶關(guān)系和動(dòng)態(tài)存儲(chǔ)。使用`User`表記錄關(guān)注關(guān)系，`Tweet`表存儲(chǔ)微博。發(fā)布時(shí)插入新記錄，獲取動(dòng)態(tài)時(shí)按時(shí)間排序?？蓛?yōu)化為Redis緩存關(guān)注者列表。12.題目：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接系統(tǒng)，支持生成短鏈接、訪問短鏈接跳轉(zhuǎn)原鏈接。答案：plaintext1.數(shù)據(jù)結(jié)構(gòu)：-ShortLink：短鏈接表（id,original_url,expire_time）2.生成短鏈接：-使用hash算法（如MD5+base62）將原URL映射為短ID。-檢查是否已存在，若存在則重新生成。-存儲(chǔ)到ShortLink表，設(shè)置有效期。3.訪問跳轉(zhuǎn)：-根據(jù)短ID查詢ShortLink表，返回原URL。-若過期則刪除記錄。解析：關(guān)鍵在于ID映射效率和緩存。使用哈希算法生成短ID，可結(jié)合Redis緩存熱點(diǎn)鏈接，降低數(shù)據(jù)庫壓力。13.題目：設(shè)計(jì)一個(gè)實(shí)時(shí)游戲排行榜系統(tǒng)，支持玩家加入、退出、更新分?jǐn)?shù)、獲取當(dāng)前排行榜。答案：plaintext1.數(shù)據(jù)結(jié)構(gòu)：-Player：玩家表（id,name,score）-Leaderboard：排行榜（使用Redis有序集合）2.功能實(shí)現(xiàn)：-加入/退出：-加入時(shí)插入Player表，更新Redis有序集合（score為分?jǐn)?shù)，id為分?jǐn)?shù)）。-退出時(shí)刪除Player表和Redis記錄。-更新分?jǐn)?shù)：-使用Rediszincrby更新玩家分?jǐn)?shù)，保持排行榜有序。-獲取排行榜：-使用Rediszrevrange獲取前N名玩家id。解析：Redis有序集合`ZSET`適合排行榜，`zincrby`和`zrevrange`高效更新和查詢?？山Y(jié)合MySQL存儲(chǔ)玩家持久化數(shù)據(jù)。四、數(shù)據(jù)庫（共2題，每題15分，總分30分）14.題目：設(shè)計(jì)一個(gè)游戲玩家數(shù)據(jù)表，支持記錄玩家ID、昵稱、等級(jí)、經(jīng)驗(yàn)值，并支持按等級(jí)和經(jīng)驗(yàn)值查詢玩家。答案：sqlCREATETABLEPlayer(idINTPRIMARYKEY,nameVARCHAR(50),levelINT,experienceINT);--查詢等級(jí)大于10的玩家SELECTFROMPlayerWHERElevel>10;--查詢經(jīng)驗(yàn)值在10000到20000之間的玩家SELECTFROMPlayerWHEREexperienceBETWEEN10000AND20000;解析：使用主鍵ID，索引`level`和`experience`加速查詢。可添加觸發(fā)器自動(dòng)更新等級(jí)。15.題目：設(shè)計(jì)一個(gè)游戲物品表，支持記錄物品ID、名稱、類型（武器/道具/消耗品）、價(jià)格，并支持按類型和價(jià)格排序查詢。答案：sqlCREATETABLEItem(idINTPRIMARYKEY,nameVARCHAR(50),typeVARCHAR(20),priceINT);--按類型查詢武器SELECTFROMItemWHEREtype='武器';--按價(jià)格降序查詢道具SELECTFROMItemWHEREtype='道具'ORDERBYpriceDESC;解析：使用類型字段分類，可添加索引`type`和`