2026年互联网企业高级工程师面试题集及答案详解

2026年互联网企业高级工程师面试题集及答案详解一、编程基础与数据结构（15题，共75分）题目1（10分）题目：请实现一个函数，输入一个非负整数n，返回n的二进制表示中1的个数。要求时间复杂度为O(1)。答案：javapublicintcountBits(intn){intcount=0;while(n!=0){count+=n&1;n>>>=1;}returncount;}解析：该方法利用位运算技巧，通过不断与1进行与运算并右移来统计1的个数。时间复杂度为O(1)在n为32位整数时成立，实际互联网企业面试中可能需要考虑64位整数或其他情况。题目2（10分）题目：给定一个数组，请实现一个函数，找出数组中不重复的数字，并返回它们的和。要求空间复杂度为O(1)。答案：javapublicintsumOfUnique(int[]nums){int[]count=newint[21];//假设数字范围在-10到10之间for(intnum:nums){count[num+10]++;}intsum=0;for(inti=0;i<count.length;i++){if(count[i]==1){sum+=i-10;}}returnsum;}解析：通过扩展数组索引范围实现O(1)空间复杂度，实际应用中需要根据数字范围调整方案。题目3（15分）题目：请实现一个函数，判断一个字符串是否是有效的括号组合。例如，输入"()[]{}"返回true，输入"([)]"返回false。要求时间复杂度为O(n)。答案：javapublicbooleanisValid(Strings){Stack<Character>stack=newStack<>();Map<Character,Character>map=newHashMap<>();map.put(')','(');map.put('}','{');map.put(']','[');for(charc:s.toCharArray()){if(map.containsKey(c)){if(stack.isEmpty()||stack.pop()!=map.get(c)){returnfalse;}}else{stack.push(c);}}returnstack.isEmpty();}解析：使用栈结构匹配括号，时间复杂度为O(n)，空间复杂度为O(n)。题目4（15分）题目：请实现一个函数，找出数组中重复次数超过n/2的元素。假设数组非空，且一定存在这样的元素。答案：javapublicintmajorityElement(int[]nums){intcount=0;Integercandidate=null;for(intnum:nums){if(count==0){candidate=num;}count+=(num==candidate)?1:-1;}//验证候选元素count=0;for(intnum:nums){if(num==candidate){count++;}}returncandidate;}解析：摩尔投票算法，时间复杂度为O(n)，空间复杂度为O(1)。题目5（10分）题目：请实现一个函数，将一个非负整数n转换为罗马数字。要求时间复杂度为O(1)。答案：javapublicStringintToRoman(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&&num>0;i++){while(num>=values[i]){sb.append(symbols[i]);num-=values[i];}}returnsb.toString();}解析：通过数组存储罗马数字的基本构成，时间复杂度为O(1)。题目6（15分）题目：请实现一个函数，找出两个有序数组的中位数。假设两个数组长度分别为m和n，且m+n是奇数。答案：javapublicdoublefindMedianSortedArrays(int[]nums1,int[]nums2){inttotal=nums1.length+nums2.length;if(total%2==1){returnfindKth(nums1,0,nums2,0,total/2+1);}else{intleft=findKth(nums1,0,nums2,0,total/2);intright=findKth(nums1,0,nums2,0,total/2+1);return(left+right)/2.0;}}privateintfindKth(int[]nums1,intstart1,int[]nums2,intstart2,intk){if(start1>=nums1.length)returnnums2[start2+k-1];if(start2>=nums2.length)returnnums1[start1+k-1];if(k==1)returnMath.min(nums1[start1],nums2[start2]);intpivot1=start1+k/2-1<nums1.length?nums1[start1+k/2-1]:Integer.MAX_VALUE;intpivot2=start2+k/2-1<nums2.length?nums2[start2+k/2-1]:Integer.MAX_VALUE;if(pivot1<pivot2){returnfindKth(nums1,start1+k/2,nums2,start2,k-k/2);}else{returnfindKth(nums1,start1,nums2,start2+k/2,k-k/2);}}解析：通过二分查找方法，时间复杂度为O(log(min(m,n)))。题目7（15分）题目：请实现一个函数，判断一个字符串是否是回文字符串。要求空间复杂度为O(1)。答案：javapublicbooleanisPalindrome(Strings){intleft=0,right=s.length()-1;while(left<right){while(left<right&&!Character.isLetterOrDigit(s.charAt(left))){left++;}while(left<right&&!Character.isLetterOrDigit(s.charAt(right))){right--;}if(left<right){if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){returnfalse;}left++;right--;}}returntrue;}解析：双指针方法，时间复杂度为O(n)，空间复杂度为O(1)。题目8（10分）题目：请实现一个函数，找出数组中和最大的三个数。假设数组长度至少为3。答案：javapublicint[]maxTopThree(int[]nums){intfirst=Integer.MIN_VALUE,second=Integer.MIN_VALUE,third=Integer.MIN_VALUE;for(intnum:nums){if(num>first){third=second;second=first;first=num;}elseif(num>second){third=second;second=num;}elseif(num>third){third=num;}}returnnewint[]{first,second,third};}解析：遍历一次数组，时间复杂度为O(n)，空间复杂度为O(1)。题目9（15分）题目：请实现一个函数，将一个字符串转换为一个整数。假设字符串可能包含正负号，且可能包含前导空格。要求时间复杂度为O(n)。答案：javapublicintstrToInt(Strings){if(s==null||s.length()==0)return0;inti=0;intn=s.length();booleannegative=false;//去除前导空格while(i<n&&s.charAt(i)==''){i++;}if(i<n&&(s.charAt(i)=='+'||s.charAt(i)=='-')){negative=s.charAt(i)=='-';i++;}intresult=0;while(i<n&&Character.isDigit(s.charAt(i))){intdigit=s.charAt(i)-'0';//溢出判断if(result>(Integer.MAX_VALUE-digit)/10){returnnegative?Integer.MIN_VALUE:Integer.MAX_VALUE;}result=result10+digit;i++;}returnnegative?-result:result;}解析：模拟整数解析过程，时间复杂度为O(n)，需要考虑溢出情况。题目10（10分）题目：请实现一个函数，找出数组中重复的数字，但只返回出现次数超过1次的数字。假设数组长度为n，且n>=2。答案：javapublicList<Integer>findDuplicates(int[]nums){List<Integer>duplicates=newArrayList<>();for(intnum:nums){intindex=Math.abs(num)-1;if(nums[index]<0){duplicates.add(Math.abs(num));}else{nums[index]=-nums[index];}}//恢复数组for(inti=0;i<nums.length;i++){nums[i]=Math.abs(nums[i]);}returnduplicates;}解析：通过数组索引标记访问情况，时间复杂度为O(n)，空间复杂度为O(1)。二、算法设计（5题，共50分）题目11（10分）题目：请设计一个算法，找出数组中第k小的元素。假设数组已排序，且k有效（1<=k<=数组长度）。答案：javapublicintfindKthSmallest(int[]nums,intk){intleft=0,right=nums.length-1;intkth=k-1;//数组索引从0开始while(left<right){intpivot=partition(nums,left,right);if(pivot==kth){returnnums[pivot];}elseif(pivot<kth){left=pivot+1;}else{right=pivot-1;}}returnnums[left];}privateintpartition(int[]nums,intleft,intright){intpivot=nums[right];inti=left;for(intj=left;j<right;j++){if(nums[j]<=pivot){swap(nums,i,j);i++;}}swap(nums,i,right);returni;}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}解析：快速选择算法，时间复杂度为O(n)，空间复杂度为O(1)。题目12（10分）题目：请设计一个算法，实现LRU缓存机制。要求实现LRU（LeastRecentlyUsed）缓存，当缓存容量已满时，应该丢弃最久未使用的缓存项。答案：javapublicclassLRUCache{privateintcapacity;privateMap<Integer,Integer>cache;privateDeque<Integer>deque;publicLRUCache(intcapacity){this.capacity=capacity;cache=newLinkedHashMap<>(capacity,0.75f,true);deque=newLinkedList<>();}publicintget(intkey){if(!cache.containsKey(key)){return-1;}deque.remove(key);deque.addLast(key);returncache.get(key);}publicvoidput(intkey,intvalue){if(cache.containsKey(key)){deque.remove(key);}elseif(cache.size()==capacity){intfirst=deque.removeFirst();cache.remove(first);}cache.put(key,value);deque.addLast(key);}}解析：使用LinkedHashMap实现LRU缓存，时间复杂度为O(1)，空间复杂度为O(capacity)。题目13（15分）题目：请设计一个算法，找出所有可能的括号组合。例如，输入n=3，应该返回["((()))","(()())","(())()","()(())","()()()"]。答案：javapublicList<String>generateParenthesis(intn){List<String>result=newArrayList<>();backtrack(result,"",0,0,n);returnresult;}privatevoidbacktrack(List<String>result,Stringcurrent,intopen,intclose,intmax){if(current.length()==max2){result.add(current);return;}if(open<max){backtrack(result,current+"(",open+1,close,max);}if(close<open){backtrack(result,current+")",open,close+1,max);}}解析：回溯算法生成括号组合，时间复杂度为O(4^n/n^(3/2))，空间复杂度为O(n)。题目14（15分）题目：请设计一个算法，找出所有无重复字符的最长子串。例如，输入"abcabcbb"返回"abc"。答案：javapublicintlengthOfLongestSubstring(Strings){int[]charIndex=newint[128];Arrays.fill(charIndex,-1);intmaxLength=0;intstart=0;for(inti=0;i<s.length();i++){charc=s.charAt(i);if(charIndex[c]>=start){start=charIndex[c]+1;}charIndex[c]=i;maxLength=Math.max(maxLength,i-start+1);}returnmaxLength;}解析：滑动窗口算法，时间复杂度为O(n)，空间复杂度为O(1)。题目15（10分）题目：请设计一个算法，实现二叉树的层序遍历。假设使用队列实现。答案：javapublicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();if(root==null)returnresult;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<size;i++){TreeNodenode=queue.poll();level.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}result.add(level);}returnresult;}解析：队列实现广度优先搜索，时间复杂度为O(n)，空间复杂度为O(n)。三、系统设计（3题，共25分）题目16（10分）题目：请设计一个简单的秒杀系统。假设每秒最多处理1000个请求，且商品库存为10000。答案：javapublicclassSecKillSystem{privateintstock;privatelonglastTimestamp=-1;privateintrequestCount=0;publicSecKillSystem(intstock){this.stock=stock;}publicbooleantrySecKill(longuserId){longtimestamp=System.currentTimeMillis();//控制每秒请求次数if(timestamp!=lastTimestamp){lastTimestamp=timestamp;requestCount=0;}if(requestCount>=1000){returnfalse;}synchronized(this){if(stock>0){stock--;requestCount++;returntrue;}}returnfalse;}}解析：简单秒杀系统设计，需要考虑并发控制，实际系统需要更复杂的方案。题目17（10分）题目：请设计一个简单的消息队列系统。假设支持最多10000个并发连接，消息最大容量为1024字节。答案：javapublicclassMessageQueueSystem{privatestaticfinalintMAX_CONNECTIONS=10000;privatestaticfinalintMAX_MESSAGE_SIZE=1024;privateQueue<Message>queue;privateSet<Integer>connections;publicMessageQueueSystem(){queue=newLinkedList<>();connections=Collections.synchronizedSet(newHashSet<>());}publicbooleanconnect(intconnectionId){if(connections.size()>=MAX_CONNECTIONS){returnfalse;}connections.add(connectionId);returntrue;}publicbooleandisconnect(intconnectionId){returnconnections.remove(connectionId);}publicbooleansendMessage(intconnectionId,byte[]message){if(message.length>MAX_MESSAGE_SIZE){returnfalse;}if(!connections.contains(connectionId)){returnfalse;}queue.offer(newMessage(connectionId,message));returntrue;}publicMessagereceiveMessage(intconnectionId){synchronized(queue){for(Messagemsg:queue){if(msg.connectionId==connectionId){queue.remove(msg);returnmsg;}}}returnnull;}privatestaticclassMessage{intconnectionId;byte[]data;publicMessage(intconnectionId,byte[]data){this.connectionId=connectionId;this.data=data;}}}解析：简单消息队列系统设计，需要考虑并发连接和消息存储。题目18（5分）题目：请设计一个简单的分布式锁。假设使用Redis实现。答案：javapublicclassRedisDistributedLo