腾讯研发工程师面试指南及答案

2026年腾讯研发工程师面试指南及答案一、编程能力测试（共5题，每题10分，总分50分）1.题目（10分）：实现一个函数，输入一个正整数`n`，返回`1`到`n`中所有奇数的平方和。要求时间复杂度为`O(n)`，空间复杂度为`O(1)`。答案：cppintsumOfOddSquares(intn){intsum=0;for(inti=1;i<=n;i+=2){sum+=ii;}returnsum;}解析：-遍历`1`到`n`的奇数（步长为`2`），计算平方并累加。-时间复杂度：`O(n)`，因为遍历了所有奇数。-空间复杂度：`O(1)`，仅使用`sum`变量存储结果。2.题目（10分）：给定一个字符串`s`，判断是否可以通过删除某些字符使其变为回文串。例如，`s="abca"`可以删除`b`变为"aca"，是回文串。答案：cppboolcanBePalindrome(conststring&s){intleft=0,right=s.size()-1;while(left<right){if(s[left]!=s[right]){//尝试跳过左或右的字符returncanBePalindrome(s.substr(left+1,right-left))||canBePalindrome(s.substr(left,right-left-1));}left++;right--;}returntrue;}解析：-双指针法从两端向中间遍历，遇到不匹配时递归尝试跳过左或右的字符。-递归时间复杂度较高（`O(2^n)`），实际面试可能要求更优解（动态规划）。3.题目（10分）：实现快速排序算法，要求在原地排序（不使用额外数组），并处理重复元素的情况。答案：cppvoidquickSort(vector<int>&nums,intleft,intright){if(left>=right)return;intpivot=nums[left+(right-left)/2];intl=left,r=right;while(l<=r){while(l<=r&&nums[l]<pivot)l++;while(l<=r&&nums[r]>pivot)r--;if(l<=r){swap(nums[l],nums[r]);l++;r--;}}quickSort(nums,left,r);quickSort(nums,l,right);}解析：-选择中间值作为基准（pivot），将小于等于基准的放左边，大于基准的放右边。-处理重复元素时，`l`和`r`会跳过相同的值，避免无限循环。4.题目（10分）：设计一个LRU（最近最少使用）缓存，支持`get`和`put`操作，容量为`capacity`。答案：cppclassLRUCache{private:unordered_map<int,int>cache;list<int>lruList;intcapacity;voidtouch(intkey){if(cache.find(key)!=cache.end()){lruList.remove(key);lruList.push_back(key);}}public:LRUCache(intcapacity_):capacity(capacity_){}intget(intkey){if(cache.find(key)==cache.end())return-1;touch(key);returncache[key];}voidput(intkey,intvalue){if(cache.find(key)!=cache.end()){cache[key]=value;touch(key);}else{if(cache.size()==capacity){intoldest=lruList.front();lruList.pop_front();cache.erase(oldest);}cache[key]=value;lruList.push_back(key);}}};解析：-使用`unordered_map`存储键值对，`list`维护访问顺序。-`get`时将键移到末尾（最近使用），`put`时若超出容量则删除最久未使用的键。5.题目（10分）：实现二叉树的深度优先遍历（前序、中序、后序），要求使用递归和非递归方式。答案：cpp//递归方式voidpreorderTraversal(TreeNoderoot,vector<int>&res){if(!root)return;res.push_back(root->val);preorderTraversal(root->left,res);preorderTraversal(root->right,res);}voidinorderTraversal(TreeNoderoot,vector<int>&res){if(!root)return;inorderTraversal(root->left,res);res.push_back(root->val);inorderTraversal(root->right,res);}voidpostorderTraversal(TreeNoderoot,vector<int>&res){if(!root)return;postorderTraversal(root->left,res);postorderTraversal(root->right,res);res.push_back(root->val);}//非递归方式（前序）voidpreorderTraversalIterative(TreeNoderoot,vector<int>&res){if(!root)return;stack<TreeNode>stk;stk.push(root);while(!stk.empty()){TreeNodenode=stk.top();stk.pop();res.push_back(node->val);if(node->right)stk.push(node->right);if(node->left)stk.push(node->left);}}解析：-递归方式直观但栈溢出风险高。非递归方式使用栈模拟递归，适合大节点树。二、系统设计测试（共2题，每题25分，总分50分）1.题目（25分）：设计一个高并发的短链接生成系统，要求：-支持分布式部署，水平扩展。-链接生成快速，解析效率高。-具备一定的容错能力（如ID丢失重试）。答案：系统架构：1.短链接服务：-每个节点存储部分短链接映射（如`hash(key)%node_count`分配）。-使用Redis缓存热点链接，减少数据库查询。2.分布式ID生成器（如TwitterSnowflake）：-时间戳（41位）+工作机器ID（10位）+序列号（12位）。-保证全局唯一且单调递增。3.数据库设计：-表结构：`id`（主键）、`short_url`（短链接）、`long_url`（原链接）、`timestamp`（创建时间）。-索引：`short_url`和`timestamp`复合索引优化查询。4.容错机制：-检查链接是否存在，若丢失则重新生成并更新缓存。-使用熔断器防止雪崩效应。关键技术：-一致性哈希：分配短链接时避免热点节点。-分片：将ID空间划分为多个区，不同节点处理不同范围。解析：-高并发场景下，分布式ID和Redis缓存是关键。-分片设计需平衡节点负载，避免单点过载。2.题目（25分）：设计一个实时推荐系统，支持用户点击流接入、实时计算与离线冷启动。要求：-处理每秒上万条点击流。-推荐结果需包含Top10热门商品。-支持新商品冷启动（基于规则或轻量模型）。答案：系统架构：1.数据接入层：-Kafka/Flume收集用户行为（点击、购买等）。-TTL清理过期数据，避免冷存储。2.实时计算层（Flink/SparkStreaming）：-Top10热门商品：滑动窗口统计点击量，更新排行榜。-协同过滤：基于用户历史行为计算相似度。3.离线模型：-使用SparkMLlib训练用户画像，定期更新。-新商品加入时，标记为“待评估”并优先推荐。4.冷启动策略：-规则：新商品默认展示给活跃用户。-模型：轻量LRU模型结合点击率预估。关键技术：-增量更新：实时计算与离线模型结果融合。-缓存：Redis存储热门商品和用户画像。解析：-实时计算需保证低延迟，冷启动需平衡探索与利用。-新商品需快速进入推荐池，避免“冷启动困境”。三、算法与数据结构（共3题，每题25分，总分75分）1.题目（25分）：给定一个包含重复元素的数组，找出所有不重复的三元组，使得`a+b+c=0`。例如，`nums=[-1,0,1,2,-1,-4]`，结果为`[[-1,-1,2],[-1,0,1]]`。答案：cppvector<vector<int>>threeSum(vector<int>&nums){sort(nums.begin(),nums.end());vector<vector<int>>res;intn=nums.size();for(inti=0;i<n-2;i++){if(i>0&&nums[i]==nums[i-1])continue;//跳过重复intleft=i+1,right=n-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==0){res.push_back({nums[i],nums[left],nums[right]});//跳过重复while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}elseif(sum<0)left++;elseright--;}}returnres;}解析：-排序后固定第一个数，双指针查找另外两个数。-跳过重复的数以避免重复三元组。2.题目（25分）：设计一个数据结构支持以下操作：-`add(num)`：添加数字。-`find(target)`：返回比`target`小的所有数的平方和。答案：cppclassNumSum{private:multiset<int>nums;unordered_map<int,longlong>cache;longlonggetSum(inttarget){if(cache.find(target)!=cache.end())returncache[target];longlongsum=0;for(intnum:nums){if(numnum<target)sum+=numnum;}cache[target]=sum;returnsum;}public:voidadd(intnum){nums.insert(num);}longlongfind(inttarget){returngetSum(target);}};解析：-使用`multiset`存储有序数字，避免重复。-缓存结果避免重复计算。3.题目（25分）：给定一个字符串`s`，找到最长的无重复字符的子串长度。例如，`s="abcabcbb"`，最长为"abc"，长度3。答案：cppintlengthOfLongestSubstring(strings){intn=s.size();intleft=0,right=0;intmaxLen=0;unordered_set<char>window;while(