联想工程师研发面试题目

2026年联想工程师研发面试题目一、编程语言基础（3题，每题10分，共30分）1.题目：请用C++实现一个函数，该函数接收一个整数数组和一个目标值，返回数组中和为目标值的两个数的索引。假设每个输入只对应一个解，且不能重复利用同一个元素。例如，给定nums=[2,7,11,15],target=9，返回[0,1]。2.题目：请用Python实现一个类，该类包含一个方法，用于判断一个字符串是否为有效的括号字符串（只包含'{'、'}'、'['、']'、'('、')'，且括号正确匹配）。例如，输入"()[]{}"应返回True，输入"([)]"应返回False。3.题目：请用Java实现一个方法，接收一个字符串，返回该字符串中每个字符的出现次数。例如，输入"hello"应返回{'h':1,'e':1,'l':2,'o':1}。二、数据结构与算法（5题，每题12分，共60分）1.题目：请解释快速排序的基本原理，并说明其时间复杂度和空间复杂度。假设你正在对包含重复元素的数组进行快速排序，如何优化算法以避免最坏情况的发生？2.题目：请设计一个算法，找出无重复元素数组中第三大的数。如果数组中少于三个不同的数，返回最大的数。例如，输入[3,2,1,5,6,4]应返回5，输入[1,2]应返回2。3.题目：请实现一个二叉树的中序遍历算法，可以使用递归或迭代方式。假设树的节点定义如下：javaclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}4.题目：请解释什么是动态规划，并举一个具体例子说明如何使用动态规划解决背包问题。假设背包的最大容量为W，物品重量和价值分别为weights和values，如何计算最大价值？5.题目：请实现一个LRU（最近最少使用）缓存，支持get和put操作。LRU缓存应该能够删除最近最少使用的项，以给新项留出空间。假设缓存容量为capacity。三、操作系统与计算机网络（4题，每题15分，共60分）1.题目：请解释进程和线程的区别，并说明在多线程编程中如何解决竞态条件问题。假设你正在开发一个多线程程序，如何使用互斥锁（mutex）来保护共享资源？2.题目：请解释TCP三次握手和四次挥手的过程，并说明为什么TCP需要三次握手而UDP不需要。假设你在调试一个TCP连接失败的问题，可能的原因有哪些？3.题目：请解释HTTP和HTTPS的区别，并说明HTTPS的工作原理（包括SSL/TLS握手过程）。假设你正在优化一个网站的HTTPS性能，可以采取哪些措施？4.题目：请解释DNS解析的过程，并说明为什么DNS缓存很重要。假设你在排查一个网站无法访问的问题，如何使用命令行工具（如nslookup或dig）进行诊断？四、数据库与SQL（3题，每题20分，共60分）1.题目：请写一个SQL查询，找出员工工资高于其所在部门平均工资的所有员工。假设有以下表结构：sqlEmployee(id,name,salary,department_id)Department(id,name)2.题目：请写一个SQL查询，找出所有订单中每种产品的总销售额。假设有以下表结构：sqlOrder(id,product_id,quantity,price)Product(id,name)3.题目：请解释什么是事务，并说明事务的ACID特性。假设你在开发一个电商系统，如何保证订单处理的原子性和一致性？五、系统设计（2题，每题25分，共50分）1.题目：请设计一个简单的微博系统，需要支持用户注册、登录、发布微博、关注/取消关注、查看关注列表微博等功能。请说明主要的数据结构和数据库表设计。2.题目：请设计一个高并发的短链接系统，需要支持用户生成短链接、访问短链接跳转到原链接、统计短链接访问次数等功能。请说明主要的技术选型和系统架构。答案与解析一、编程语言基础1.C++实现两数之和：cppvector<int>twoSum(vector<int>&nums,inttarget){unordered_map<int,int>numMap;for(inti=0;i<nums.size();i++){intcomplement=target-nums[i];if(numMap.find(complement)!=numMap.end()){return{numMap[complement],i};}numMap[nums[i]]=i;}return{};}解析：使用哈希表存储遍历过程中的数字及其索引，每次遍历时检查target减去当前数字的值是否已存在于哈希表中，若存在则返回对应索引，时间复杂度为O(n)。2.Python实现有效括号判断：pythonclassSolution:defisValid(self,s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用栈结构，遍历字符串，对于每个右括号检查栈顶元素是否为对应的左括号，若不是则返回False，遍历结束后栈应为空。3.Java实现字符出现次数统计：javaimportjava.util.HashMap;publicclassSolution{publicHashMap<Character,Integer>countCharacters(Strings){HashMap<Character,Integer>countMap=newHashMap<>();for(charc:s.toCharArray()){countMap.put(c,countMap.getOrDefault(c,0)+1);}returncountMap;}}解析：使用HashMap存储字符及其出现次数，遍历字符串时更新HashMap中的计数。二、数据结构与算法1.快速排序原理与优化：原理：选择一个基准元素，将数组分为两部分，左部分所有元素小于基准，右部分所有元素大于基准，然后递归对左右部分进行排序。时间复杂度：平均O(nlogn)，最坏O(n^2)。空间复杂度：O(logn)。优化：选择基准时可以随机选择，或使用“三数取中”法（取首、中、尾三数的中值作为基准）。2.找出第三大的数：javapublicintthirdMax(int[]nums){Longmax1=Long.MIN_VALUE,max2=Long.MIN_VALUE,max3=Long.MIN_VALUE;for(intnum:nums){if(num>max1){max3=max2;max2=max1;max1=num;}elseif(num>max2&&num!=max1){max3=max2;max2=num;}elseif(num>max3&&num!=max2&&num!=max1){max3=num;}}returnmax3!=Long.MIN_VALUE?max3:max1;}解析：维护三个变量记录前三大的数，遍历数组时更新这三个变量。3.二叉树中序遍历：java//递归方式publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<>();inorderHelper(root,result);returnresult;}privatevoidinorderHelper(TreeNodenode,List<Integer>result){if(node==null)return;inorderHelper(node.left,result);result.add(node.val);inorderHelper(node.right,result);}//迭代方式publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<>();Stack<TreeNode>stack=newStack<>();TreeNodecurrent=root;while(current!=null||!stack.isEmpty()){while(current!=null){stack.push(current);current=current.left;}current=stack.pop();result.add(current.val);current=current.right;}returnresult;}4.动态规划解决背包问题：原理：定义dp[i][j]表示前i个物品在容量为j时的最大价值，状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i])。解析：通过动态规划表逐步计算最大价值，最终dp[n][W]即为答案。5.LRU缓存实现：javaclassLRUCache{privateintcapacity;privateLinkedHashMap<Integer,Integer>cache;publicLRUCache(intcapacity){this.capacity=capacity;cache=newLinkedHashMap<>(capacity,0.75f,true);}publicintget(intkey){if(!cache.containsKey(key))return-1;returncache.get(key);}publicvoidput(intkey,intvalue){if(cache.containsKey(key)){cache.put(key,value);}else{if(cache.size()==capacity){cache.remove(cache.keySet().iterator().next());}cache.put(key,value);}}}三、操作系统与计算机网络1.进程与线程：区别：进程是资源分配的基本单位，线程是CPU调度的基本单位，进程有独立的内存空间，线程共享进程内存。竞态条件：多个线程同时访问共享资源时，执行结果依赖于线程的执行顺序，可能导致错误。使用互斥锁（mutex）可以保护共享资源，确保同一时间只有一个线程可以访问。javaReentrantLocklock=newReentrantLock();lock.lock();//访问共享资源lock.unlock();2.TCP三次握手与四次挥手：三次握手：客户端发送SYN，服务器回复SYN-ACK，客户端发送ACK，建立连接。四次挥手：客户端发送FIN，服务器回复ACK，服务器发送FIN，客户端回复ACK，关闭连接。原因：三次握手需要确认双方的发送和接收能力，四次挥手需要确保双方都完成数据传输。3.HTTP与HTTPS：区别：HTTP是明文传输，HTTPS通过SSL/TLS加密传输。HTTPS原理：客户端发起请求，服务器返回SSL/TLS证书，客户端验证证书，双方协商加密算法，建立加密通道。优化措施：使用HTTP/2、启用HSTS、使用CDN、优化证书有效期。4.DNS解析：过程：客户端向DNS服务器发送查询请求，DNS服务器逐级查询，最终返回IP地址。缓存重要性：减少查询延迟，提高解析效率。诊断命令：bashnslookupdig四、数据库与SQL1.员工工资高于部门平均工资：sqlSELECTe.id,FROMEmployeeeWHEREe.salary>(SELECTAVG(salary)FROMEmployeeWHEREdepartment_id=e.department_id)2.每种产品的总销售额：sqlSELECT,SUM(o.quantityo.price)AStotal_salesFROMOrderoJOINProductpONduct_id=p.idGROUPBY3.事务与ACID特性：事务：原子性（不可分割）、一致性（执行结果需符合业务规则）、隔离性（并发执行结果与串行执行相同）、持久性（一旦提交不可回滚）。保证原子性：使用数据库事务管理机制（如ACID）。保证一致性：设计数据库约束（如主键、外键、唯一约束）。五、系统设计1.微博系统设计：数据结构：-User(id,username,password,email)-Post(id,user_id,