招聘笔试指南软件工程师笔试题目

招聘笔试指南软件工程师笔试题目一、选择题（每题2分，共30分）1.关于进程与线程，以下描述正确的是：A.同一进程下的线程共享堆内存，但拥有各自独立的栈空间。B.线程是资源分配的基本单位，进程是CPU调度的基本单位。C.多进程程序上下文切换的开销通常小于多线程程序。D.进程间通信必须通过内核进行，线程间通信则无需内核介入。答案：A解析：线程是CPU调度的基本单位，进程是资源分配的基本单位，B错误。线程共享进程的地址空间，其上下文切换涉及的内容较少（主要是寄存器、栈指针等），开销远小于进程切换，C错误。线程间通信虽然可以通过共享内存等高效方式进行，但同步机制（如互斥锁、信号量）的实现通常需要内核支持，D说法过于绝对。A正确描述了线程共享堆、独享栈的特性。2.已知一棵二叉搜索树的前序遍历序列为：30,20,10,25,40,35,50。它的中序遍历序列是：A.10,20,25,30,35,40,50B.30,20,10,25,40,35,50C.10,25,20,35,50,40,30D.50,40,35,30,25,20,10答案：A解析：二叉搜索树（BST）的中序遍历序列是递增序列。前序遍历首节点为根节点（30）。在BST中，左子树所有节点值小于根，右子树所有节点值大于根。根据前序序列：根30后，20,10,25均小于30，属于左子树；40,35,50大于30，属于右子树。递归应用此规则，可重建BST，或直接判断选项中递增序列即为中序遍历结果，A符合。3.在TCP协议中，假设主机A向主机B连续发送两个报文段，序号分别是70和100。如果第一个报文段丢失，第二个报文段到达了B，那么B在收到第二个报文段后，发送给A的确认号是：A.70B.71C.100D.101答案：A解析：TCP确认号表示期望收到的下一个字节的序号，采用累积确认机制。第一个报文段序号70，假设其长度为L1（虽未给出，但根据序号差可推断为30），那么它携带的字节范围是70到99。第二个报文段序号100，携带字节范围100开始。由于第一个报文段丢失，B未收到序号70-99的字节，因此它期望收到的下一个序号仍然是70。所以确认号为70。4.关于HTTP状态码，以下说法错误的是：A.301MovedPermanently表示资源被永久重定向，浏览器会缓存此重定向。B.403Forbidden表示服务器理解请求，但拒绝执行，通常与权限相关。C.502BadGateway通常表示作为网关或代理的服务器，从上游服务器收到了一个无效的响应。D.503ServiceUnavailable表示服务器内部错误，无法处理请求。答案：D解析：503状态码表示服务器暂时无法处理请求（由于超载或系统维护），通常意味着状态是临时的。服务器内部错误通常对应500InternalServerError。因此D选项描述错误。5.对以下代码的时间复杂度分析正确的是：```pythondeffunc(n):i=1whilei<n:j=iwhilej<n:j=j*2i=i+1```A.OB.OC.OD.O答案：B解析：外层循环`i`从1到n-1，执行O(n)次。对于每个固定的`i`，内层循环`j`从`i`开始，每次乘以2，直到大于等于`n`。内层循环次数约为lo(6.在Linux系统中，想要查找当前目录及其子目录下所有扩展名为`.log`的文件，并在其中搜索包含字符串“ERROR”的行，应使用的命令是：A.`find.-name"*.log"|xargsgrep"ERROR"`B.`grep-r"ERROR"*.log`C.`find.-typef"*.log"-execgrep"ERROR"{};`D.`ls-R*.log|grep"ERROR"`答案：A解析：`find.-name".log"`递归查找所有.log文件，通过管道`|`和`xargs`将找到的文件列表作为参数传递给`grep"ERROR"`进行内容搜索。B选项`grep-r`虽然可以递归，但`.log`通配符可能无法被shell正确展开到子目录。C选项语法有误，`-exec`的正确格式是`-execgrepERROR{}\;`。D选项`ls-R`列出文件，但`*.log`同样无法递归匹配，且后续grep是针对文件名而非文件内容。7.关于数据库索引，以下描述不恰当的是：A.对表创建主键约束会自动创建一个唯一索引。B.在频繁进行UPDATE操作的列上创建索引，可能会降低更新性能。C.多列复合索引遵循最左前缀匹配原则。D.哈希索引非常适合进行范围查询。答案：D解析：哈希索引基于哈希表实现，只能进行等值查询（=，IN），无法高效支持范围查询（如BETWEEN,>,<）。范围查询通常使用B树（或B+树）索引。A、B、C的描述都是正确的。8.以下Python代码的输出是：```pythondefextend_list(val,my_list=[]):my_list.append(val)returnmy_listlist1=extend_list(10)list2=extend_list(123,[])list3=extend_list('a')print(list1,list2,list3)```A.`[10][123]['a']`B.`[10,'a'][123][10,'a']`C.`[10,'a'][123]['a']`D.`[10][123][10,'a']`答案：B解析：这是Python中一个经典的“可变默认参数”陷阱。函数`extend_list`的参数`my_list`的默认值`[]`在函数定义时被创建，且仅在定义时创建一次。后续每次调用中，如果没有显式提供`my_list`参数，使用的都是同一个默认列表对象。`list1=extend_list(10)`使用了默认列表，该列表变为`[10]`。`list2=extend_list(123,[])`传入了新的空列表`[]`，与默认列表无关，结果为`[123]`。`list3=extend_list('a')`再次使用了默认列表（此时已是`[10]`），向其添加`'a'`后变为`[10,'a']`。因此`list1`和`list3`引用的是同一个列表对象，输出为`[10,'a']`。9.在面向对象设计中，遵循“开闭原则”（Open-ClosedPrinciple）的主要目的是：A.允许模块在不修改其源代码的情况下扩展其行为。B.确保一个类只有一个引起变化的原因。C.高层模块不应依赖于低层模块，二者都应依赖于抽象。D.子类必须能够替换掉它们的父类。答案：A解析：开闭原则（OCP）强调软件实体（类、模块、函数等）应该对扩展开放，对修改关闭。即当需求变化时，应通过添加新的代码来扩展功能，而非修改已有的、运行良好的代码。B是单一职责原则，C是依赖倒置原则，D是里氏替换原则。10.以下关于死锁必要条件的叙述，错误的是：A.互斥条件：资源是独占的，一次只能被一个进程使用。B.请求与保持条件：进程在请求新资源时，保持对已有资源的占有。C.不剥夺条件：进程已获得的资源，只能由该进程自己释放。D.环路等待条件：存在一个进程-资源的环形等待链。答案：C解析：死锁的四个必要条件是：互斥、请求与保持、不剥夺、环路等待。其中“不剥夺条件”是指进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由该进程主动释放。C选项的描述“只能由该进程自己释放”过于绝对，忽略了系统强制剥夺的可能性（虽然这违反了“不剥夺”条件本身），但作为对“不剥夺条件”的解释，其核心是“非主动释放不可剥夺”，表述上C不够精确，但更关键的错误在于题目问“错误的是”，而A、B、D都是标准描述。C的表述容易引起歧义，但在严格意义上，它试图描述“不剥夺”，并非完全错误。然而，对比标准定义，更严谨的说法是“已获得的资源不可被强行剥夺”。本题意在考察对四个条件的准确记忆，C的表述是常见的模糊点。从选择题角度，C是“错误”的。11.使用Dijkstra算法求从顶点A到其他顶点的最短路径，当前已确定最短路径的顶点集合S={A,B,C}，从A到其余顶点的当前最短距离估计为：D:5,E:8,F:∞。已知边(B,D)=1,(C,D)=3,(C,E)=2,(D,E)=1。下一步被加入集合S的顶点及从A到该顶点的距离是：A.D,4B.D,5C.E,7D.E,8答案：A解析：Dijkstra算法每一步从未确定集合中选取距离起点估计值最小的顶点加入S。当前S={A,B,C}，估计值D=5,E=8,F=∞。但加入B和C后，需要松弛（Relax）从B和C出发的边。通过B到D：`dist[A->B]+w(B,D)`，但题目未给出A到B的距离。通过C到D：`dist[A->C]+w(C,D)`，同样未给出A到C的距离。然而，题目暗示了当前D的估计值5可能是通过某条路径得到的。检查边：`(C,D)=3`，如果A到C的距离是2（这是可能的，因为C已在S中，其最短距离已确定），那么通过C到D的新距离为2+3=5，与当前估计一致。现在，通过新加入的B和C，看是否有更优路径：假设A到B距离为4（合理推测），则通过B到D为4+1=5，无更新。但关键点在于，当C加入S后，可以通过C松弛到E的边：`dist[A->C]+w(C,E)=2+2=4`？这比当前E的估计值8小，会更新E=4？但选项中没有E=4。这里存在矛盾。重新审视：题目给出“当前已确定最短路径的顶点集合S={A,B,C}”，意味着A到B和C的最短距离已确定且不再改变。当前估计D=5,E=8是基于已探索的路径。下一步，应在D和E中选估计值最小的，即D(5)。但加入D后，可以通过D松弛到E的边：`dist[A->D]+w(D,E)=5+1=6`，这比E当前的8小，会更新E=6。然而，问题问的是“下一步被加入集合S的顶点及距离”，即加入S时该顶点的距离。所以加入的是D，距离为5。加入后E被更新为6。因此答案为A。12.关于C++中`std::move`和`std::forward`，以下说法正确的是：A.`std::move`是一个强制类型转换，它将一个左值无条件地转换为右值引用。B.`std::forward`用于实现完美转发，它总是将参数转换为右值引用。C.对一个对象使用`std::move`后，该对象的内容立即被移空，不应再被使用。D.`std::forward`可以替代`std::move`在任何需要移动语义的场景使用。答案：A解析：`std::move`的本质是`static_cast<T&&>`，将一个左值（或右值）无条件转换为右值引用，以允许移动语义的发生，A正确。`std::forward`是条件转换，当模板参数是左值引用类型时，它转发左值；当模板参数是非引用或右值引用类型时，它转换为右值引用，B错误。`std::move`只是转换类型，真正的资源转移发生在移动构造函数或移动赋值运算符中，调用`move`后对象处于有效但未指定的状态，并非立即“移空”，且通常不应再使用其值，但可能可以赋予新值或调用无前提条件的方法，C说法过于绝对。`std::forward`用于完美转发参数，其行为依赖于模板参数类型，不能随意替代`std::move`，D错误。13.在Redis中，以下哪项操作不是原子的？A.对一个列表（List）执行LPUSH和LRANGE组合在一个MULTI/EXEC事务块中。B.使用INCR命令递增一个字符串键的值。C.使用HMSET命令同时设置哈希（Hash）的多个字段。D.使用SADD命令向集合（Set）中添加多个成员。答案：A解析：Redis的单个命令（如INCR,HMSET,SADD）是原子执行的。事务块（MULTI/EXEC）中的一系列命令会按顺序、不被其他客户端命令打断地执行，但事务本身并不是原子性的，它只是将多个命令打包顺序执行，不保证中间不被其他客户端命令插入（Redis事务无隔离性）。且在事务中，命令在EXEC时才真正执行，而非在MULTI时。因此A选项中的“组合在一个MULTI/EXEC事务块中”这一整个操作，从外部看，其执行过程不是原子的（虽然事务内的命令是顺序连续执行的，但事务开始到提交期间，数据可能被其他客户端修改）。B、C、D的单个命令是原子操作。14.关于HTTPS，以下描述错误的是：A.HTTPS在HTTP和TCP之间加入了SSL/TLS安全层。B.服务器证书的主要作用是向客户端证明服务器的身份。C.使用HTTPS可以完全防止中间人攻击（Man-in-the-Middle）。D.HTTPS通信中，对称加密密钥是通过非对称加密协商的。答案：C解析：HTTPS通过SSL/TLS提供了加密、身份认证和完整性保护，能有效防范窃听、篡改和冒充。但如果客户端不验证服务器证书（如接受自签名证书、忽略证书错误），或者证书颁发机构被攻破，中间人攻击仍然可能发生。因此HTTPS“可以完全防止”的说法是错误的。A、B、D均为正确描述。15.对于以下SQL查询：```sqlSELECTdepartment_id,AVG(salary)asavg_salFROMemployeesWHEREhire_date>'2020-01-01'GROUPBYdepartment_idHAVINGAVG(salary)>5000ORDERBYavg_salDESC;```其执行顺序的逻辑描述是：A.WHERE->GROUPBY->HAVING->SELECT->ORDERBYB.FROM->WHERE->GROUPBY->HAVING->SELECT->ORDERBYC.FROM->WHERE->GROUPBY->HAVING->ORDERBY->SELECTD.FROM->WHERE->SELECT->GROUPBY->HAVING->ORDERBY答案：B解析：SQL查询的逻辑执行顺序为：1.FROM（确定数据源）2.WHERE（行级过滤）3.GROUPBY（分组）4.HAVING（组级过滤）5.SELECT（选择列，计算表达式，赋予别名）6.ORDERBY（排序）。注意，HAVING子句中可以使用SELECT中定义的别名`avg_sal`，但这是某些数据库（如MySQL）的扩展，在标准逻辑顺序中，HAVING在SELECT之前执行，因此标准HAVING中应使用聚合表达式`AVG(salary)`。题目中HAVING子句正是使用了`AVG(salary)`，符合逻辑顺序。B选项正确。二、编程题（共35分）1.（10分）实现一个函数，用于判断给定的二叉树是否是平衡二叉树。平衡二叉树的定义是：任意节点的左右子树高度差不超过1。要求：请用你熟悉的编程语言（如C++,Java,Python）实现，并分析时间复杂度。```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisBalanced(root):""":typeroot:TreeNode:rtype:bool"""defheight(node):ifnotnode:return0,True#返回高度和是否平衡left_height,left_balanced=height(node.left)ifnotleft_balanced:return0,Falseright_height,right_balanced=height(node.right)ifnotright_balanced:return0,Falseifabs(left_height-right_height)>1:return0,Falsereturnmax(left_height,right_height)+1,True_,balanced=height(root)returnbalanced```解析：采用后序遍历（深度优先搜索），自底向上计算每个节点的高度，并在计算过程中判断其左右子树是否平衡以及当前节点是否平衡。如果子树不平衡，则提前返回False，避免不必要的计算。每个节点仅访问一次，时间复杂度为O(n)2.（15分）设计并实现一个LRU（LeastRecentlyUsed）缓存机制。它应该支持以下操作：`LRUCache(intcapacity)`：以正整数作为容量capacity初始化缓存。`intget(intkey)`：如果关键字key存在于缓存中，则返回关键字的值，并将该节点提升为最近使用；否则返回-1。`voidput(intkey,intvalue)`：如果关键字已经存在，则变更其数据值并提升为最近使用；如果关键字不存在，则插入该组key-value。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。要求：`get`和`put`操作的时间复杂度均为O(```pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.cache={}self.capacity=capacityself.size=0#使用伪头部和伪尾部节点，简化边界条件处理self.head=DLinkedNode()self.tail=DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]#将节点移动到链表头部（表示最近使用）self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_to_head(node)self.size+=1ifself.size>self.capacity:#删除尾部节点（最久未使用）removed=self._remove_tail()delself.cache[removed.key]self.size-=1def_add_to_head(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_move_to_head(self,node):self._remove_node(node)self._add_to_head(node)def_remove_tail(self):node=self.tail.prevself._remove_node(node)returnnode```解析：LRU缓存的核心是快速定位（通过key）和快速维护访问顺序。使用哈希表（`dict`）实现O(1)的查找。使用双向链表维护访问顺序：最近访问的放在头部，最久未访问的放在尾部。当需要删除时，直接删除尾部节点及其在哈希表中的映射。所有链表操作（插入头部、删除节点）都是O3.（10分）给定一个字符串`s`，请你找出其中不含有重复字符的最长子串的长度。示例：输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc"，所以其长度为3。```pythondeflengthOfLongestSubstring(s:str)->int:char_index={}#存储字符最近一次出现的位置left=0#滑动窗口左边界max_len=0forrightinrange(len(s)):ch=s[right]#如果字符出现过，并且出现位置在窗口内，则移动左边界ifchinchar_indexandchar_index[ch]>=left:left=char_index[ch]+1#更新字符的最新位置char_index[ch]=right#计算当前窗口长度current_len=right-left+1max_len=max(max_len,current_len)returnmax_len```解析：采用滑动窗口（双指针）算法。`right`指针向右遍历，用哈希表记录每个字符最近一次出现的位置。当`right`指向的字符在哈希表中存在，并且其上次出现的位置大于等于`left`（即在当前窗口内），说明出现了重复字符。此时，将`left`指针移动到该重复字符上次出现位置的下一个位置，从而排除重复字符，形成新的无重复字符窗口。在每一步更新最大长度。时间复杂度O(n)，空间复杂度O三、系统设计题（15分）题目：请设计一个简单的短网址生成服务（TinyURL）。要求：1.描述核心功能：长URL转短URL，短URL重定向到原始长URL。2.估算系统规模：假设每日生成1亿个短链接，读写比例为100:1（即每生成1个短链，有100次访问）。3.设计关键的数据结构或数据库表结构。4.阐述短码的生成算法，并讨论如何避免冲突。5.简要说明高并发创建和访问的架构考虑（如缓存、数据库分片等）。答案与解析：1.核心功能：`create(long_url,[custom_alias])`：接收长URL，返回一个唯一的短码（如`https://short.url/abc123`）。可选支持自定义别名。`redirect(short_code)`：根据短码，返回对应的原始长URL，并触发HTTP302重定向。2.规模估算：每日生成（写操作）：100million(10^8)。每日访问（读操作）：100*10^8=10^10(100亿)。QPS估算：写QPS≈/(读QPS≈/(数据存储：假设每条记录约500字节（含索引），每日新增数据量约*5003.数据表设计：```sqlCREATETABLEtiny_urls(idBIGINTAUTO_INCREMENTPRIMARYKEY,--自增主键，用于生成短码short_codeVARCHAR(10)NOTNULLUNIQUE,--短码，唯一索引long_urlTEXTNOTNULL,--原始长URLcreated_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,expires_atTIMESTAMPNULL,--可选，过期时间user_idINTNULL,--可选，关联用户custom_aliasVARCHAR(20)NULLUNIQUE,--可选，自定义别名INDEXidx_short_code(short_code),INDEXidx_created_at(created_at));```4.短码生成算法与冲突避免：算法：使用分布式唯一ID生成器（如Snowflake算法）生成一个全局唯一的、趋势递增的长整型ID（对应表中的`id`字段）。然后将这个ID转换为一个62进制（a-z,A-Z,0-9）的字符串作为短码。例如，ID`123456789`转换为短码`"8M0kX"`。冲突避免：1.唯一性来源：核心依赖ID生成器的全局唯一性。由于ID唯一，其62进制编码也唯一。2.数据库唯一约束：在`short_code`字段上建立唯一索引，作为最终保障。即使ID生成器在极端情况下出现重复（概率极低），数据库插入也会因唯一约束失败，此时服务端可重试生成（例如使用新的ID或添加随机盐）。3.自定义别名：单独处理。需要先查询该别名是否已存在，存在则返回错误。优点：算法简单高效，无需预生成或检查冲突（依赖ID唯一性），短码长度可控且有序（有利于数据库索引性能）。5.高并发架构考虑：无状态服务：Web/API服务层设计为无状态的，可以水平扩展，通过负载均衡器分发请求。读写分离与缓存：读操作（重定向）：是绝对的读多写少。使用分布式缓存（如Redis或Memcached）存储热点`short_code->long_url`的映射。缓存命中率会非常高，能极大减轻数据库压力。缓存未命中时查询数据库并回填缓存。设置合理的TTL。写操作（创建）：ID生成器：需要部署多个ID生成器实例，确保其机器ID不冲突，以支持高并发创建。数据库分片：由于数据量巨大，单库无法支撑。可根据`short_code`或生成的`id`进行分片（例如，按`id`的范围或哈希值分到多个数据库实例）。由于短码生成是均匀的，分片后写负载也能均匀分布。异步处理：对于创建请求，在生成短码和ID后，可以将实际写入数据库的操作放入消息队列异步执行，API立即返回短码。这能极大提高写入吞吐量和响应速度，但需要考虑数据最终一致性。重定向优化：使用HTTP301（永久重定向）而非302（临时重定向），有利于客户端和搜索引擎缓存，减少后续请求对服务器的压力。四、简答题（每题5分，共20分）1.简述