百度持续交付项目组面试题

### 百度持续交付项目组面试题解析 #### 计算机基础 ##### 数据结构、算法 **代码实现快速排序** 快速排序是一种高效的排序算法，采用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序的关键在于选择合适的基准值进行分区。 **示例代码**： ```java public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (arr == null || arr.length == 0) return; if (low >= high) return; // Partitioning index int index = partition(arr, low, high); quickSort(arr, low, index - 1); quickSort(arr, index + 1, high); } private static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = (low - 1); // Index of smaller element for (int j = low; j < high; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } } ``` **输入n个整数，输出其中最小的k个** 这个问题可以通过构建一个最大堆来解决。首先将前k个元素放入堆中，然后对于剩余的每个元素，如果比堆顶元素小，则替换堆顶元素并调整堆。最后堆中剩下的就是最小的k个数。 **示例代码**： ```java import java.util.PriorityQueue; public class TopKElements { public static int[] smallestK(int[] nums, int k) { PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); for (int num : nums) { if (maxHeap.size() < k) { maxHeap.offer(num); } else if (num < maxHeap.peek()) { maxHeap.poll(); maxHeap.offer(num); } } int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = maxHeap.poll(); } return result; } } ``` **最长字符串** 这个问题可以通过遍历数组，用一个变量来跟踪当前最长字符串的长度，并更新最长字符串的引用。 **示例代码**： ```java public class LongestString { public static String findLongest(String[] arr) { if (arr == null || arr.length == 0) return ""; String longest = arr[0]; for (String str : arr) { if (str.length() > longest.length()) { longest = str; } } return longest; } } ``` #### 网络 ##### 标准的OSI参考模型与TCP/IP参考模型 **OSI参考模型**由国际标准化组织（ISO）制定，分为七层：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。 - **物理层**：负责传输原始比特流。 - **数据链路层**：负责帧的封装和解封装。 - **网络层**：负责IP寻址和路由选择。 - **传输层**：负责端到端的数据传输。 - **会话层**：管理会话建立和断开。 - **表示层**：负责数据格式转换。 - **应用层**：提供用户接口服务。 **TCP/IP参考模型**分为四层：网络接口层、网际层、传输层和应用层。 - **网络接口层**：对应OSI的物理层和数据链路层。 - **网际层**：对应OSI的网络层。 - **传输层**：同OSI的传输层。 - **应用层**：包含OSI的应用层、表示层和会话层。 ##### “三次握手”与“四次挥手” **三次握手**用于建立TCP连接： 1. 客户端发送SYN包(syn=j)给服务器，并进入SYN_SEND状态，等待服务器确认； 2. 服务器收到SYN后确认客户的SYN（ack=j+1），同时自己也发送一个SYN包（syn=k），即SYN+ACK包，此时服务器进入SYN_RECV状态； 3. 客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。 **四次挥手**用于关闭TCP连接： 1. 主动关闭方发送一个FIN，用来关闭主动方到被动关闭方的数据传送，也就是关闭主动方的TCP发送器。 2. 被动关闭方接收FIN后，发送一个ACK给对方，并且进入到CLOSE_WAIT状态。 3. 被动关闭方发送一个FIN，用来关闭被动方到主动方的数据传送，也就是关闭被动方的TCP发送器。 4. 主动关闭方接收FIN后，发送一个ACK给对方，确认序号为收到序号加1，此时主动方进入TIME_WAIT状态。需要经过2MSL后主动关闭方才会回到CLOSED状态。 #### 设计 ##### 网站搜索 设计网站搜索系统时，需要考虑以下几点： - **索引构建**：对网页进行抓取、解析和索引化。 - **查询处理**：处理用户的查询请求，通过索引查找匹配的网页。 - **排名算法**：根据相关性等指标对搜索结果进行排序。 - **缓存机制**：使用缓存来提高响应速度和减少数据库负担。 ##### 分布式缓存系统的设计 为了保证数据分布均匀，可以采用一致性哈希算法来分配数据。一致性哈希可以确保当增加或删除节点时，只需要重新哈希一小部分数据，而不是整个数据集。 **一致性哈希步骤**： 1. **初始化**：将所有节点映射到一个环形空间上。 2. **添加/删除节点**：新加入或移除的节点只需重新计算与该节点相关的数据位置。 3. **数据分布**：使用哈希函数将数据映射到特定的节点上。 ##### Singleton设计模式 **静态内部类方式**实现Singleton模式： ```java public class Singleton { private Singleton() {} private static class SingletonHolder { private static final Singleton INSTANCE = new Singleton(); } public static Singleton getInstance() { return SingletonHolder.INSTANCE; } } ``` #### Java基础 ##### 线程的概念与实现 **线程**是操作系统能够进行运算调度的最小单位，它被包含在进程之中，是进程中的实际运作单位。一个进程可以有多个线程，各线程间共用相同的资源。 在Java中可以通过继承`Thread`类或实现`Runnable`接口的方式来创建线程。 **继承Thread类**： ```java class MyThread extends Thread { public void run() { System.out.println("Thread running"); } } public class Main { public static void main(String[] args) { MyThread thread = new MyThread(); thread.start(); // 启动线程 } } ``` **实现Runnable接口**： ```java class MyRunnable implements Runnable { public void run() { System.out.println("Thread running"); } } public class Main { public static void main(String[] args) { Thread thread = new Thread(new MyRunnable()); thread.start(); // 启动线程 } } ``` ##### Java中的线程同步机制 **synchronized关键字**用于实现线程同步，它可以修饰方法或者代码块。当一个线程访问某个对象的一个`synchronized`方法时，它就获得了该对象的锁，并执行该`synchronized`方法；其他线程若试图访问此对象的任何`synchronized`方法，都会被阻塞，直到第一个线程执行完该方法。 **ReentrantLock**是一个可重入的互斥锁，它具有与`synchronized`相同的锁定功能，但是更灵活。 **volatile关键字**用于标记变量的状态，当一个变量被声明为volatile时，任何对该变量的读写操作都直接发生在主存中，因此任何线程对该变量的修改都能被其他线程立即感知。 **线程安全**是指多个线程并发访问同一个资源时，不会出现数据不一致的情况。`Vector`类在多线程环境中是线程安全的，因为它在内部使用了`synchronized`关键字。 **竞态条件**指的是在多线程环境中，两个或多个线程同时访问并试图修改同一个共享资源时发生的情况。例如，两个线程同时对一个变量进行自增操作，可能会导致最终的结果比预期的小。 **线程间通信**可以通过`wait()`、`notify()`和`notifyAll()`方法来实现。`wait()`方法会使线程放弃对象锁，进入等待此对象的等待锁定池；`notify()`方法唤醒等待池中的一个线程；`notifyAll()`方法唤醒等待池中的所有线程。 **ThreadLocal**类提供了线程局部变量，这些变量在线程之间是独立的，每个线程都有自己的副本，因此不会发生线程安全问题。 #### 数据库 ##### 关系型数据库 **MySQL查询联接方式**包括内联接（INNER JOIN）、左联接（LEFT JOIN）、右联接（RIGHT JOIN）和全外联接（FULL OUTER JOIN）。 - **INNER JOIN**：返回两个表中联接字段相等的行。 - **LEFT JOIN**：返回左表的所有行和右表中匹配的行，如果右表中没有匹配的行，则结果为NULL。 - **RIGHT JOIN**：与LEFT JOIN相反。 - **FULL OUTER JOIN**：返回左右表中所有匹配和不匹配的行。 **数据库事务的四个基本要素**：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。 - **原子性**：事务中的所有操作要么全部成功，要么全部失败。 - **一致性**：事务执行前后，数据必须保持一致状态。 - **隔离性**：事务之间相互独立，互不影响。 - **持久性**：一旦事务提交，其对数据库的影响是永久的。 **关系数据库的范式**主要包括第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、第四范式（4NF）和第五范式（5NF或BCNF）。 - **第一范式**：数据表中的每一列都是不可分割的基本数据项。 - **第二范式**：在满足第一范式的基础上，非码属性完全依赖于候选码。 - **第三范式**：在满足第二范式的前提下，非码属性不传递依赖于候选码。 - **第四范式**：非平凡多值依赖的决定因素是候选码。 - **第五范式**：不存在非平凡的连接依赖。 **MySQL常用的数据库引擎**有InnoDB、MyISAM、MEMORY等。其中InnoDB支持事务，而MyISAM不支持。 **MySQL事务隔离级别**包括读未提交（READ UNCOMMITTED）、读已提交（READ COMMITTED）、可重复读（REPEATABLE READ）和串行化（SERIALIZABLE）。 - **读未提交**：允许读取尚未提交的数据。 - **读已提交**：只能读取已经提交的数据。 - **可重复读**：在一个事务中多次读取同一数据时，结果是一致的。 - **串行化**：最严格的隔离级别，事务串行执行，性能最低。 #### 框架 ##### Spring框架 **Spring MVC工作机制**主要涉及以下几个组件：DispatcherServlet、HandlerMapping、ViewResolver、ModelAndView。 - **DispatcherServlet**：前端控制器，处理HTTP请求并将请求分发给相应的控制器。 - **HandlerMapping**：处理器映射器，负责寻找处理请求的控制器。 - **ViewResolver**：视图解析器，负责将逻辑视图名称解析成实际的视图对象。 - **ModelAndView**：模型和视图，控制器返回的对象，包含了视图名称和模型数据。 **Spring框架的核心模块**包括核心容器、数据访问/集成、Web、AOP、工具、测试等。 - **核心容器**：BeanFactory和ApplicationContext。 - **数据访问/集成**：提供数据访问和集成的支持。 - **Web**：提供Web开发的支持。 - **AOP**：面向切面编程的支持。 - **工具**：提供工具类支持。 - **测试**：提供单元测试和集成测试的支持。 **使用Spring框架的优点**包括松耦合、易于单元测试、统一的事务管理、AOP支持、强大的IoC容器、MVC支持等。 **Spring框架配置事务**的方式有两种：声明式事务管理和编程式事务管理。声明式事务管理通过XML或注解来实现，编程式事务管理则通过编程的方式来控制事务的边界。 **依赖注入（DI）与控制反转（IoC）**是Spring框架的核心概念。依赖注入指的是由容器动态注入对象所依赖的对象；控制反转指的是将原本在程序中控制流程的调用细节转移到外部容器中，由容器来控制对象的生命周期。 ##### Hibernate **Hibernate的检索策略**包括立即加载（Eager）和延迟加载（Lazy）。立即加载会在加载父对象时一同加载关联的对象，而延迟加载则是在真正需要使用关联对象时才加载。 - **立即加载**：在加载父对象时同时加载子对象。 - **延迟加载**：只有在访问关联对象时才加载。 **SortedCollection和OrderedCollection的区别**主要在于排序方式。SortedCollection是基于比较器排序的集合，而OrderedCollection则是按插入顺序排序的集合。 **Hibernate的缓存机制**包括一级缓存和二级缓存。一级缓存是默认启用的，用于保存Session中获取的对象；二级缓存可以通过配置启用，用于跨Session缓存数据。 **Hibernate中的update()和saveOrUpdate()的区别**： - `update()`方法用于更新现有的对象。 - `saveOrUpdate()`方法根据传入对象的状态来决定是执行保存还是更新操作。 **session的load()和get()的区别**： - `load()`方法会在找不到对象时抛出异常。 - `get()`方法会在找不到对象时返回null。 **Hibernate中对象的三种状态**：瞬时态（Transient）、持久态（Persistent）和脱管态（Detached）。 - **瞬时态**：尚未与Session关联的对象。 - **持久态**：与Session关联并且在Session中持久化的对象。 - **脱管态**：与Session脱离关系的对象。 ##### Dubbo **Dubbo**是一个高性能、轻量级的开源服务框架，提供服务自动注册与发现、透明化的远程方法调用等功能。 **微服务的服务注册与发现**通常是通过服务注册中心来实现的。Dubbo通过Zookeeper等注册中心来实现服务的注册与发现。 ##### Spring Cloud **Spring Cloud**是一个基于Spring Boot的框架，用于构建云原生微服务架构。它提供了一系列工具和服务来简化分布式系统的开发，如服务发现、配置管理、熔断器、智能路由等。 #### 中间件 ##### Redis **Redis主键失效原理**：Redis提供了过期键的管理机制，当设置了键的过期时间后，Redis会在键过期时将其从内存中移除。Redis使用两种策略来处理过期键：定期删除和惰性删除。 - **定期删除**：每隔一段时间检查过期键并删除。 - **惰性删除**：在访问键时检查是否过期，过期则删除。 **如何保证Redis中的数据都是热点数据**可以通过以下几种方式实现： - **合理设置过期时间**：为每个键设置合理的过期时间，让不活跃的数据自动删除。 - **LRU淘汰策略**：当内存不足时，使用最近最少使用的淘汰策略来移除不活跃的数据。 - **监控和分析**：定期监控和分析数据访问情况，根据实际情况调整策略。 **Redis事务**提供了多个命令作为一个单元一起执行的功能。Redis事务不支持回滚，但可以确保命令的顺序执行。 **示例代码**： ```redis MULTI SET key1 value1 SET key2 value2 EXEC ``` ##### Solr **SolrCloud集群结构**是由多个SolrServer实例组成的集群，每个SolrServer实例运行在单独的JVM上，可以分布在不同的服务器上。SolrCloud支持数据复制和分片，可以实现高可用性和水平扩展。 **查询创建时间在2017年9月1日至今的数据**： ```solr q=createTime:[2017-09-01T00:00:00Z TO NOW] ``` **Solr与Elasticsearch的比较**： - **索引机制**：Solr使用倒排索引，Elasticsearch使用倒排索引和分词器。 - **可扩展性**：两者都支持水平扩展，但Elasticsearch在分布式方面更加成熟。 - **API支持**：Elasticsearch提供了RESTful API，而Solr同时支持XML和JSON。 - **社区支持**：Elasticsearch拥有更大的社区和更多的第三方插件。 ##### Zookeeper **Zookeeper如何保证事务的顺序一致性**：Zookeeper通过ZAB协议（Zookeeper Atomic Broadcast Protocol）来保证所有节点上数据的一致性和顺序性。每个提议都有一个全局唯一的zxid，确保所有更新按照顺序执行。 **ZK选举过程**： 1. **初始化阶段**：每个服务器启动后，进入LOOKING状态，等待接收其他服务器的消息。 2. **投票阶段**：服务器接收到消息后，如果消息中的zxid大于自己的zxid，则投票给该服务器；否则投票给自己。 3. **决策阶段**：当一个服务器收到超过半数服务器的票数时，成为领导者，其他服务器成为跟随者。 **ZooKeeper不适合做Queue的原因**： - **性能瓶颈**：ZooKeeper是为了解决分布式系统中协调问题而设计的，其设计初衷不是作为队列系统。 - **复杂性**：使用ZooKeeper实现队列需要复杂的逻辑来维护队列的顺序性，这增加了系统的复杂性。 - **非阻塞特性**：ZooKeeper的非阻塞特性使得其实现阻塞队列较为困难。 **客户端连接集群server的策略**： - **随机连接**：客户端随机选择一个server连接。 - **轮询连接**：客户端按照一定顺序轮流连接各个server。 - **负载均衡**：根据server的负载情况选择连接。 **一个客户端修改了某个节点的数据，其它客户端能够马上获取到这个最新数据**：ZooKeeper提供了一种叫做Watcher的通知机制，当一个客户端修改了某个节点的数据时，其他监听该节点变化的客户端会收到通知，从而能够及时获取到最新的数据。 #### 持续集成工具 ##### Jenkins **Jenkins**是一个开源的持续集成/持续交付工具，支持构建、测试和部署软件项目。它支持多种插件，可以方便地集成各种开发工具和服务。 Jenkins的主要功能包括： - **持续集成**：自动构建、测试代码。 - **持续交付**：自动化部署到不同环境。 - **可插拔架构**：支持大量插件，可以扩展功能。 - **多平台支持**：支持Windows、Linux和Mac OS等多种操作系统。 #### 总结 本文详细介绍了百度持续交付项目组面试题中的知识点，涵盖了计算机基础、网络、设计模式、Java基础、数据库、框架、中间件以及持续集成工具等方面的内容。通过对这些知识点的学习，可以帮助开发者更好地准备面试，掌握必要的技能，提升技术能力。