2025年初级软件开发工程师面试攻略编程与算法预测题

2025年初级软件开发工程师面试攻略：编程与算法预测题一、编程题（共5题，每题20分）题目1：字符串反转题目描述：编写一个函数，接收一个字符串作为输入，返回该字符串的反转版本。例如，输入`"hello"`，输出`"olleh"`。要求：1.不使用内置的反转函数或方法。2.实现空间复杂度为O(1)的解法（如果可能）。3.处理空字符串和单字符字符串的情况。示例：plaintext输入:"hello"输出:"olleh"题目2：合并两个有序数组题目描述：给定两个有序数组`nums1`和`nums2`，它们的长度分别为`m`和`n`。编写一个函数，将`nums2`合并到`nums1`中，使合并后的数组仍然有序。假设`nums1`有足够的空间容纳`nums2`的元素。要求：1.初始时，`nums1`的后`n`个元素为空。2.合并后的数组应当有序，且不使用额外的空间。3.时间复杂度为O(m+n)。示例：plaintext输入:nums1=[1,2,3,0,0,0],m=3,nums2=[2,5,6],n=3输出:[1,2,2,3,5,6]题目3：实现LRU缓存题目描述：设计一个LRU（LeastRecentlyUsed）缓存系统。LRU缓存会删除最近最少使用的项目。缓存应该支持以下操作：-`get(key)`：获取键`key`的值（如果键存在，则返回值，并将其标记为最近最少使用；如果键不存在，返回-1）。-`put(key,value)`：向缓存中插入一个键值对。如果键已经存在，则更新其值；如果键不存在，则插入键值对。如果插入后缓存大小超过限制，则删除最近最少使用的项目。要求：1.使用哈希表和双向链表实现。2.`get`和`put`操作的时间复杂度为O(1)。示例：plaintextLRUCachecache=newLRUCache(2)cache.put(1,1)cache.put(2,2)cache.get(1)//返回1cache.put(3,3)//去除键2cache.get(2)//返回-1(未找到)cache.put(4,4)//去除键1cache.get(1)//返回-1(未找到)cache.get(3)//返回3cache.get(4)//返回4题目4：二叉树遍历题目描述：给定一个二叉树，编写一个函数，分别实现前序遍历、中序遍历和后序遍历。可以使用递归或迭代的方式实现。要求：1.使用递归和迭代两种方法实现每种遍历。2.树的节点定义如下：plaintextclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}示例：plaintext输入:root=[1,2,3]输出:前序遍历:[1,2,3]中序遍历:[2,1,3]后序遍历:[2,3,1]题目5：查找数组中的最长递增子序列题目描述：给定一个无序的整数数组，编写一个函数，找到数组中的最长递增子序列的长度。子序列不需要连续，但必须是递增的。要求：1.时间复杂度为O(nlogn)。2.可以使用二分查找优化。示例：plaintext输入:[10,9,2,5,3,7,101,18]输出:4解释:最长递增子序列是[2,3,7,101]或[2,5,7,101]。二、算法题（共5题，每题20分）题目1：递归与迭代题目描述：编写一个函数，使用递归和迭代两种方法计算阶乘。阶乘的定义为：`n!=n*(n-1)*...*1`，其中`n>=0`。要求：1.处理`n=0`和`n=1`的情况。2.避免栈溢出问题（针对递归方法）。示例：plaintext输入:5输出:120题目2：动态规划题目描述：给定一个整数数组`nums`，编写一个函数，找到其中和最大的连续子数组的和。子数组最少包含一个元素。要求：1.使用动态规划方法。2.时间复杂度为O(n)。示例：plaintext输入:[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大，为6。题目3：贪心算法题目描述：给定一个整数数组`nums`和一个整数`k`，编写一个函数，找到长度为`k`的子数组，使得子数组中所有元素的乘积最小，并返回这个最小乘积。要求：1.使用贪心算法。2.时间复杂度为O(n)。示例：plaintext输入:nums=[1,2,-1,-3,5],k=3输出:-3解释:子数组[-3,5,1]的乘积最小，为-3。题目4：深度优先搜索题目描述：给定一个二叉树，编写一个函数，判断该二叉树是否是平衡二叉树。平衡二叉树的定义是：对于树中的每个节点，其左右子树的高度差不超过1。要求：1.使用深度优先搜索（DFS）方法。2.时间复杂度为O(n)。示例：plaintext输入:root=[3,9,20,null,null,15,7]输出:true题目5：广度优先搜索题目描述：给定一个无向图，编写一个函数，找到图中所有节点的最短路径长度。图使用邻接表表示。要求：1.使用广度优先搜索（BFS）方法。2.处理图中可能存在的环。示例：plaintext输入:graph=[[1,2],[0,2],[0,1,3],[2]]输出:[0,1,1,2]解释:从节点0出发，到其他节点的最短路径长度分别为0,1,1,2。答案编题目1：字符串反转答案：plaintext//递归方法functionreverseString(s:string):string{if(s.length<=1)returns;returnreverseString(s.slice(1))+s.charAt(0);}//迭代方法functionreverseStringIterative(s:string):string{letresult='';for(leti=s.length-1;i>=0;i--){result+=s[i];}returnresult;}编题目2：合并两个有序数组答案：plaintextfunctionmerge(nums1:number[],m:number,nums2:number[],n:number):void{letp1=m-1;letp2=n-1;letp=m+n-1;while(p1>=0&&p2>=0){if(nums1[p1]>nums2[p2]){nums1[p]=nums1[p1];p1--;}else{nums1[p]=nums2[p2];p2--;}p--;}//复制nums2的剩余元素while(p2>=0){nums1[p]=nums2[p2];p2--;p--;}}编题目3：实现LRU缓存答案：plaintextclassLRUCache{privatecapacity:number;privatecache:Map<number,number>;privatehead:DLLNode;privatetail:DLLNode;constructor(capacity:number){this.capacity=capacity;this.cache=newMap();this.head=newDLLNode(0,0);this.tail=newDLLNode(0,0);this.head.next=this.tail;this.tail.prev=this.head;}get(key:number):number{if(!this.cache.has(key))return-1;constnode=this.cache.get(key)!;this.remove(node);this.add(node);returnnode.value;}put(key:number,value:number):void{if(this.cache.has(key)){this.remove(this.cache.get(key)!);}if(this.cache.size===this.capacity){this.remove(this.tail.prev!);}this.add(newDLLNode(key,value));this.cache.set(key,this.tail.prev!);}privateremove(node:DLLNode):void{this.cache.delete(node.key);node.prev!.next=node.next;node.next!.prev=node.prev;}privateadd(node:DLLNode):void{node.next=this.head.next;node.next!.prev=node;this.head.next=node;node.prev=this.head;this.cache.set(node.key,node);}}classDLLNode{key:number;value:number;next:DLLNode;prev:DLLNode;constructor(key:number,value:number){this.key=key;this.value=value;this.next=null;this.prev=null;}}编题目4：二叉树遍历答案：plaintext//递归方法//前序遍历functionpreorderTraversal(root:TreeNode):number[]{constresult:number[]=[];functiondfs(node:TreeNode){if(!node)return;result.push(node.val);dfs(node.left);dfs(node.right);}dfs(root);returnresult;}//中序遍历functioninorderTraversal(root:TreeNode):number[]{constresult:number[]=[];functiondfs(node:TreeNode){if(!node)return;dfs(node.left);result.push(node.val);dfs(node.right);}dfs(root);returnresult;}//后序遍历functionpostorderTraversal(root:TreeNode):number[]{constresult:number[]=[];functiondfs(node:TreeNode){if(!node)return;dfs(node.left);dfs(node.right);result.push(node.val);}dfs(root);returnresult;}//迭代方法//前序遍历functionpreorderTraversalIterative(root:TreeNode):number[]{constresult:number[]=[];conststack:TreeNode[]=[root];while(stack.length){constnode=stack.pop()!;result.push(node.val);if(node.right)stack.push(node.right);if(node.left)stack.push(node.left);}returnresult;}//中序遍历functioninorderTraversalIterative(root:TreeNode):number[]{constresult:number[]=[];conststack:TreeNode[]=[];letcurrent=root;while(stack.length||current){while(current){stack.push(current);current=current.left;}current=stack.pop()!;result.push(current.val);current=current.right;}returnresult;}//后序遍历functionpostorderTraversalIterative(root:TreeNode):number[]{constresult:number[]=[];conststack:TreeNode[]=[root];while(stack.length){constnode=stack.pop()!;result.push(node.val);if(node.left)stack.push(node.left);if(node.right)stack.push(node.right);}returnresult.reverse();}编题目5：查找数组中的最长递增子序列答案：plaintextfunctionlengthOfLIS(nums:number[]):number{consttails:number[]=[];for(constnumofnums){letleft=0;letright=tails.length;while(left<right){constmid=Math.floor((left+right)/2);if(tails[mid]<num){left=mid+1;}else{right=mid;}}if(left===tails.length){tails.push(num);}else{tails[left]=num;}}returntails.length;}算题目1：递归与迭代答案：plaintext//递归方法functionfactorialRecursive(n:number):number{if(n<=1)return1;returnn*factorialRecursive(n-1);}//迭代方法functionfactorialIterative(n:number):number{letresult=1;for(leti=2;i<=n;i++){result*=i;}returnresult;}算题目2：动态规划答案：plaintextfunctionmaxSubArray(nums:number[]):number{letmaxSum=nums[0];letcurrentSum=nums[0];for(leti=1;i<nums.length;i++){currentSum=Math.max(nums[i],currentSum+nums[i]);maxSum=Math.max(maxSum,currentSum);}returnmaxSum;}算题目3：贪心算法答案：plaintextfunctionminProductSubarray(nums:number[],k:number):number{letminProduct=nums[0];letcurrentProduct=nums[0];for(leti=1;i<k;i++){currentProduct*=nums[i];minProduct=Math.min(minProduct,currentProduct);}for(leti=k;i<nums.length;i++){currentProduct/=nums[i-k];currentProduct*=nums[i];minProduct=Math.min(minProduct,currentProduct);}returnminProduct;}算题目4：深度优先搜索答案：plaintextfunctionisBalanced(root:TreeNode):boolean{functioncheckHeight(node:TreeNode):number{if(!node)return0;constleftHeight=checkHeight(node.left);if(leftHeight===-1)return-1;constrightHeight=checkHeight(node.right);if(rightHeight===-1)return-1;if(Math.abs(leftHeight-rightHeight)>1)return-1;returnMath.max(leftHeight,rightHeight)+1;}returncheckHeight(root)!==-1;}算题目5：广度优先搜索答案：plaintextfunctionshortestPathLength(graph:number[][]):number[]{constn=graph.length;constvisited=newArray(n).fill(false);constdistances=newArray(n).fill(Infinity);constqueue:number[]=[];for(leti=0;i<n;i++){distances[i]=0;queue.push(i);visited[i]