华为OD技术面试实战模拟题库

华为OD技术面试实战模拟题库本文借鉴了近年相关经典试题创作而成，力求帮助考生深入理解测试题型，掌握答题技巧，提升应试能力。一、编程题1.题目：给定一个字符串，请编写代码找到并返回该字符串中最长的回文子串。例如，输入："babad"，输出可以是"bab"或"aba"。```javapublicclassLongestPalindromicSubstring{publicStringlongestPalindrome(Strings){//请在此处编写代码}}```2.题目：实现一个函数，输入是一个非负整数，输出是其对应的英文表示。例如，输入123，输出"OneHundredTwentyThree"。```javapublicclassNumberToWordsConverter{publicStringnumberToWords(intnum){//请在此处编写代码}}```3.题目：给定一个包含n个整数的数组，判断数组中是否存在三个元素a,b,c，使得a+b+c=0。请找出所有不重复的三元组。```javapublicclassThreeSum{publicList<List<Integer>>threeSum(int[]nums){//请在此处编写代码}}```4.题目：编写一个函数，输入是一个字符串，输出是该字符串的所有排列组合。例如，输入"abc"，输出["abc","acb","bac","bca","cab","cba"]。```javapublicclassStringPermutations{publicList<String>permute(Strings){//请在此处编写代码}}```5.题目：给定一个二叉树，请编写代码判断它是否是高度平衡的二叉树。一棵高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。```javapublicclassBalancedBinaryTree{publicbooleanisBalanced(TreeNoderoot){//请在此处编写代码}}```二、算法题1.题目：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回新的数组长度。不要使用额外空间。```javapublicclassRemoveDuplicates{publicintremoveDuplicates(int[]nums){//请在此处编写代码}}```2.题目：实现一个Trie（前缀树）数据结构，包含插入和搜索功能。```javapublicclassTrie{//请在此处编写代码}```3.题目：给定一个链表，判断链表中是否有环。如果链表中有环，返回true，否则返回false。```javapublicclassListNode{intval;ListNodenext;ListNode(intx){val=x;next=null;}}publicclassLinkedListCycle{publicbooleanhasCycle(ListNodehead){//请在此处编写代码}}```4.题目：给定一个非空数组，返回此数组中第三大的数。如果数组中少于三个不同的数，返回最大的数。```javapublicclassThirdMaximumNumber{publicintthirdMax(int[]nums){//请在此处编写代码}}```5.题目：编写一个函数，输入是一个非负整数，返回其对应的罗马数字表示。例如，输入3，输出"III"。```javapublicclassIntegerToRoman{publicStringintToRoman(intnum){//请在此处编写代码}}```三、系统设计题1.题目：设计一个简单的微博系统，包括用户发布微博、关注用户、获取关注用户的微博列表等功能。2.题目：设计一个短链接生成系统，要求能够将长链接转换为短链接，并且能够通过短链接访问到原始的长链接。3.题目：设计一个简单的消息队列系统，包括生产者发送消息、消费者接收消息等功能。4.题目：设计一个简单的电商系统，包括商品展示、购物车、订单管理等功能。5.题目：设计一个简单的在线投票系统，包括用户投票、查看投票结果等功能。四、面试题1.题目：请谈谈你对面向对象编程的理解，并举例说明。2.题目：请解释一下什么是多线程编程，并举例说明你在项目中是如何使用多线程的。3.题目：请谈谈你对数据库索引的理解，并说明索引的作用。4.题目：请解释一下什么是RESTfulAPI，并举例说明你在项目中是如何设计和使用RESTfulAPI的。5.题目：请谈谈你对软件测试的理解，并说明你在项目中是如何进行软件测试的。答案和解析一、编程题1.答案：```javapublicclassLongestPalindromicSubstring{publicStringlongestPalindrome(Strings){if(s==null||s.length()<1)return"";intstart=0,end=0;for(inti=0;i<s.length();i++){intlen1=expandAroundCenter(s,i,i);intlen2=expandAroundCenter(s,i,i+1);intlen=Math.max(len1,len2);if(len>end-start){start=i-(len-1)/2;end=i+len/2;}}returns.substring(start,end+1);}privateintexpandAroundCenter(Strings,intleft,intright){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}returnright-left-1;}}```2.答案：```javapublicclassNumberToWordsConverter{privatefinalString[]units={"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};privatefinalString[]teens={"","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};privatefinalString[]tens={"","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};publicStringnumberToWords(intnum){if(num==0)return"Zero";returnhelper(num).trim();}privateStringhelper(intnum){StringBuildersb=newStringBuilder();if(num>=1000000){sb.append(helper(num/1000000)).append("Million");num%=1000000;}if(num>=1000){sb.append(helper(num/1000)).append("Thousand");num%=1000;}if(num>=100){sb.append(units[num/100]).append("Hundred");num%=100;}if(num>=20){sb.append(tens[num/10]).append("");num%=10;}if(num>0){sb.append(num<10?units[num]:teens[num-11]);sb.append("");}returnsb.toString();}}```3.答案：```javapublicclassThreeSum{publicList<List<Integer>>threeSum(int[]nums){Arrays.sort(nums);List<List<Integer>>result=newArrayList<>();for(inti=0;i<nums.length-2;i++){if(i>0&&nums[i]==nums[i-1])continue;intleft=i+1,right=nums.length-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==0){result.add(Arrays.asList(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++;}else{right--;}}}returnresult;}}```4.答案：```javapublicclassStringPermutations{publicList<String>permute(Strings){List<String>result=newArrayList<>();if(s==null)returnresult;char[]chars=s.toCharArray();permuteHelper(chars,0,result);returnresult;}privatevoidpermuteHelper(char[]chars,intstart,List<String>result){if(start==chars.length-1){result.add(newString(chars));}else{for(inti=start;i<chars.length;i++){swap(chars,start,i);permuteHelper(chars,start+1,result);swap(chars,start,i);}}}privatevoidswap(char[]chars,inti,intj){chartemp=chars[i];chars[i]=chars[j];chars[j]=temp;}}```5.答案：```javapublicclassBalancedBinaryTree{publicbooleanisBalanced(TreeNoderoot){returncheckHeight(root)!=-1;}privateintcheckHeight(TreeNodenode){if(node==null)return0;intleftHeight=checkHeight(node.left);if(leftHeight==-1)return-1;intrightHeight=checkHeight(node.right);if(rightHeight==-1)return-1;if(Math.abs(leftHeight-rightHeight)>1)return-1;returnMath.max(leftHeight,rightHeight)+1;}}```二、算法题1.答案：```javapublicclassRemoveDuplicates{publicintremoveDuplicates(int[]nums){if(nums==null||nums.length==0)return0;intslow=0;for(intfast=1;fast<nums.length;fast++){if(nums[fast]!=nums[slow]){slow++;nums[slow]=nums[fast];}}returnslow+1;}}```2.答案：```javapublicclassTrie{privateTrieNoderoot;publicTrie(){root=newTrieNode();}publicvoidinsert(Stringword){TrieNodenode=root;for(charc:word.toCharArray()){if(!node.containsKey(c)){node.put(c,newTrieNode());}node=node.get(c);}node.setEnd();}publicbooleansearch(Stringword){TrieNodenode=searchPrefix(word);returnnode!=null&&node.isEnd();}publicbooleanstartsWith(Stringprefix){returnsearchPrefix(prefix)!=null;}privateTrieNodesearchPrefix(Stringprefix){TrieNodenode=root;for(charc:prefix.toCharArray()){if(!node.containsKey(c)){returnnull;}node=node.get(c);}returnnode;}privatestaticclassTrieNode{privateTrieNode[]children;privatebooleanisEnd;publicTrieNode(){children=newTrieNode[26];isEnd=false;}publicbooleancontainsKey(charc){returnchildren[c-'a']!=null;}publicTrieNodeget(charc){returnchildren[c-'a'];}publicvoidput(charc,TrieNodenode){children[c-'a']=node;}publicvoidsetEnd(){isEnd=true;}}}```3.答案：```javapublicclassListNode{intval;ListNodenext;ListNode(intx){val=x;next=null;}}publicclassLinkedListCycle{publicbooleanhasCycle(ListNodehead){if(head==null||head.next==null)returnfalse;ListNodeslow=head,fast=head.next;while(slow!=fast){if(fast==null||fast.next==null)returnfalse;slow=slow.next;fast=fast.next.next;}returntrue;}}```4.答案：```javapublicclassThirdMaximumNumber{publicintthirdMax(int[]nums){Integermax1=null,max2=null,max3=null;for(intnum:nums){if(num.equals(max1)||num.equals(max2)||num.equals(max3))continue;if(max1==null||num>max1){max3=max2;max2=max1;max1=num;}elseif(max2==null||num>max2){max3=max2;max2=num;}elseif(max3==null||num>max3){max3=num;}}returnmax3==null?max1:max3;}}```5.答案：```javapublicclassIntegerToRoman{publicStringintToRoman(intnum){int[]values={1000,900,500,400,100,90,50,40,10,9,5,4,1};String[]symbols={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};StringBuildersb=newStringBuilder();for(inti=0;i<values.length;i++){while(num>=values[i]){sb.append(symbols[i]);num-=values[i];}}returnsb.toString();}}```三、系统设计题1.答案：-用户发布微博：用户输入微博内容，系统生成一个微博ID，存储微博内容和用户ID、发布时间等信息。-关注用户：用户可以选择关注其他用户，系统存储用户关注关系。-获取关注用户的微博列表：系统根据用户关注关系，获取关注用户的微博列表，并按时间倒序排列。2.答案：-生成短链接：将长链接转换为短链接，可以使用哈希算法（如MD5）生成一个短字符串作为短链接。-访问短链接：通过短链接访问到原始的长链接，系统根据短链接查询到原始的长链接，并返回给用户。3.答案：-生产者发送消息：生产者将消息发送到消息队列中，系统存储消息并通知消费者。-消费者接收消息：消费者从消息队列