2020一线互联网大厂面经集——阿里篇「1」

1.1.1 如何实现一个高效的单向链表逆序输出？

1.1.2 已知sqrt(2)约等于1.414，要求不用数学库，求sqrt(2)精确到小数点后10位

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

1.1.4 LRU缓存机制

1.1.5 关于epoll和select的区别，以下哪些说法是正确的.

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

1.1.7 MySQL的数据如何恢复到任意时间点？.

1.1.8 NFS与SMB的区别？

1.1.9 输入 ping IP 后敲回车，发包前会发生什么？

1.2.0 请解释下为什么鹿晗发布恋情的时候，微博系统会崩溃，如何解决？

以上问题答案及解析

1.1.1 如何实现一个高效的单向链表逆序输出？

出题人：阿里巴巴出题专家：昀龙／阿里云弹性人工智能负责人
参考答案：下面是其中一种写法，也可以有不同的写法，比如递归等。供参考。
typedef struct node{
int data;
struct node* next;
node(int d):data(d), next(NULL){}
}node;

void reverse(node* head)
{
if(head == NULL){
return;
}

node* pleft = NULL;
node* pcurrent = head;
node* pright = head->next;

while(pright){
    pcurrent->next = pleft;
    node *ptemp = pright->next;
    pright->next = pcurrent;
    pleft = pcurrent;
    pcurrent = pright;
    pright = ptemp;
}

while(pcurrent != NULL){
    cout<< pcurrent->data << "\t";
    pcurrent = pcurrent->next;
}

}
class Solution<t> {</t>

public void reverse(ListNode<T> head) {
   if (head == null || head.next == null) {
       return ;
   }
   ListNode<T> currentNode = head;
   Stack<ListNode<T>> stack = new Stack<>();
   while (currentNode != null) {
       stack.push(currentNode);
       ListNode<T> tempNode = currentNode.next;
       currentNode.next = null; // 断开连接
       currentNode = tempNode;
   }

   head = stack.pop();
   currentNode = head;

   while (!stack.isEmpty()) {
       currentNode.next = stack.pop();
       currentNode = currentNode.next;
   }
}

}

class ListNode<t>{
T val;
public ListNode(T val) {
this.val = val;
}
ListNode<t> next;
}</t></t>

1.1.2已知 sqrt (2)约等于 1.414，要求不用数学库，求 sqrt (2)精确到小数点后 10 位。
出题人：——阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家
参考答案：

• 考察点
  基础算法的灵活应用能力（二分法学过数据结构的同学都知道，但不一定往这个方向考虑；如果学过数值计算的同学，应该还要能想到牛顿迭代法并解释清楚）
  退出条件设计
  二分法

1. 已知 sqrt(2)约等于 1.414，那么就可以在(1.4, 1.5)区间做二分
   查找，如： a) high=>1.5 b) low=>1.4 c) mid => (high+low)/2=1.45 d) 1.45*1.45>2 ? high=>1.45 : low => 1.45 e) 循环到 c)

2. 退出条件
   a) 前后两次的差值的绝对值<=0.0000000001, 则可退出

const double EPSILON = 0.0000000001;

double sqrt2() {
double low = 1.4, high = 1.5;
double mid = (low + high) / 2;

while (high - low > EPSILON) {
    if (mid * mid > 2) {
        high = mid;
    } else {
        low = mid;
    }
    mid = (high + low) / 2;
}

return mid;

}
牛顿迭代法
1.牛顿迭代法的公式为：
xn+1 = xn-f(xn)/f'(xn)

对于本题，需要求解的问题为：f(x)=x2-2 的零点

EPSILON = 0.1 ** 10
def newton(x):
if abs(x ** 2 - 2) > EPSILON:
return newton(x - (x ** 2 - 2) / (2 * x))
else:

1.1.3给定一个二叉搜索树(BST)，找到树中第 K 小的节点。
出题人：阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家
参考答案：

• 考察点
  基础数据结构的理解和编码能力
  递归使用
• 示例

   5
  / \

  3 6
  /
  2 4
  /
  1

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

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

/**

• Definition for a binary tree node.
• */

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

class Solution {
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) {
    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);
}

}
1.1.4LRU 缓存机制 设计和实现一个 LRU（最近最少使用）缓存数据结构，使它应该支持一下操作：get 和 put。 get(key) - 如果 key 存在于缓存中，则获取 key 的 value（总是正数），否则返回 -1。 put(key,value) - 如果 key 不存在，请设置或插入 value。当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目作废。

出题人：文景／阿里云 CDN 资深技术专家

参考答案：

python版本的：

class LRUCache(object):
def init(self, capacity):
"""
:type capacity: int
"""
self.cache = {}
self.keys = []
self.capacity = capacity

