Job

面经--阿里

#面经–阿里

阿里一面—基础，语言无关

1.介绍项目

搜索引擎项目（Nutch+Lucene）

2.Nutch（加强细节）

优化实现细节
缓存存储结构如何实现

3.Lucene（需要加强）

  • 什么是索引
    数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。

  • 如何实现索引

  • Lucene索引结构

  • 倒排索引
    一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

4.算法

  • 题目一：乱序数组，求出其中最小的 k 个值
    小顶堆 时间复杂度O(nlogk)

  • 题目二：有N个长度不一样的数组，所有数组中的元素都是从小到大有序排列的，请从大到小打印这N个数组整体的前K个数。
    TOP-K问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package Test;
  
import java.util.Arrays;  
  
public class PrintMaxTopKInMatrix {  
    public static class HeapNode {
        public int value;
        public int arrNum;
        public int index;
    
        public HeapNode(int value, int arrNum, int index) {  
            this.value = value;  
            this.arrNum = arrNum;  
            this.index = index;  
        }  
    }  
    
    public static void printTopK(int[][] matrix, int topK) {  
        int heapSize = matrix.length;  
        HeapNode[] heap = new HeapNode[heapSize];  
        for (int i = 0; i != heapSize; i++) {  
            int index = matrix[i].length - 1;  
            heap[i] = new
            HeapNode(matrix[i][index], i, index);  
            heapInsert(heap, i);  
        }  
        System.out.println("TOP " + topK + " : ");  
  
        for (int i = 0; i != topK; i++) {  
            if (heapSize == 0) {  
                break;  
            }  
        System.out.print(heap[0].value + " ");  
        if (heap[0].index != 0) {  
            heap[0].value =
            matrix[heap[0].arrNum][--heap[0].index];  
        } else {  
            swap(heap, 0, --heapSize);  
        }  
        heapify(heap, 0, heapSize);  
    }  
    
    public static void heapInsert(HeapNode[] heap, int index) {  
        while (index != 0) {  
            int parent = (index - 1) / 2;  
            if (heap[parent].value < heap[index].value) {  
                swap(heap, parent, index);  
                index = parent;  
            } else {  
                break;  
            }  
        }  
    }  

    public static void heapify(HeapNode[] heap, int index, int heapSize) {  
        int left = index * 2 + 1;  
        int right = index * 2 + 2;  
        int largest = index;  
        while (left < heapSize) {  
            if (heap[left].value > heap[index].value) {  
                largest = left;  
            }  
            if (right < heapSize && heap[right].value > heap[largest].value) {  
                largest = right;  
            }  
            if (largest != index) {  
                swap(heap, largest, index);  
            } else {  
                break;  
            }  
            index = largest;  
            left = index * 2 + 1;  
            right = index * 2 + 2;  
        }  
    }  
  
    public static void swap(HeapNode[] heap, int index1, int index2) {
        HeapNode tmp = heap[index1];  
        heap[index1] = heap[index2];  
        heap[index2] = tmp;  
    }  
  
    public static int[][] generateRandomMatrix(int maxRow, int maxCol, int maxValue) {  
        if (maxRow < 0 || maxCol < 0) {  
            return null;
        }  
  
        int[][] matrix = newint[(int)(Math.random() * maxRow) + 1][];  
        for (int i = 0; i != matrix.length; i++) {  
            matrix[i] = new
            int[(int)(Math.random() * maxCol) + 1];  
  
            for (int j = 0; j != matrix[i].length; j++) {  
                matrix[i][j] = (int)(Math.random() * maxValue);  
            }  
            Arrays.sort(matrix[i]);  
        }  
        return matrix;  
    }  
    
    public static void printMatrix(int[][] matrix) {  
        for (int i = 0; i != matrix.length; i++) {  
            for (int j = 0; j != matrix[i].length; j++) {  
                System.out.print(matrix[i][j] + " ");  
            }  
        System.out.println();  
        }  
    }  
  
    public static void main(String[] args) {  
        int[][] matrix = generateRandomMatrix(5, 10, 1000);  
        printMatrix(matrix);  
        System.out.println("===========================");
        printTopK(matrix, 100);  
    }  
}

阿里二面—基础，语言

使用java集合类设计一种缓存机制实现LRU替换机制

LinkedHashMap

缓存淘汰算法

FIFO：First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。
LRU：Least Recently Used，最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。
LFU：Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。

选用Redis的原因

concurrentHashMap底层实现

MySQL的乐观锁和悲观锁如何实现

　　乐观锁（ Optimistic Locking ）假设认为数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则让返回用户错误的信息，让用户决定如何去做。
　　实现数据版本有两种方式，第一种是使用版本号，第二种是使用时间戳。
　　悲观锁，假设认为数据每次访问都会发生冲突，所以在访问数据前先加锁

MySQL索引

Hash冲突及解决方法

开放定址法
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
拉链法

B树和B+树的区别

B树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

HashMap底层实现

HashSet底层实现及如何实现去重

基于HashMap实现，在加入数据时比较去重

Linux命令

  • top命令中表示cpu状态的us和sy的区别
    • us — 用户空间占用CPU的百分比
    • sy — 内核空间占用CPU的百分比

线程池如何保证完成任务线程的空闲不被kill掉

java多线程

写出生产者消费者模式。

线程池的底层实现和工作原理（建议写一个雏形简版源码实现）