(Java面試題分享)萬里長征-03-搜狐

萬里長征-03-搜狐

問題

1.LeetCode103 二叉樹的鋸齒形層序遍歷

103. 二叉樹的鋸齒形層序遍歷 - 力扣（LeetCode）

2.LeetCode5 最長回文子串

5. 最長回文子串 - 力扣（LeetCode）

3.Kafka為何那么快

GPT問答

Kafka為何那么快

Kafka 以其高性能和低延遲廣受歡迎，原因在于其設計中的幾個關鍵因素：

順序寫入磁盤：
- Kafka 將消息順序地寫入磁盤，這比隨機寫入快得多，因為順序寫入可以充分利用磁盤的帶寬。
零拷貝機制：
- Kafka 使用了零拷貝技術（Zero Copy），這使得消息在網絡傳輸過程中不需要被多次拷貝，從而提高了傳輸效率。零拷貝技術允許數據直接從磁盤傳輸到網絡緩沖區，而不需要在用戶態和內核態之間進行數據拷貝。
分區和并行處理：
- Kafka 將數據分片成多個分區（Partitions），每個分區可以分配給不同的消費者，從而實現并行處理。多個分區可以分布在不同的機器上，實現負載均衡和高吞吐量。
批量處理：
- Kafka 支持批量消息傳遞（Batch Processing），可以在一次網絡請求中發送或接收多條消息。這樣減少了網絡開銷，提高了吞吐量。
高效的存儲格式：
- Kafka 使用了一種高效的二進制消息格式。這種格式使得消息在寫入和讀取時都非常高效，減少了序列化和反序列化的開銷。
高效的索引機制：
- Kafka 使用稀疏索引和段文件（Segment Files），使得消息查找非常高效。每個段文件都有一個索引，消費者可以快速找到消息的位置。
內存映射文件：
- Kafka 使用內存映射文件（Memory-Mapped Files），使得磁盤上的數據可以被直接映射到內存中進行讀寫操作，從而提高了 I/O 性能。
異步復制：
- Kafka 的副本機制是異步復制的，主節點在寫入數據后不需要等待所有副本節點的確認，減少了寫入延遲。
高效的網絡協議：
- Kafka 使用了一種高效的二進制網絡協議（基于 TCP），減少了網絡通信的開銷。
簡化的消費者模型：
- Kafka 的消費者模型非常簡化，不需要中心化的協調服務來管理消費者狀態，消費者自己負責跟蹤讀取的偏移量（Offset），這減少了協調開銷。

這些設計決策共同作用，使得 Kafka 能夠實現高吞吐量、低延遲的消息處理能力，適用于大規模、高并發的數據流處理場景。

rabbitmq消息是順序寫入磁盤嗎

RabbitMQ 的消息存儲和處理機制與 Kafka 有一些顯著的不同。RabbitMQ 并不總是順序地將消息寫入磁盤，其消息存儲機制依賴于不同的持久性設置和隊列類型。以下是一些關鍵點：

持久性設置：
- 如果消息和隊列被標記為持久（durable），RabbitMQ 會將消息寫入磁盤以保證在服務器重啟后消息不會丟失。持久消息會在收到時立即被寫入磁盤。
- 非持久消息通常只保存在內存中，雖然在內存壓力大時也可能被寫入磁盤，但這不是默認行為。
內存和磁盤的使用：
- RabbitMQ 首先將消息保存在內存中，以提高消息的吞吐量和處理速度。
- 當內存使用達到一定閾值時，RabbitMQ 會將消息轉移到磁盤上，以防止內存溢出。這種情況下，消息寫入磁盤的順序可能會有所不同。
隊列類型：
- 不同類型的隊列有不同的消息存儲策略。例如，經典隊列（Classic Queue）和 Quorum Queue 在消息存儲和復制上有不同的實現方式。
- Quorum Queue 是基于 Raft 共識算法實現的，提供了更高的可靠性和一致性的消息存儲，但其性能和消息寫入順序可能會受到影響。
消息確認機制：
- RabbitMQ 支持多種消息確認機制（如消息確認、發布確認等），這些機制可以影響消息何時被寫入磁盤以及寫入的順序。

