华为技术面试题软件工程师篇

2026年华为技术面试题：软件工程师篇一、编程题（共5题，每题20分，总分100分）1.数组轮转题目：给定一个数组和一个正整数k，将数组中的元素向右轮转k次。例如，输入数组`[1,2,3,4,5]`，k=2，输出`[4,5,1,2,3]`。请编写代码实现该功能。要求：-时间复杂度不超过O(n)-不使用额外空间（或使用O(1)额外空间）答案：cppinclude<vector>include<algorithm>usingnamespacestd;vector<int>rotateArray(vector<int>&nums,intk){intn=nums.size();if(n==0)returnnums;k=k%n;//处理k大于n的情况reverse(nums.begin(),nums.end());//反转整个数组reverse(nums.begin(),nums.begin()+k);//反转前k个元素reverse(nums.begin()+k,nums.end());//反转剩余元素returnnums;}解析：-首先将整个数组反转，得到`[5,4,3,2,1]`。-然后反转前k个元素`[4,5,3,2,1]`。-最后反转剩余元素`[4,5,1,2,3]`，得到最终结果。-时间复杂度：O(n)，空间复杂度：O(1)。2.二叉树的最大深度题目：给定一个二叉树，编写函数计算其最大深度（即从根节点到最远叶子节点的最长路径上的节点数）。例如：3/\920/\157最大深度为3。要求：-使用递归或迭代方法实现-时间复杂度O(n)，n为节点数答案：cppinclude<iostream>usingnamespacestd;//定义二叉树节点structTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};//递归方法intmaxDepth(TreeNoderoot){if(root==nullptr)return0;intleft=maxDepth(root->left);intright=maxDepth(root->right);returnmax(left,right)+1;}//迭代方法（使用队列）intmaxDepthIterative(TreeNoderoot){if(root==nullptr)return0;intdepth=0;queue<TreeNode>q;q.push(root);while(!q.empty()){intsize=q.size();depth++;for(inti=0;i<size;i++){TreeNodenode=q.front();q.pop();if(node->left)q.push(node->left);if(node->right)q.push(node->right);}}returndepth;}解析：-递归方法：通过比较左右子树的最大深度，加1得到当前节点的高度。-迭代方法：使用队列进行层序遍历，每层深度加1。-两种方法时间复杂度均为O(n)，空间复杂度递归为O(h)，迭代为O(n)。3.字符串匹配题目：实现字符串匹配算法，查找主串`s`中是否存在子串`p`，如果存在返回子串的起始索引，否则返回-1。例如：-`s="ababa"`,`p="aba"`→返回0-`s="aaaaa"`,`p="aaab"`→返回-1要求：-使用KMP算法实现-时间复杂度O(m+n)，m为s长度，n为p长度答案：cppinclude<vector>include<string>usingnamespacestd;//KMP算法前缀表vector<int>getPrefix(conststring&p){intn=p.size();vector<int>prefix(n,0);intj=0;for(inti=1;i<n;i++){while(j>0&&p[i]!=p[j]){j=prefix[j-1];}if(p[i]==p[j]){j++;}prefix[i]=j;}returnprefix;}//KMP匹配intKMPSearch(conststring&s,conststring&p){if(p.empty())return0;vector<int>prefix=getPrefix(p);inti=0,j=0;while(i<s.size()){if(s[i]==p[j]){i++;j++;}if(j==p.size())returni-j;elseif(i<s.size()&&s[i]!=p[j]){if(j!=0)j=prefix[j-1];elsei++;}}return-1;}解析：-KMP算法通过前缀表避免重复比较，前缀表记录子串p中每个位置的最长相同前后缀长度。-时间复杂度：O(m+n)，空间复杂度：O(n)。4.快速排序题目：实现快速排序算法，并分析其平均时间复杂度和最坏时间复杂度。要求：-使用Hoare分区方案-给出代码实现答案：cppinclude<vector>usingnamespacestd;//Hoare分区intpartition(vector<int>&nums,intleft,intright){intpivot=nums[left];inti=left-1,j=right+1;while(true){do{i++;}while(nums[i]<pivot);do{j--;}while(nums[j]>pivot);if(i>=j)returnj;swap(nums[i],nums[j]);}}//快速排序voidquickSort(vector<int>&nums,intleft,intright){if(left>=right)return;intpivotIndex=partition(nums,left,right);quickSort(nums,left,pivotIndex);quickSort(nums,pivotIndex+1,right);}解析：-快速排序通过分治思想将数组划分为小于和大于枢轴的两部分，再递归排序。-平均时间复杂度：O(nlogn)，最坏时间复杂度：O(n²)（当枢轴选择不均匀时）。-空间复杂度：O(logn)（递归栈）。5.并发编程题目：假设有多个线程需要更新同一个全局变量`count`，请编写线程安全的代码实现该操作。要求：-使用互斥锁（mutex）或原子操作-保证`count`的线程安全性答案：cppinclude<iostream>include<thread>include<mutex>std::mutexmtx;intcount=0;voidincrement(){for(inti=0;i<1000;i++){std::lock_guard<std::mutex>lock(mtx);count++;}}intmain(){std::threadt1(increment);std::threadt2(increment);t1.join();t2.join();std::cout<<"Finalcount:"<<count<<std::endl;return0;}解析：-使用`std::mutex`和`std::lock_guard`确保`count++`操作互斥执行。-也可以使用`std::atomic<int>`实现无锁原子操作。-互斥锁时间复杂度：O(1)，但可能导致线程阻塞。二、算法题（共4题，每题25分，总分100分）1.最长递增子序列（LIS）题目：给定一个无序数组，找到其中最长的严格递增子序列的长度。例如：-输入`[10,9,2,5,3,7,101,18]`→输出4（子序列为`[2,3,7,101]`）要求：-使用动态规划或二分查找实现-时间复杂度O(nlogn)答案：cppinclude<vector>include<algorithm>usingnamespacestd;intlengthOfLIS(vector<int>&nums){if(nums.empty())return0;vector<int>tails;for(intnum:nums){autoit=upper_bound(tails.begin(),tails.end(),num);if(it==tails.end()){tails.push_back(num);}else{it=num;}}returntails.size();}解析：-使用`tails`数组记录以每个位置结尾的最长递增子序列长度。-对于每个数，使用二分查找在`tails`中找到第一个大于等于它的位置，并更新该位置。-最终`tails.size()`即为LIS长度。2.爬楼梯题目：假设你正在爬楼梯，每次可以爬1或2个台阶。给定楼梯总数`n`，计算共有多少种爬法。例如：-`n=3`→输出3（1+1+1,1+2,2+1）要求：-使用动态规划或斐波那契数列-时间复杂度O(n)答案：cppinclude<vector>usingnamespacestd;intclimbStairs(intn){if(n<=2)returnn;vector<int>dp(n+1,0);dp[1]=1;dp[2]=2;for(inti=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}解析：-每个位置爬法等于前两个位置爬法之和，类似斐波那契数列。-动态规划时间复杂度：O(n)，空间复杂度：O(n)；可优化为O(1)空间。3.矩阵旋转题目：给定一个n×n的二维矩阵，原地旋转90度。例如：[[1,2,3],[4,5,6],[7,8,9]]旋转后：[[7,4,1],[8,5,2],[9,6,3]]要求：-先转置矩阵，再反转每一行答案：cppinclude<vector>usingnamespacestd;voidrotate(vector<vector<int>>&matrix){intn=matrix.size();//转置矩阵for(inti=0;i<n;i++){for(intj=i;j<n;j++){swap(matrix[i][j],matrix[j][i]);}}//反转每一行for(inti=0;i<n;i++){reverse(matrix[i].begin(),matrix[i].end());}}解析：-转置矩阵将行变列，列变行。-反转每一行将左上角变为右上角。-时间复杂度：O(n²)，空间复杂度：O(1)。4.括号匹配题目：给定一个字符串，判断其中的括号（`()`、`[]`、`{}`）是否匹配。例如：-`s="()"`→true-`s="([)]"`→false要求：-使用栈结构实现-时间复杂度O(n)答案：cppinclude<stack>include<unordered_map>usingnamespacestd;boolisValid(strings){unordered_map<char,char>pairs={{')','('},{']','['},{'}','{'}};stack<char>st;for(charc:s){if(pairs.count(c)){if(st.empty()||st.top()!=pairs[c])returnfalse;st.pop();}else{st.push(c);}}returnst.empty();}解析：-遇到右括号时，检查栈顶是否为对应左括号，若匹配则弹出，否则不匹配。-最终栈为空则匹配成功。-时间复杂度：O(n)，空间复杂度：O(n)。三、系统设计题（共2题，每题50分，总分100分）1.设计短链接系统题目：设计一个短链接系统，将长链接转换为短链接，并支持通过短链接跳转回原链接。要求：-短链接长度不超过6位（如`aBCdeF`）-支持高并发访问-实现基本功能：生成短链接、解析短链接答案：cppinclude<iostream>include<unordered_map>include<string>include<random>usingnamespacestd;classShortLinkSystem{private:unordered_map<string,string>longToShort;unordered_map<string,string>shortToLong;stringbase="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";random_devicerd;mt19937gen;public:ShortLinkSystem():gen(rd()){}stringgenerateShortLink(conststring&longUrl){stringshortCode;do{shortCode.clear();for(inti=0;i<6;i++){shortCode+=base[gen()%base.size()];}}while(shortToLong.count(shortCode)>0);//避免重复longToShort[longUrl]=shortCode;shortToLong[shortCode]=longUrl;returnshortCode;}stringgetLongLink(conststring&shortCode){returnshortToLong.count(shortCode)?shortToLong[shortCode]:"";}};//示例使用intmain(){ShortLinkSystemsystem;stringlongUrl="/article/12345";stringshortCode=system.generateShortLink(longUrl);cout<<"Shortlink:"<<shortCode<<endl;cout<<"Resolvedlonglink:"<<system.getLongLink(shortCode)<<endl;return0;}解析：-使用随机6位字符作为短链接，确保唯一性。-哈希表存储长链接与短链接的映射关系。-高并发场景下需考虑分布式存储（如Redis）。-优化：可使用Base62编码（a-z,A-Z,0-9）缩短长度。2.设计微博点赞系统题目：设计一个微博点赞系统，支持用户对微博进行点赞/取消点赞，并实时返回点赞数。要求：-支持高并发操作-实现功能：点赞、取消点赞、获取点赞数-数据存储与同步答案：cppinclude<unordered_map>include<mutex>usingnamespacestd;classWeiboLikeSystem{private:unordered_map<int,int>likeCounts;//微博ID->点赞数unordered_map<int,unordered_set<int>>likesMap;//微博ID->点赞用户ID集合mutexmtx;public://点赞voidlike(intweiboId,intuserId){lock_guard<mutex>lock(mtx);if(likesMap.find(weiboId)==likesMap.end()){likesMap[weiboId]=unordered_set<int>();}likesMap