Java面试题

1. 给定一个二叉搜索树(BST)，找到树中 第 K 小的节点。

考察点

1. 基础数据结构的理解和编码能力
2. 递归使用

示例:
如下图，输入 K=3， 输出节点值 3

说明:保证输入的 K 满足 1<=K<=(节点数目)

参考答案

树相关的题目，第一眼就想到递归求解，左右子树分别遍历。联想 到二叉搜索树的性质，root 大于左子树，小于右子树，如果左子树 的节点数目等于 K-1，那么 root 就是结果，否则如果左子树节点数 目小于 K-1，那么结果必然在右子树，否则就在左子树。因此在搜 索的时候同时返回节点数目，跟 K 做对比，就能得出结果了。

◼ 代码示例:

class Solution {
Definition for a binary tree node. public class TreeNode {
int val;
TreeNode left;
TreeNode right; TreeNode(int x) { val = x; }
private class ResultType { // 是否找到
boolean found; // 节点数目
int val;
ResultType(boolean found, int val) { this.found = found;
this.val = val;
} }
public int kthSmallest(TreeNode root, int k) { return kthSmallestHelper(root, k).val;
}
private ResultType kthSmallestHelper(TreeNode root, int k) {
11
 
if (root == null) {
return new ResultType(false, 0);
}
ResultType left = kthSmallestHelper(root.left, k);
// 左子树找到，直接返回
if (left.found) {
return new ResultType(true, left.val);
}
// 左子树的节点数目 = K-1，结果为 root 的值
if (k - left.val == 1) {
return new ResultType(true, root.val);
}
// 右子树寻找
ResultType right = kthSmallestHelper(root.right, k - left.val - 1); if (right.found) {
return new ResultType(true, right.val); }
// 没找到，返回节点总数
return new ResultType(false, left.val + 1 + right.val);
} }

复杂度分析:
时间复杂度: O(N)，节点最多遍历一遍 空间复杂度:O(1)，(如果算上递归深度可以当做 O(logN))

2. 关于 epoll 和 select 的区别，哪些说法 是正确的?(多选)

• A. epoll 和 select 都是 I/O 多路复用的技术，都可以实现同时监听 多个 I/O 事件的状态。

• B. epoll 相比select 效率更高，主要是基于其操作系统支持的 I/O 事件通知机制，而 select 是基于轮询机制。

• C.epoll支持水平触发和边沿触发两种模式。

• D. select 能并行支持 I/O 比较小，且无法修改。

参考答案 A.B.C

3. 从 innodb 的索引结构分析，为什么索 引的 key 长度不能太长?

参考答案

key 太长会导致一个页当中能够存放的 key 的数目变少，间接导致 索引树的页数目变多，索引层次增加，从而影响整体查询变更的效 率。

4. MySQL 的数据如何恢复到任意时间点?

参考答案

恢复到任意时间点以定时的做全量备份，以及备份增量的 binlog 日 志为前提。恢复到任意时间点首先将全量备份恢复之后，再此基础 上回放增加的 binlog 直至指定的时间点。

5. NFS 和 SMB 是最常见的两种 NAS (Network Attached Storage)协议，当把一个文件 系统同时通过 NFS 和 SMB 协议共享给多个主机访问时， 以下哪些说法是错误的:(多选)

• A. 不可能有这样的操作，即把一个文件系统同时通过 NFS 和 SMB 协议共享给多个主机访问。
• B. 主机a的用户通过NFS协议创建的文件或者目录，另一个主机b 的用户不能通过 SMB 协议将其删除。
• C. 在同一个目录下，主机 a 通过 NFS 协议看到文件 file.txt，主机 b 通过 SMB 协议也看到文件
  file.txt，那么它们是同一个文件。
• D. 主机 a 通过 NFS 协议，以及主机 b 通过 SMB 协议，都可以通过 主机端的数据缓存，提升文件访问性能。

参考答案 A.B.C

——摘自阿里巴巴出题专家:江岚/阿里巴巴数据技术高级技术专家