總的來說，RabbitMQ 不總是順序地將消息寫入磁盤。消息的寫入順序和時機受多種因素影響，包括消息和隊列的持久性設置、內存使用情況、隊列類型和消息確認機制等。

相比之下，Kafka 設計上的一個顯著特點是順序寫入磁盤，這使其在高吞吐量和低延遲的日志存儲和流處理場景中表現優異。而 RabbitMQ 作為一個強大的消息隊列系統，提供了豐富的功能和靈活性，但在消息持久化和存儲機制上與 Kafka 有著不同的設計和優化。

總結

順序寫可以最大的利用磁盤的帶寬
零拷貝允許磁盤直接到網絡緩沖區，不用經過多次copy，內核不用多次切換
批量處理機制

4.MySQL中B樹 B+樹區別

GPT問答

MySQL中B樹 B+樹區別

B樹（B-Tree）和 B+樹（B+ Tree）是兩種常見的樹形數據結構，用于數據庫和文件系統的索引結構。它們都有助于高效地存儲和檢索數據，但它們在實現和性能上有一些關鍵的區別。

B樹（B-Tree）

節點結構：
- B樹的每個節點可以包含多個鍵和子節點指針。
- 每個節點的鍵和子節點指針數量有一個上限和下限，具體取決于樹的階（degree）。
- 所有葉子節點不一定在同一層。
葉子節點：
- 葉子節點包含實際的數據記錄。
- 由于數據可以存在于所有節點（不僅僅是葉子節點），因此查找數據時可能在非葉子節點找到。
搜索效率：
- 查詢過程中，數據可能在任何層次的節點中找到，導致查詢路徑可能較短。

B+樹（B+ Tree）

節點結構：
- 內部節點（非葉子節點）只存儲鍵和子節點指針，不存儲實際數據。
- 葉子節點存儲所有的數據記錄。
- 所有葉子節點在同一層，并通過指針相互鏈接，形成一個鏈表結構。
葉子節點：
- 葉子節點包含所有的數據記錄和指向相鄰葉子節點的指針。
- 這種結構使得范圍查詢和順序訪問更加高效。
搜索效率：
- 數據記錄只存在于葉子節點，因此查找數據時必須到達葉子節點，但由于葉子節點在同一層，所以樹的高度較低，查找路徑相對穩定。

主要區別總結

數據存儲位置：
- B樹：數據存儲在所有節點中（包括內部節點和葉子節點）。
- B+樹：數據僅存儲在葉子節點中。
葉子節點的結構：
- B樹：葉子節點沒有特別的鏈接結構。
- B+樹：葉子節點通過鏈表結構相互鏈接，便于范圍查詢和順序訪問。
樹的高度：
- B樹：由于數據存儲在各層節點中，樹的高度可能會比 B+樹稍高。
- B+樹：所有數據都在葉子節點中，內部節點的高度較低，樹的高度更穩定。
查詢效率：
- B樹：數據可能在任何節點中找到，查詢路徑可能較短。
- B+樹：數據必須到葉子節點才找到，但由于葉子節點在同一層，查找路徑較穩定。

應用場景

B樹：適用于需要頻繁插入和刪除操作的場景，因為它不需要保持葉子節點的鏈表結構。
B+樹：適用于需要高效范圍查詢和順序訪問的場景，比如數據庫索引結構。

在 MySQL 中，InnoDB 存儲引擎使用 B+樹作為其默認索引結構，因為這種結構非常適合數據庫的范圍查詢和順序訪問。

給我用java類的方式，寫出B+樹的葉子結點結構和內部節點結構

假設每個節點可以存儲一個固定數量的鍵，并且每個葉子節點包含一個指向下一個葉子節點的指針。

B+ 樹葉子節點結構

public class BPlusTreeLeafNode<K extends Comparable<K>, V> {private static final int MAX_KEYS = 4; // 假設每個節點最多存儲4個鍵private K[] keys;private V[] values;private int keyCount;private BPlusTreeLeafNode<K, V> next;
}

