创新科技公司研发工程师面试指南及答案

2026年创新科技公司研发工程师面试指南及答案一、编程基础（共5题，每题10分，总分50分）题目1（10分）请用Python实现一个函数，该函数接收一个字符串参数，返回该字符串中所有唯一字符的列表。例如，输入"hello"，返回['h','e','l','o']。pythondefunique_chars(s):returnlist(set(s))答案解析：使用Python内置的set数据结构可以快速去除重复字符，然后将其转换回列表。这种方法时间复杂度为O(n)，空间复杂度也为O(n)。题目2（10分）请用C++实现一个函数，该函数对一个整数数组进行快速排序，并返回排序后的数组。要求不使用额外的存储空间。cppinclude<vector>usingnamespacestd;intpartition(vector<int>&arr,intlow,inthigh){intpivot=arr[high];inti=low-1;for(intj=low;j<high;j++){if(arr[j]<pivot){i++;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[high]);returni+1;}vector<int>quick_sort(vector<int>&arr,intlow,inthigh){if(low<high){intpi=partition(arr,low,high);quick_sort(arr,low,pi-1);quick_sort(arr,pi+1,high);}returnarr;}答案解析：快速排序的基本思想是分治法。选择一个基准元素，将数组分为两部分，使得左边的元素都小于基准，右边的元素都大于基准，然后递归地对左右两部分进行排序。题目3（10分）请用Java实现一个方法，计算一个链表的中间节点。如果链表有偶数个节点，则返回上半个部分的中间节点。javaclassListNode{intval;ListNodenext;ListNode(intx){val=x;}}publicListNodemiddleNode(ListNodehead){ListNodeslow=head,fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}returnslow;}答案解析：使用快慢指针法。慢指针每次移动一步，快指针每次移动两步。当快指针到达链表末尾时，慢指针正好位于中间位置。题目4（10分）请用JavaScript实现一个函数，该函数接收一个正整数n，返回一个包含所有小于等于n的素数的数组。javascriptfunctionsieveOfEratosthenes(n){constprimes=[];constisPrime=newArray(n+1).fill(true);isPrime[0]=isPrime[1]=false;for(leti=2;i<=n;i++){if(isPrime[i]){primes.push(i);for(letj=ii;j<=n;j+=i){isPrime[j]=false;}}}returnprimes;}答案解析：埃拉托斯特尼筛法是一种高效的找出所有小于等于n的素数的方法。首先假设所有小于等于n的数都是素数，然后从2开始，将每个素数的倍数标记为非素数。题目5（10分）请用Go语言实现一个函数，该函数接收一个整数数组，返回该数组的最长递增子序列的长度。gofunclengthOfLIS(nums[]int)int{iflen(nums)==0{return0}dp:=make([]int,len(nums))dp[0]=1maxLen:=1fori:=1;i<len(nums);i++{dp[i]=1forj:=0;j<i;j++{ifnums[i]>nums[j]{dp[i]=max(dp[i],dp[j]+1)}}maxLen=max(maxLen,dp[i])}returnmaxLen}funcmax(x,yint)int{ifx>y{returnx}returny}答案解析：动态规划方法。dp[i]表示以nums[i]结尾的最长递增子序列的长度。对于每个nums[i]，遍历它之前的所有元素，如果nums[i]>nums[j]，则dp[i]=max(dp[i],dp[j]+1)。二、数据结构与算法（共5题，每题10分，总分50分）题目6（10分）请解释什么是二叉搜索树(BST)，并给出一个递归方法判断一个二叉树是否是BST。pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisBST(root,left=float('-inf'),right=float('inf')):ifnotroot:returnTrueifnot(left<root.val<right):returnFalsereturnisBST(root.left,left,root.val)andisBST(root.right,root.val,right)答案解析：二叉搜索树是一种特殊的二叉树，满足对于任意节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。递归判断时，需要维护当前节点应该位于的值范围。题目7（10分）请实现一个LRU（最近最少使用）缓存，支持get和put操作。pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:self.cache[key]=valueself.cache.move_to_end(key)iflen(self.cache)>self.capacity:self.cache.popitem(last=False)答案解析：使用Python的OrderedDict实现LRU缓存。get操作将访问的元素移动到末尾表示最近使用过。put操作将新元素添加到末尾，如果超出容量则删除最早的元素。题目8（10分）请解释什么是动态规划，并给出一个使用动态规划解决0/1背包问题的示例。pythondefknapsack(weights,values,capacity):n=len(weights)dp=[[0](capacity+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,capacity+1):ifweights[i-1]<=w:dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])else:dp[i][w]=dp[i-1][w]returndp[n][capacity]答案解析：动态规划通过将问题分解为子问题并存储子问题的解来避免重复计算。0/1背包问题中，对于每个物品，我们决定是否放入背包，如果放入则当前重量加上该物品的值，如果不放入则保持当前值。题目9（10分）请解释什么是图，并给出一个使用深度优先搜索(DFS)遍历图的示例。pythondefdfs(graph,start,visited=None):ifvisitedisNone:visited=set()visited.add(start)print(start,end='')forneighboringraph[start]:ifneighbornotinvisited:dfs(graph,neighbor,visited)答案解析：图是由顶点集合和边集合组成的数据结构。深度优先搜索是一种遍历或搜索树或图的算法，它从根节点开始，尽可能深地探索每个分支。题目10（10分）请解释什么是贪心算法，并给出一个使用贪心算法解决活动选择问题的示例。pythondefactivitySelection(start,finish):n=len(start)activities=list(zip(start,finish))Sortactivitiesbyfinishtimeactivities.sort(key=lambdax:x[1])count=0last_finish=0fors,finactivities:ifs>=last_finish:count+=1last_finish=freturncount答案解析：贪心算法在每一步选择当前看起来最优的选项，希望这样能导致全局最优解。活动选择问题中，我们按结束时间排序活动，然后选择不重叠的活动。三、系统设计（共3题，每题20分，总分60分）题目11（20分）设计一个简单的微博系统，需要支持用户发布微博、关注用户、获取关注用户的最新微博。设计要点：1.用户可以发布最多140个字符的微博2.用户可以关注其他用户3.用户获取关注用户的最新10条微博4.系统需要考虑可扩展性和性能回答要点：-数据库设计：用户表、微博表、关注关系表-API设计：POST/publish、POST/follow、GET/timeline-技术选型：数据库（MySQL/PostgreSQL）、缓存（Redis）、消息队列（Kafka）答案解析：微博系统需要考虑的关键点：1.数据库设计：用户表存储用户信息，微博表存储微博内容，关注关系表存储用户之间的关注关系2.API设计：发布微博接口需要验证用户身份和内容长度，关注接口需要维护双向关注关系，获取时间线接口需要按时间倒序获取关注用户的微博3.技术选型：使用关系型数据库存储结构化数据，使用Redis缓存热点用户的时间线，使用消息队列处理高并发发布操作题目12（20分）设计一个短链接系统，需要支持将长链接转换为短链接，并能通过短链接访问原始长链接。设计要点：1.短链接需要保持一定的有效期2.系统需要支持高并发访问3.需要统计短链接的访问次数4.短链接应尽量短且唯一回答要点：-短链接生成算法：可以使用Base62编码-数据库设计：短链接表存储映射关系和统计信息-高并发处理：使用缓存和分布式架构-技术选型：数据库（Redis/PostgreSQL）、缓存（Memcached）、负载均衡答案解析：短链接系统设计要点：1.短链接生成：使用Base62编码（包含a-z、A-Z、0-9）将ID映射为短链接，确保短链接长度适中2.数据库设计：存储短链接与长链接的映射关系，以及访问统计和有效期信息3.高并发处理：使用Redis缓存热点短链接的映射关系，使用消息队列处理创建请求4.分布式架构：使用负载均衡分发请求，使用分布式缓存避免单点瓶颈题目13（20分）设计一个实时消息推送系统，需要支持多用户聊天和系统通知。设计要点：1.支持WebSocket或长轮询实现实时通信2.需要处理用户在线状态3.需要支持离线消息推送4.系统需要考虑可扩展性和容错性回答要点：-消息存储：使用消息队列存储待发送消息-用户状态管理：使用Redis存储用户在线状态-消息推送：使用WebSocket或长轮询实现实时推送-技术选型：消息队列（Kafka/RabbitMQ）、缓存（Redis）、实时通信（WebSocket/Socket.IO）答案解析：实时消息推送系统设计要点：1.消息存储：使用消息队列解耦消息生产者和消费者，保证消息不丢失2.用户状态管理：使用Redis存储用户在线状态和最后活跃时间，实现心跳检测3.消息推送：对于在线用户使用WebSocket实时推送，对于离线用户将消息存储在数据库或消息队列中4.可扩展性：使用微服务架构，将消息存储、状态管理和推送服务分离四、数据库（共3题，每题15分，总分45分）题目14（15分）请解释数据库索引的作用，并比较B树索引和哈希索引的优缺点。答案解析：数据库索引的作用：1.加快数据检索速度2.保证数据完整性3.支持数据库事务B树索引和哈希索引的比较：-B树索引：-优点：支持范围查询，平衡树结构保证查找效率-缺点：对于点查询性能不如哈希索引-哈希索引：-优点：点查询效率高-缺点：不支持范围查询，哈希冲突会影响性能题目15（15分）请解释什么是数据库事务，并说明事务的ACID特性。答案解析：数据库事务：-事务是一系列数据库操作，被视为单个逻辑工作单元-事务必须满足ACID特性ACID特性：-原子性（Atomicity）：事务中的所有操作要么全部完成，要么全部不做-一致性（Consistency）：事务必须使数据库从一个一致性状态转移到另一个一致性状态-隔离性（Isolation）：一个事务的执行不能被其他事务干扰-持久性（Durability）：一旦事务提交，其所做的更改将永久保存在数据库中题目16（15分）请设计一个数据库表结构，用于存储商品信息，并说明索引设计。sqlCREATETABLEproducts(idINTPRIMARYKEYAUTO_INCREMENT,nameVARCHAR(255)NOTNULL,categoryVARCHAR(100),priceDECIMAL(10,2)NOTNULL,stockINTDEFAULT0,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,updated_atTIMESTAMPDEFAULTCURRENT_TIMESTAMPONUPDATECURRENT_TIMESTAMP);CREATEINDEXidx_categoryONproducts(category);CREATEINDEXidx_priceONproducts(price);答案解析：商品表设计：-id：主键，唯一标识商品-name：商品名称，非空-category：商品分类-price：商品价格，非空-stock：库存数量-created_at：创建时间-updated_at：更新时间索引设计：-category索引：加速按分类查询商品-price索引：加速按价格查询商品-主键索引：自动创建，用于快速查找特定商品五、网络与系统（共3题，每题15分，总分45分）题目17（15分