def visit_key(self, key):
    if key in self.keys:
        self.keys.remove(key)
    self.keys.append(key)

def elim_key(self):
    key = self.keys[0]
    self.keys = self.keys[1:]
    del self.cache[key]

def get(self, key):
    """
    :type key: int
    :rtype: int
    """
    if not key in self.cache:
        return -1
    self.visit_key(key)
    return self.cache[key]

def put(self, key, value):
    """
    :type key: int
    :type value: int
    :rtype: void
    """
    if not key in self.cache:
    if len(self.keys) == self.capacity:
    self.elim_key()
    self.cache[key] = value
    self.visit_key(key)

def main():
s =
[["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[
4,4],[1],[3],[4]]]
obj = LRUCache(2)
l=[]
for i,c in enumerate(s[0]):
if(c == "get"):
l.append(obj.get(s[1][i][0]))
else:
obj.put(s[1][i][0], s[1][i][1])
print(l)

if name == "main":
main()
c++版本的：

class LRUCache{
public:
LRUCache(int capacity) {
cap = capacity;
}

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        l.splice(l.begin(), l, it->second);
        return it->second->second;
    }

    void set(int key, int value) {
        auto it = m.find(key);
        if (it != m.end()) l.erase(it->second);
        l.push_front(make_pair(key, value));
        m[key] = l.begin();
        if (m.size() > cap) {
            int k = l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }

}

1.1.5 关于epoll和select的区别，以下哪些说法是正确的
735 Bytes
lee 提交于 9月前 . revert latest push
问题：关于 epoll 和 select 的区别，哪些说法是正确的？（多选）
A. epoll 和 select 都是 I/O 多路复用的技术，都可以实现同时监听多个 I/O 事件的状态。

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

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

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

出题人：阿里巴巴出题专家：寈峰／阿里技术专家
参考答案：A，B，C
【延伸】那在高并发的访问下，epoll使用那一种触发方式要高效些？当使用边缘触发的时候要注意些什么东西？

1.1.6 从innodb的索引结构分析，为什么索引的 key 长度不能太长
405 Bytes
lee 提交于 9月前 . revert latest push
题目：从 innodb 的索引结构分析，为什么索引的 key 长度不能太长？
出题人：阿里巴巴出题专家：近秋／阿里云数据库产品技术部技术专家
参考答案：key 太长会导致一个页当中能够存放的 key 的数目变少，间接导致索引树的页数目变多，索引层次增加，从而影响整体查询变更的效率。

1.1.7 MySQL的数据如何恢复到任意时间点？
435 Bytes
lee 提交于 9月前 . revert latest push
题目：MySQL 的数据如何恢复到任意时间点？
出题人：阿里巴巴出题专家：近秋／阿里云数据库产品技术部技术专家参考答案
参考答案：恢复到任意时间点以定时的做全量备份，以及备份增量的 binlog 日志为前提。恢复到任意时间点首先将全量备份恢复之后，再此基础上回放增加的 binlog 直至指定的时间点。

1.1.8 NFS与SMB的区别？
917 Bytes
lee 提交于 9月前 . revert latest push
题目：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

1.1.9 输入 ping IP 后敲回车，发包前会发生什么？
822 Bytes
lee 提交于 9月前 . revert latest push
题目：输入 ping IP 后敲回车，发包前会发生什么？
出题人：阿里巴巴出题专家：怀虎／阿里云云效平台负责人
参考答案：
ping目标ip时，先查路由表，确定出接口

如果落在直连接口子网内，此时若为以太网等 多路访问网络 则先查询arp缓存，命中则直接发出，否则在该接口上发arp询问目标ip的mac地址，取得后发出，若为ppp等 点对点网络 ，则直接可以发出；
如果查表落在缺省路由上，此时若为以太网等 多路访问网络 则先查询网关arp缓存，命中则直接发出，否则在该接口上发arp询问网关的mac地址，取得后发出，若为ppp等 点对点网络 ，则直接可以发出；
若查表未命中，则返回不可达。

1.2.0 请解释下为什么鹿晗发布恋情的时候，微博系统会崩溃，如何解决？
459 Bytes
lee 提交于 9月前 . revert latest push
题目：请解释下为什么鹿晗发布恋情的时候，微博系统会崩溃，如何解决？
出题人：阿里巴巴出题专家：江岚／阿里巴巴数据技术高级技术专家
参考答案：
A. 获取微博通过 pull 方式还是 push 方式

B. 发布微博的频率要远小于阅读微博

C. 流量明星的发微博，和普通博主要区分对待，比如在 sharding的时候，也要考虑这个因素

更多大厂面试经验题目集锦大纲点击下方

**大厂面试经验题目超详细解析免费拿网址：https://github. https://github. com/Ovoice/ interview internal reference *