B+ 樹內部節點結構

public class BPlusTreeInternalNode<K extends Comparable<K>> {private static final int MAX_KEYS = 4; // 假設每個節點最多存儲4個鍵private K[] keys;private Object[] children; // 可以是葉子節點或內部節點private int keyCount;
}

說明

葉子節點（BPlusTreeLeafNode）包含鍵和值的數組以及指向下一個葉子節點的指針。
內部節點（BPlusTreeInternalNode）包含鍵的數組和子節點指針的數組。
為了簡化實現，假設每個節點最多存儲4個鍵。
實際的插入和刪除邏輯需要處理節點分裂、合并等操作，這里省略了具體實現。

這些類提供了 B+ 樹節點的基本結構。在完整實現中，你需要實現插入、刪除、查找等操作，以及處理節點的分裂和合并。

總結

B+樹，主要就是去看葉子節點和非葉子節點的特性
葉子節點才有值，非葉子節點只是做導航用的
為了滿足范圍查詢，有個next相鄰指針的概念
查詢路徑穩定，不會有大波動

5.、Netty、BIO、NIO、AIO框架

GPT問答

給我介紹下Netty、BIO、NIO、AIO

Netty 是一個基于 Java 的高性能、異步事件驅動的網絡應用框架，主要用于開發高性能的網絡服務器和客戶端。Netty 提供了豐富的功能，如：

支持多種協議（如 HTTP、FTP、SMTP、WebSocket 等）。
高度可配置的線程模型。
內置的編解碼器，方便進行數據處理。
異步和事件驅動的編程模型，簡化了并發編程。

Netty 的核心是基于 NIO 的，提供了更高的抽象層，使開發更容易和高效。

BIO (Blocking I/O) 是 Java 傳統的 I/O 模型，基于流的阻塞式 I/O 操作。其特點是：

每個連接都會有一個獨立的線程進行處理。
阻塞式 I/O 操作會導致線程等待，直到數據準備好。
簡單易用，但在高并發場景下性能較差，因為線程資源會被大量消耗。

