▶ 如何在有序数组中实现二分查找？请给出多语言实现，并说明时间复杂度$ O(\log n) $
二分查找（Binary Search）利用元素有序的特性，每次将搜索区间折半，直到找到目标或区间为空。
▶ 如何在有序数组中实现二分查找？请给出多语言实现，并说明时间复杂度$ O(\log n) $
- 输入：有序数组
nums及目标值target - 输出：目标值在数组中的索引，若不存在则返回
-1 - 时间复杂度：$ O(\log n) $
- 空间复杂度：$ O(1) $
- 输入：有序数组
nums及目标值target - 输出：目标值在数组中的索引，若不存在则返回
-1 - 时间复杂度：$ O(\log n) $
- 空间复杂度：$ O(1) $
实现代码：
from typing import List
def binary_search(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
package algo
// BinarySearch returns the index of target or -1 if not found.
func BinarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
switch {
case nums[mid] == target:
return mid
case nums[mid] < target:
left = mid + 1
default:
right = mid - 1
}
}
return -1
}
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
▶ 请反转单链表，并给出时间复杂度
反转单链表可通过迭代一次遍历来实现。
- 时间复杂度：$ O(n) $
- 空间复杂度：$ O(1) $
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head: ListNode) -> ListNode:
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prev
type ListNode struct {
Val int
Next *ListNode
}
func ReverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
▶ 快速排序的原理及实现，平均时间复杂度是多少？
快速排序（Quick Sort）采用分治思想：
- 选择基准
pivot； - 将数组划分为小于基准、等于基准和大于基准三部分；
- 递归地排序左右子数组。
平均时间复杂度：$ O(n \log n) $ ，最坏情况：$ O(n^2) $ 。
def quicksort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quicksort(left) + middle + quicksort(right)
func QuickSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}
pivot := nums[len(nums)/2]
left, mid, right := []int{}, []int{}, []int{}
for _, v := range nums {
switch {
case v < pivot:
left = append(left, v)
case v > pivot:
right = append(right, v)
default:
mid = append(mid, v)
}
}
return append(append(QuickSort(left), mid...), QuickSort(right)...)
}
public List<Integer> quickSort(List<Integer> nums) {
if (nums.size() <= 1) return nums;
int pivot = nums.get(nums.size() / 2);
List<Integer> left = new ArrayList<>();
List<Integer> mid = new ArrayList<>();
List<Integer> right = new ArrayList<>();
for (int n : nums) {
if (n < pivot) left.add(n);
else if (n > pivot) right.add(n);
else mid.add(n);
}
List<Integer> res = new ArrayList<>();
res.addAll(quickSort(left));
res.addAll(mid);
res.addAll(quickSort(right));
res.addAll(quickSort(right));
return res;
}
▶ Kubernetes 是什么？
Kubernetes 是一个开源的容器编排平台，用于自动化部署、扩展和管理容器化应用程序。
▶ Kubernetes 的核心组件有哪些？
- Master 组件：kube-apiserver, kube-scheduler, kube-controller-manager, etcd.
- Node 组件：kubelet, kube-proxy, container runtime.
▶ Kubernetes 的 Pod 是什么？
Pod 是 Kubernetes 中最小的部署单元。它可以包含一个或多个容器，这些容器共享网络和存储资源。
▶ Kubernetes 的 Service 是什么？
Service 是对一组 Pod 的抽象，它定义了访问这些 Pod 的方式。Service 可以提供负载均衡和服务发现的功能。
▶ Kubernetes 的 Deployment 是什么？
Deployment 用于管理 Pod 的部署和更新。它可以确保指定数量的 Pod 正在运行，并在 Pod 发生故障时自动替换它们。
▶ Kubernetes 的 Ingress 是什么？
Ingress 用于将外部流量路由到集群内部的 Service。它可以提供基于 HTTP/HTTPS 的路由规则。
▶ Kubernetes 的 ConfigMap 和 Secret 有什么区别？
- ConfigMap 用于存储非敏感的配置数据。
- Secret 用于存储敏感数据，例如密码、API 密钥等。Secret 中的数据是经过 base64 编码的。
▶ Kubernetes 的 livenessProbe 和 readinessProbe 有什么区别？
- livenessProbe 用于检测容器是否还存活。如果检测失败，kubelet 会杀死该容器，并根据重启策略来决定是否重启它。
- readinessProbe 用于检测容器是否已经准备好接收请求。如果检测失败，端点控制器会从 Service 的端点中移除该 Pod 的 IP 地址。
▶ Kubernetes 的 Helm 是什么？
Helm 是 Kubernetes 的包管理器。它允许你定义、安装和升级复杂的 Kubernetes 应用程序。
▶ Kubernetes 的亲和性和反亲和性是什么？
- 亲和性：用于将 Pod 调度到满足特定条件的节点上。
- 反亲和性：用于避免将 Pod 调度到满足特定条件的节点上。
▶ Docker 是什么？
Docker 是一个开源的应用容器引擎，让开发者可以打包他们的应用以及依赖包到一个可移植的容器中，然后发布到任何流行的 Linux 机器上，也可以实现虚拟化。
▶ Docker 的核心概念有哪些？
镜像（Image）、容器（Container）、仓库（Repository）。
▶ Docker 镜像和容器有什么区别？
镜像是静态的，它是一个只读的模板。容器是动态的，它是镜像的运行实例。
▶ Dockerfile 是什么？
Dockerfile 是一个用来构建镜像的文本文件，它包含了一条条的指令，每一条指令构建一层。
▶ Docker 的数据卷（Volume）有什么用？
数据卷用于持久化容器中的数据。它可以将宿主机的目录挂载到容器中，从而实现数据的持久化。
▶ Docker Compose 是什么？
Docker Compose 是一个用于定义和运行多容器 Docker 应用程序的工具。它使用 YAML 文件来配置应用程序的服务。
▶ Docker Swarm 是什么？
Docker Swarm 是 Docker 官方提供的容器编排工具。它可以将多个 Docker 主机组合成一个集群，并以集群的方式来管理容器。
▶ Docker 的网络模式有哪些？
bridge, host, none, container.
▶ 如何清理 Docker 中的无用镜像和容器？
docker image prune：清理无用的镜像。docker container prune：清理无用的容器。docker system prune：清理所有无用的镜像、容器、网络和数据卷。
▶ Kubernetes 和 Docker Swarm 有什么区别？
- Kubernetes 是一个更强大、更复杂的容器编排工具，它提供了更丰富的功能，例如自动扩缩容、服务发现、负载均衡等。
- Docker Swarm 更简单、更容易上手，但功能相对较少。
▶ MySQL 的 InnoDB 和 MyISAM 存储引擎有什么区别？
- InnoDB 支持事务和外键，MyISAM 不支持。
- InnoDB 支持行级锁，MyISAM 只支持表级锁。
- InnoDB 的数据和索引是存储在同一个文件中的，MyISAM 是分开存储的。
▶ MySQL 的索引有哪些类型？
普通索引、唯一索引、主键索引、组合索引、全文索引。
▶ MySQL 的事务隔离级别有哪些？
读未提交、读已提交、可重复读、串行化。
▶ MySQL 的 B+ 树索引有什么特点？
- 所有数据都存储在叶子节点上。
- 叶子节点之间通过指针连接，形成一个有序链表。
- 非叶子节点只存储索引，不存储数据。
▶ MySQL 的 MVCC 是什么？
MVCC（多版本并发控制）是一种并发控制的方法。它通过保存数据在某个时间点的快照来实现。在 InnoDB 中，MVCC 是通过在每行记录后面保存两个隐藏的列来实现的。
▶ MySQL 的 explain 命令有什么用？
explain 命令用于分析 SQL 语句的执行计划。它可以帮助我们了解 SQL 语句的执行情况，从而进行优化。
▶ MySQL 的 binlog 有什么用？
binlog（二进制日志）记录了所有对数据库进行修改的操作。它可以用于数据恢复和主从复制。
▶ MySQL 的慢查询日志有什么用？
慢查询日志用于记录执行时间超过指定阈值的 SQL 语句。它可以帮助我们找到性能瓶颈。
▶ MySQL 的分库分表有哪些方式？
- 垂直拆分：将一个大表按列拆分成多个小表。
- 水平拆分：将一个大表按行拆分成多个小表。
▶ MySQL 的索引优化有哪些方法？
- 避免在索引列上使用函数或表达式。
- 使用覆盖索引。
- 避免使用 select *。
- 使用联合索引时，遵循最左前缀原则。
▶ Redis 有哪些数据结构？
String, Hash, List, Set, Sorted Set.
▶ Redis 的持久化方式有哪些？
RDB 和 AOF.
▶ Redis 的哨兵（Sentinel）模式有什么作用？
哨兵模式用于实现 Redis 的高可用。它可以监控 master 节点的状态，并在 master 节点宕机时，自动将一个 slave 节点提升为新的 master 节点。
▶ Redis 的缓存穿透、缓存击穿和缓存雪崩是什么？
- 缓存穿透：查询一个不存在的数据，导致请求一直访问数据库。
- 缓存击穿：一个热点 key 过期，导致大量请求同时访问数据库。
- 缓存雪崩：大量 key 同时过期，导致大量请求同时访问数据库。
▶ Redis 的事务支持原子性吗？
Redis 的事务只保证隔离性和一致性，不保证原子性。事务中的命令会按顺序执行，但如果其中一个命令执行失败，其他命令仍然会继续执行。
▶ Redis 的过期键删除策略有哪些？
- 定期删除：每隔一段时间，随机抽取一些设置了过期时间的 key，检查是否过期，如果过期就删除。
- 惰性删除：在访问一个 key 时，先检查它是否过期，如果过期就删除。
▶ Redis 的内存淘汰策略有哪些？
noeviction, allkeys-lru, volatile-lru, allkeys-random, volatile-random, volatile-ttl.
▶ Redis 如何实现分布式锁？
可以使用 SETNX 命令来实现。当一个客户端执行 SETNX key value 成功时，表示它获取了锁。执行完毕后，再通过 DEL 命令释放锁。
▶ Redis 的主从复制是如何工作的？
主从复制分为全量复制和增量复制。当一个 slave 节点第一次连接 master 节点时，会进行全量复制。之后，master 节点会将写操作的命令同步给 slave 节点，进行增量复制。
▶ Redis Cluster 的数据分片方式是什么？
Redis Cluster 采用哈希槽（hash slot）的方式来进行数据分片。它将 16384 个哈希槽分配给不同的节点。
▶ Go 语言的 goroutine 是什么？
goroutine 是 Go 语言中并发执行的单元。它由 Go 运行时管理，比线程更轻量。
▶ Go 语言的 channel 是什么？
channel 是 goroutine 之间通信的管道。它可以用来在 goroutine 之间传递数据。
▶ Go 语言的 defer 关键字有什么作用？
defer 用于延迟一个函数或方法的执行。被延迟的函数或方法会在当前函数执行完毕后，按照后进先出的顺序执行。
▶ Go 语言的 select 语句有什么用？
select 语句用于在多个 channel 操作中进行选择。它会阻塞，直到其中一个 channel 操作可以进行。
▶ Go 语言的 map 是线程安全的吗？
不是。如果需要在多个 goroutine 中并发地读写一个 map，必须使用互斥锁等同步机制来保护。
▶ Go 语言中的 new 和 make 有什么区别？
new 用于分配内存，返回指向类型的指针，并且该指针指向的值为该类型的零值。make 用于为 slice、map 和 channel 类型分配内存并初始化，返回的是类型本身，而不是指针。
▶ Go 语言的接口（interface）是什么？
接口是一组方法的集合。一个类型只要实现了接口中定义的所有方法，就被认为是实现了该接口。
▶ Go 语言的 GMP 模型是什么？
GMP 是 Go 语言的调度器模型，G 代表 goroutine，M 代表内核线程，P 代表处理器。调度器负责将 G 分配到 M 上执行。
▶ Go 语言的垃圾回收（GC）是如何工作的？
Go 语言使用三色标记清除算法进行垃圾回收。它通过并发的方式执行，以减少对程序性能的影响。
▶ Go 语言中的 rune 类型是什么？
rune 是 Go 语言中 char 类型的一种别名，用于表示一个 Unicode 码点。