// 示例：BIO的Socket服務器
import java.io.*;
import java.net.*;public class BioServer {public static void main(String[] args) throws IOException {ServerSocket serverSocket = new ServerSocket(8080);while (true) {Socket socket = serverSocket.accept(); // 阻塞等待連接new Thread(() -> handle(socket)).start();}}private static void handle(Socket socket) {try (BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream()));PrintWriter out = new PrintWriter(socket.getOutputStream(), true)) {String line;while ((line = in.readLine()) != null) {out.println("Echo: " + line);}} catch (IOException e) {e.printStackTrace();}}
}

NIO（Non-blocking I/O）

NIO (Non-blocking I/O) 是 Java 1.4 引入的一種新的 I/O 模型，提供了非阻塞式的 I/O 操作。其特點包括：

基于通道（Channel）和緩沖區（Buffer）。
使用選擇器（Selector）管理多個通道，進行單線程多路復用。
非阻塞的 I/O 操作，不會阻塞線程。

// 示例：NIO的Socket服務器
import java.io.IOException;
import java.net.InetSocketAddress;
import java.nio.ByteBuffer;
import java.nio.channels.SelectionKey;
import java.nio.channels.Selector;
import java.nio.channels.ServerSocketChannel;
import java.nio.channels.SocketChannel;
import java.util.Iterator;public class NioServer {public static void main(String[] args) throws IOException {Selector selector = Selector.open();ServerSocketChannel serverSocketChannel = ServerSocketChannel.open();serverSocketChannel.bind(new InetSocketAddress(8080));serverSocketChannel.configureBlocking(false);serverSocketChannel.register(selector, SelectionKey.OP_ACCEPT);while (true) {selector.select();Iterator<SelectionKey> iterator = selector.selectedKeys().iterator();while (iterator.hasNext()) {SelectionKey key = iterator.next();iterator.remove();if (key.isAcceptable()) {SocketChannel socketChannel = serverSocketChannel.accept();socketChannel.configureBlocking(false);socketChannel.register(selector, SelectionKey.OP_READ);} else if (key.isReadable()) {SocketChannel socketChannel = (SocketChannel) key.channel();ByteBuffer buffer = ByteBuffer.allocate(1024);int bytesRead = socketChannel.read(buffer);if (bytesRead > 0) {buffer.flip();socketChannel.write(buffer);} else if (bytesRead == -1) {socketChannel.close();}}}}}
}

AIO（Asynchronous I/O）

AIO (Asynchronous I/O) 是 Java 7 引入的一種 I/O 模型，也稱為 NIO.2。AIO 提供了異步的 I/O 操作，其特點包括：

異步非阻塞 I/O 操作，通過回調機制處理 I/O 事件。
更加高效地處理大量連接，適合高性能、高并發的網絡應用。

// 示例：AIO的Socket服務器
import java.io.IOException;
import java.net.InetSocketAddress;
import java.nio.ByteBuffer;
import java.nio.channels.AsynchronousServerSocketChannel;
import java.nio.channels.AsynchronousSocketChannel;
import java.nio.channels.CompletionHandler;public class AioServer {public static void main(String[] args) throws IOException {AsynchronousServerSocketChannel serverSocketChannel =AsynchronousServerSocketChannel.open().bind(new InetSocketAddress(8080));serverSocketChannel.accept(null, new CompletionHandler<AsynchronousSocketChannel, Void>() {@Overridepublic void completed(AsynchronousSocketChannel socketChannel, Void attachment) {serverSocketChannel.accept(null, this); // 繼續接受新的連接ByteBuffer buffer = ByteBuffer.allocate(1024);socketChannel.read(buffer, buffer, new CompletionHandler<Integer, ByteBuffer>() {@Overridepublic void completed(Integer result, ByteBuffer buffer) {buffer.flip();socketChannel.write(buffer, buffer, new CompletionHandler<Integer, ByteBuffer>() {@Overridepublic void completed(Integer result, ByteBuffer buffer) {if (buffer.hasRemaining()) {socketChannel.write(buffer, buffer, this);} else {buffer.clear();socketChannel.read(buffer, buffer, this);}}@Overridepublic void failed(Throwable exc, ByteBuffer buffer) {try {socketChannel.close();} catch (IOException e) {e.printStackTrace();}}});}@Overridepublic void failed(Throwable exc, ByteBuffer buffer) {try {socketChannel.close();} catch (IOException e) {e.printStackTrace();}}});}@Overridepublic void failed(Throwable exc, Void attachment) {exc.printStackTrace();}});// 防止主線程退出while (true) {try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}}}
}

總結

BIO 適用于連接數目較小且固定的場景，編程模型簡單直觀。
NIO 適用于連接數目多且連接較短的場景，能夠通過單線程處理多連接，但編程復雜度較高。
AIO 適用于連接數目多且連接較長的場景，能夠實現完全的異步非阻塞 I/O 操作，編程模型復雜。
Netty 基于 NIO，提供了更高的抽象層，簡化了開發過程，同時具有高性能和高可擴展性，適用于大多數網絡應用場景。

6.ZooKeeper的理解，分布式事務2PC、3PC、TCC、Paxos實現思路及優缺點

GPT問答

ZooKeeper是什么，有什么特性，為啥可以滿足cp

Apache ZooKeeper 是一個開源的分布式協調服務，用于管理大型分布式系統中的配置信息、命名、同步和組服務等任務。它提供了一組簡單的原語，分布式應用程序可以用它來實現更高層次的服務，例如同步、配置管理和命名等。

ZooKeeper 的特性

簡化開發：通過提供簡單的接口和一致性保證，簡化了分布式應用程序的開發。
高可用性：ZooKeeper 通過其分布式架構實現高可用性。它的服務可以在多個服務器之間復制，保證即使個別節點失效也不會影響整個系統的運行。
嚴格的順序保證：ZooKeeper 保證對所有更新操作的全局順序。
高性能：ZooKeeper 在讀操作上具有高性能，因為讀操作可以在所有節點上進行。
一致性：ZooKeeper 保證客戶端在任何時刻讀到的數據是最新的或者是一個較新的數據版本。

ZooKeeper 的一致性模型

ZooKeeper 是一個 CP 系統（在 CAP 定理中），即它保證一致性（Consistency）和分區容忍性（Partition Tolerance），可能會在可用性（Availability）上做出犧牲。

一致性（Consistency）：
- 在 ZooKeeper 中，當一個操作返回成功時，意味著系統所有節點的數據都是一致的。
- ZooKeeper 的一致性通過其嚴格的順序保證和持久性機制實現。所有對 ZooKeeper 的寫操作（例如創建、更新或刪除節點）都會按照全局順序寫入日志，并且這些日志會在所有節點上進行復制。
分區容忍性（Partition Tolerance）：
- ZooKeeper 能夠在網絡分區的情況下繼續運行。它采用 ZAB (ZooKeeper Atomic Broadcast) 協議來保證在分區情況下的容錯性。
- 當網絡分區發生時，ZooKeeper 會選出一個主節點，只要超過半數的節點仍然能夠通信，ZooKeeper 就能繼續服務。
可用性（Availability）：
- 在 CAP 定理中，ZooKeeper 在某些情況下會犧牲可用性以保證一致性和分區容忍性。例如，在網絡分區期間，如果無法達成多數節點的共識，ZooKeeper 可能會停止提供服務，以避免不一致的數據狀態。

它通過 ZAB 協議和復制機制保證一致性和分區容忍性，這使得 ZooKeeper 在 CAP 定理中滿足 CP 的要求。盡管在極端情況下可能會犧牲可用性，但這也是為了保證系統的一致性和整體可靠性。

分布式事務2PC、3PC、TCC、Paxos實現思路及優缺點

分布式事務在分布式系統中用于保證跨多個節點的操作要么全部成功，要么全部失敗。以下是四種常見的分布式事務實現思路：2PC（Two-Phase Commit）、3PC（Three-Phase Commit）、TCC（Try-Confirm/Cancel）、Paxos。

Two-Phase Commit (2PC)

實現思路

2PC 分為兩個階段：

階段 1：準備階段（Prepare Phase）
- 協調者（Coordinator）向所有參與者（Participants）發送準備請求（Prepare Request）。
- 參與者執行事務操作并將操作結果寫入日志，但不提交（Commit），然后向協調者返回準備就緒（Ready）或失敗（Abort）。
階段 2：提交階段（Commit Phase）
- 如果所有參與者都返回準備就緒，協調者發送提交請求（Commit Request），參與者提交事務。
- 如果有任何一個參與者返回失敗，協調者發送回滾請求（Rollback Request），參與者回滾事務。

優點

實現相對簡單。
容易理解和實現基本的事務一致性。

缺點

同步阻塞：所有參與者在等待協調者的決策時會被阻塞。
單點故障：協調者故障時，系統可能會進入不一致狀態。
超時問題：參與者可能長時間等待協調者的指令。

Three-Phase Commit (3PC)

實現思路

3PC 在 2PC 的基礎上增加了一個準備提交階段，分為三個階段：

階段 1：詢問階段（CanCommit Phase）
- 協調者向所有參與者發送詢問請求（CanCommit Request）。
- 參與者返回同意（Yes）或拒絕（No）。
階段 2：準備提交階段（PreCommit Phase）
- 如果所有參與者都同意，協調者發送準備提交請求（PreCommit Request）。
- 參與者在準備提交階段確認準備就緒。
階段 3：提交階段（DoCommit Phase）
- 協調者發送提交請求（DoCommit Request），參與者提交事務。

優點

減少了單點故障的影響：通過增加階段，降低了協調者故障帶來的風險。
更加非阻塞：參與者可以在等待協調者指令時進行超時處理。

缺點

實現復雜度增加。
仍然存在網絡分區可能帶來的問題。

Try-Confirm/Cancel (TCC)

實現思路

TCC 模型分為三個操作：

Try：嘗試執行，預留資源。
Confirm：確認執行，真正提交事務。
Cancel：取消執行，釋放資源。

優點

靈活性高：可以根據業務需求自定義 Try、Confirm 和 Cancel 的邏輯。
異步執行：Try 操作可以異步執行，提高系統性能。

缺點

實現復雜度高：需要明確實現每個步驟的業務邏輯。
一致性依賴于業務邏輯的正確實現。

Paxos

實現思路

Paxos 是一種分布式一致性算法，用于在分布式系統中達成共識。主要步驟如下：

提議階段（Prepare Phase）
- 提議者（Proposer）向所有接受者（Acceptor）發送提議請求，附帶提議編號。
- 接受者返回承諾不再接受編號低于當前請求的提議。
提交階段（Accept Phase）
- 提議者收到多數接受者的承諾后，發送提交請求。
- 接受者同意該提議并更新狀態。
學習階段（Learn Phase）
- 一旦提議被多數接受者接受，提議者通知所有節點該提議已被選定。

優點

高容錯性：在大多數節點存活的情況下仍能達成一致。
非阻塞：在網絡分區情況下仍能繼續操作。

缺點

高復雜度：實現和理解相對復雜。
性能開銷：多次通信和協調帶來較高的性能開銷。

總結

2PC 和 3PC 適用于需要嚴格事務一致性的場景，但存在同步阻塞和單點故障問題。
TCC 提供了更高的靈活性和性能，但需要自定義業務邏輯實現。
Paxos 適用于需要高容錯和一致性的分布式系統，但實現復雜且性能開銷較大。根據具體業務需求和系統特性選擇合適的分布式事務方案，是設計分布式系統時的關鍵決策。
2PC和3PC在做取舍，一致性？可用性？

7. Scala跟Java的區別關系

GPT問答

Scala跟Java的區別關系

Scala 和 Java 都是運行在 JVM（Java Virtual Machine）上的編程語言，但它們在設計理念、語法特性和應用場景等方面有著顯著的區別和關系。以下是一些主要的區別和關系：

設計理念與范式

Java 是一種面向對象編程（OOP）語言，強調類和對象的使用。
Scala 是一種多范式編程語言，支持面向對象編程（OOP）和函數式編程（FP），其設計目標是提供一種更簡潔、靈活和表達力更強的編程方式。語法簡潔性
Java 語法相對冗長，需要寫較多的模板代碼（boilerplate code）。
Scala 語法簡潔，減少了大量的模板代碼。例如，Scala 中可以使用類型推斷來減少顯式類型聲明。

// Java 代碼示例
public class HelloWorld {public static void main(String[] args) {System.out.println("Hello, World!");}
}// Scala 代碼示例
object HelloWorld extends App {println("Hello, World!")
}

函數式編程支持

Java 雖然在 Java 8 之后引入了 lambda 表達式和 Stream API，但其函數式編程特性相對有限。
Scala 原生支持函數式編程，擁有強大的高階函數、不可變數據結構和模式匹配等特性。

// Java 中的 lambda 表達式
List<String> list = Arrays.asList("a", "b", "c");
list.forEach(item -> System.out.println(item));// Scala 中的高階函數
val list = List("a", "b", "c")
list.foreach(println)

類型系統

Java 使用相對傳統的類型系統，泛型在某些情況下可能帶來復雜性。
Scala 擁有更強大和靈活的類型系統，包括類型推斷、協變和逆變、隱式轉換、類型類等特性。

并發編程模型

Java 提供了線程、同步塊、并發包（如 java.util.concurrent）等用于并發編程。
Scala 提供了更高級的并發編程模型，如 Akka Actor 模型，用于簡化復雜的并發編程。

互操作性

Java 和 Scala 都運行在 JVM 上，因此它們可以互相調用。Scala 可以直接調用 Java 的類庫，反之亦然。

// Scala 調用 Java 類庫
import java.util.Dateval now = new Date()
println(now)

// Java 調用 Scala 類庫
import scala.collection.JavaConverters;List<String> list = Arrays.asList("a", "b", "c");
scala.collection.immutable.List<String> scalaList = JavaConverters.asScalaBufferConverter(list).asScala().toList();
System.out.println(scalaList);