阿里巴巴-2018-校招内推-杭州

[toc]

#阿里巴巴

#网上面经总结

##编程测试：

1.题目：小猴子下山，沿着下山的路有一排桃树，每棵树都结了一些桃子。小猴子想摘桃子，但是又一些条件需要遵守，小瘦子只能沿着下山的方向走，不能回头，每棵树最多摘一个，而且一旦摘了一棵树的桃子，就不能再摘比这棵树结的桃子少的树上的桃子，那么小猴子最多能摘到几课桃子呢？
距离说明，比如有五棵树，分别结了10，4，5，12，8棵桃子，那么小猴子最多能摘3颗桃子，来自于结了4，5，12颗桃子的桃树。

输入范例：
5
10
4
5
12
8
输出范例：
3

    /*Solution 1: 最长递增子序列
    DP[i] : longest incrasing subsequence include nums[i]
    determination : Max_Value = Math.max(DP[i])
    DP[0] = 1;
    DP[i] =  0 ~ i - 1里 DP最大的那个。
    也就是说，我们要check的是从0开始，从1开始，从2开始--走向j。
    一定不可以只用count，那样只记录了从0走向J，那么会出现：
    0， 1， 2， 7， 5，10 ，j在10的位置，那么count = 4 + 1。不对。

    */

//S1:    
public class Main {

   public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int trees[] = new int[n];
        for(int i=0;i<n;i++){
            trees[i] = input.nextInt();
        }

        int[]DP = new int[n];
        DP[0] = 1;
        int ans = 1;
        //Wrong:
        //for(int j = 1; j < trees.length; j++){
        //         int currentMax = 0;
        //         for(int i = 0; i < j; i++){
        //             int count = 0;
        //             if(nums[i] < nums[j]){
        //                 count++;
        //             }
        //             currentMax = Math.max(count,currentMax);
        //         }
        //         DP[j] = Math.max(currentMax + 1, DP[i]);
        // }

        for(int j = 1; j < trees.length; j++){
            int levelMax = 0;
            for(int i = 0; i < j; i++){
                if(nums[i] < nums[j]){
                    levelMax = Math.max(levelMax, DP[i]);
                }
            }
            DP[j] = levelMax + 1;
            ans = Math.max(DP[j], ans);
        }
        return ans;


/*
    Solution 1 Time Complexity: o(n^2) --- Optimize : BST
    Solution 2 : BST + DP

    return DP[len];

    8 5 7 2 1 0 6 9

    8
    5 7
    2 7 
    1 7
    0 7
    0 6 
    0 6 9
    return 3 

    BST : find the first emelent bigger than target

*/        


//S2 : 

public class Main(){
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int nums[] = new int[n];
        for(int i : nums){
            i = intput.nexInt();
        }

        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);

        for(int i = 1; i < nums.length; i++){
            int target = nums[i];
            int start = 0; int end = list.size() - 1;
            while(start <= end){
                int mid = (end - start) / 2 + start;
                if(list.get(mid) < target){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }
            if(list.get(start) < target){
                list.add(target);
            }else{
                list.set(start, target);
            }
        }
        return list.size();
    }
}

##电话面试：

1.求一个数组前K小的数.

    /*Solution*/

    8 5 7 2 1 0 6 5 9   Eg : k = 3

    1. Sort + for : nlog(n) --> k
    2. Quick Selection:
    3. Heap : 
        A. MinHeap : Store all, Space O(n) --> Streaming flow !
        B. MaxHeap : Store k
                8 7 5
                top.peek() 
                if top < nums[i]
                    top.pop();
                    insert(nums[i]);
                Ans : top.peek();

    Solution 3:            
    public int findKthSmallest(int[] a, int k) {
            Queue<Integer> queue = new PriorityQueue<>(
                (a, b) -> {b.val - a.val}
            );
        }

        // heapify : o(k)
        for(int i = 0; i <k ; i++){
            queue.offer(a[i]);
        }        

        //o(n - k)log(k) 
        for(int i = k; i < a.length; i++){
            int head = queue.peek();
            if(a[i] < head){
                queue.poll();
                queue.offer(nums[i]);
            }
        }
        return queue.peek();


    Solution 2: QuickSelection

    The basic idea is to use Quick Select algorithm to
    partition the array with pivot:

    Put numbers < pivot to pivot's left
    Put numbers > pivot to pivot's right
Then:
if indexOfPivot == k, return A[k]
else if indexOfPivot < k, keep checking left part to pivot
else if indexOfPivot > k, keep checking right part to pivot



public int findKthSmall(int[] nums, int k){
        k--;
        int start = 0; int end = nums.length - 1;
        while(start + 1 <  end){
            int pivot = partation(nums, start, end);
            System.out.println(pivot);
            if (pivot < k){
                start = pivot + 1;
            }else if(pivot > k){
                end = pivot - 1;
            }else{
                return nums[pivot];
            }
        }

        if(start == k){
            return nums[start];
        }else{
            return  nums[end];
        }
    }

    private int partation(int[] nums, int left, int right){
        int pivot = right;
        int target = nums[right--];
        while (left <= right){
            while (left <= right && nums[left] < target){
                left++;
            }
            while(left <= right && nums[right] > target){
                right--;
            }

            if(left <= right){
                swap(nums,left, right);
            }

        }

        swap(nums, left, pivot);
        return  left;
    }

Fellow Up
Kth Smallest Element in a BST

.

2. Sort

【heapSort】–> maxheap :

1. from bottom to up : BuildMaxheap o(n)
   continuously swap the heap with last one
2. from up to bottom heapfiy O(nlogn)

就是1. heapfiy 2. 丢到末尾。 3.接着heapfiy， 再丢到末尾

Parent i
left child 2i
right child 2i + 1

【QuickSort】
choose more than 4 pivot, get median of it as pivot
Time will converge to nlog(n)

【B-tree】
用于数据库索引，每个节点可以保存多个key
Assumption:
Maximum 3 keys in an internal node
Maximum 3 keys in a leaf node

• A new key is always inserted into a leaf node first.
• If an overflow occurs at a leaf node, the node splits around the middle and the rightmost key of the left node is copied into its parent node.
  • If there is no parent node, a new level is created.
• If an overflow occurs at an internal node, the node splits around the middle and the rightmost key of the left node is moved into its parent node.
  • If there is no parent node,a new level is created.

B+Tree
B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

每个节点的指针上限为2d而不是2d+1。

内节点不存储data，只存储key；叶子节点不存储指针。

###MySQL索引

• B-Tree索引：
  所有值（被索引的列）都是排过序的，每个叶节点到跟节点距离相等。所以B-Tree适合用来查找某一范围内的数据
  Eg:Innodb myisam

• Hash索引:
  只支持精确查找，不支持范围查找，不支持排序。
  KEY USING HASH(fname)
  Eg: Memory引擎

• full-text索引: 主要用来查找文本中的关键字

• r-tree索引:（空间）索引

数据库事务

1. 原子性（Atomicity）
   　　原子性是指事务包含的所有操作要么全部成功，要么全部失败回滚
2. 一致性（Consistency）
   　　一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态，也就是说一个事务执行之前和执行之后都必须处于一致性状态
3. 隔离性（Isolation）

   　隔离性是当多个用户并发访问数据库时，比如操作同一张表时，数据库为每一个用户开启的事务，不能被其他事务的操作所干扰，多个并发事务之间要相互隔离
   

4. 持久性（Durability）
   持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作

###MySQl 四种事务隔离级说明

• read uncommitted : A没提交， B就可以读 —> 脏读
• read commited： A提交 B才可以读 —> 大部分数据库采取的是这种
• repeatable： A提交了id = 3， 1000， B读不出来，B还是读的原始状态（只有id 1 和 id 2的信息），可是又不让B set id=3 ，数据重复。–> 幻读
• serliazale : set B 为此等级， 则B在执行的时候，A被hand on，不能进行任何操作 –> 影响性能

https://www.jianshu.com/p/4e3edbedb9a8

###3. HashMap 原理

[源码分析]https://blog.csdn.net/zxt0601/article/details/77413921

    1. HashMap --> array + linkedlist
                         consistant 连续存储 
                         key-value o(1) 
                         允许key值为null， value 为null
                         它实现了Map<K,V>, Cloneable, Serializable接口。                

    2. HashMap --> hashcode（）+ 扰动函数
        算法：对数组的大小取模 hash & (length-1)
        多对1的不可逆过程， 对于hashcode相同的Key：
        我们用linkedlist来存的，也就是：
        Array里的bucket。
        然后每个linkedlist一个node是一个entry，key/value/next指针

        ---> 链表太长的问题。

    3.collision 碰撞


        A. java8 以后 linkedlist自动转化为红黑树 O(n)--O(log n)
                java8 : getOrDefault()
                java8 ： putIfAbsent（true：若key对应的value之前存在，不会覆盖）
        B. load factor = bucket size/ Capacity = 0.75--> resize 2倍




扩容操作时，会new一个新的Node数组作为哈希桶，
然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中，
相当于对原哈希表中所有的数据重新做了一个put操作。
所以性能消耗很大，可想而知，在哈希表的容量越大时，性能消耗越明显。        

    4. 源码 

    putVal() / onlyifAbsenct() 见图
    resize() ：
    **初始化或加倍哈希桶大小。
    如果是当前哈希桶是null,分配符合当前阈值的初始容量目标。 
    否则，判断 我们扩容成以前的两倍。
    get():

    HashMap的源码中，充斥个各种位运算代替常规运算的地方，以提升效率： 
* 与运算替代模运算。求index时，用 hash & (table.length-1) 替代 hash % (table.length) 
* 用if ((e.hash & oldCap) == 0)判断扩容后，节点e处于低区还是高区


    5. HashTable VS HashMap

     1) sychronized意味着在一次仅有一个线程能够更改Hashtable。
     就是说任何线程要更新Hashtable时要首先获得同步锁，
     其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。 --->效率低

    2) Fail-safe和iterator迭代器相关。（HashMap,Vector,ArrayList,HashSet）
    如果某个集合对象创建了Iterator或者ListIterator，
    然后其它的线程试图“结构上”更改集合对象，
    将会抛出ConcurrentModificationException异常。
    但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。
    但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。

    3) 结构上的更改指的是删除或者插入一个元素，这样会影响到map的结构。

我们能否让HashMap同步？
HashMap可以通过下面的语句进行同步：
Map m = Collections.synchronizeMap(hashMap);    


    6. 分布式存储，当每一个节点是一台机器的时候：
        consistent hashing, 对2^32次方取模
        将所有对象存储到离自己最近的机器中。
        一致性hash算法可以均匀分担机器的负载，解决了分布式环境下机器需要增加或者减少的问题。


    7. 内存泄露：
    对于应用程序来说，当对象已经不再被使用，但是Java的垃圾回收器不能回收它们的时候，
    就产生了内存泄露。
    HashMap  ArrayList  Vector：静态变量的生命周期和应用程序一致，他们所引用的所有的对象Object也不能被释放
    https://www.jianshu.com/p/d2823693ccc2


    8. [服务器死循环]HashMap并非是线程安全的，
        所以在高并发的情况下必然会出现问题。 

    所以在并发的情况，发生扩容时，可能会产生循环链表，
    在执行get的时候，会触发死循环，引起CPU的100%问题，
    所以一定要避免在并发环境下使用HashMap。

曾经有人把这个问题报给了Sun，不过Sun不认为这是一个bug，
因为在HashMap本来就不支持多线程使用，要并发就用ConcurrentHashmap

###4. 红黑树原理和优势

        BST tree 特点 : height log(n) --> 
                        anynode anyoperation -log(n)

        red black tree: rotation --> self balance
        黑色是树干        红色是node
           x               y
        1     y          x   3
            2   3       1  2

        1.红&黑    
        2.root是黑的，insert是红的，
        3.叶子到根的所有路径上不能有两个连续的红色节点  
        4.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 

    * AVL树的每个节点的左右子树的高度差不超过1

5. jvm的内存模型

程序计数器，虚拟机方法栈，本地方法栈，方法区，堆

静态存储区（方法区）：主要存放静态数据、全局 static 数据和常量。这块内存在程序编译时就已经分配好，并且在程序整个运行期间都存在。

栈区 ：当方法被执行时，方法体内的局部变量（其中包括基础数据类型、对象的引用）都在栈上创建，并在方法执行结束时这些局部变量所持有的内存将会自动被释放。因为栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。

堆区 ： 又称动态内存分配，通常就是指在程序运行时直接 new 出来的内存，也就是对象的实例。这部分内存在不使用时将会由 Java 垃圾回收器来负责回收。

程序计数器: 每当启动一个新线程时，都会为这个新线程创建一个自己的PC(程序计数器)寄存器.程序计数器的作用可以看做是当前线程所执行的字节码的行号指示器。

类装载器子系统

负责查找并装载Class 文件到内存，最终形成可以被虚拟机直接使用的Java类型，这个过程主要包括三个步骤。
（1）装载
装载过程负责找到二进制字节码并加载至JVM中，JVM通过类名、类所在的包名通过ClassLoader来完成类的加载，同样，也采用以上三个元素来标识一个被加载了的类：类名+包名+ClassLoader实例ID。
（2）链接
链接过程负责对二进制字节码的格式进行校验、初始化装载类中的静态变量以及解析类中调用的接口、类。
在完成了校验后，JVM初始化类中的静态变量，并将其值赋为默认值。
最后一步为对类中的所有属性、方法进行验证，以确保其需要调用的属性、方法存在，以及具备应的权限（例如public、private域权限等），会造成NoSuchMethodError、NoSuchFieldError等错误信息。
（3）初始化
初始化过程即为执行类中的静态初始化代码、构造器代码以及静态属性的初始化，在四种情况下初始化过程会被触发执行：
调用了new；反射调用了类中的方法；子类调用了初始化；JVM启动过程中指定的初始化类。

6. GC

GC什么时候/对什么东西/做了什么事情
http://wwwcomy.iteye.com/blog/1798255

简单理解Java的垃圾回收机制与finalize方法的作用
https://www.jb51.net/article/74779.htm

7. 单例模式

8. Excption 与 Error 区别

Error 表示系统级的错误和程序不必处理的异常，是恢复不是不可能但很困难的情况下的一种严重问题；比如内存溢出，不可能指望程序能处理这样的状况；

Exception 表示需要捕捉或者需要程序进行处理的异常，是一种设计或实现问题；也就是说，它表示如果程序运行正常，从不会发生的情况。
IllegalArgumentException();
NullPointerException();

try-catch-finally – database.close()

9. 子类能重写父类的构造函数吗

子类 不可以 重写 父类 的 构造方法，因为构造方法是父类特有的,子类根本继承不了父类的构造函数，所以子类不可以重写父类的构造方法。
但是可以使用关键字 super 调用父类的构造方法。

10. 怎么做出一个像淘宝那样每次打开都会给你推荐一些你可能喜欢的物品进行排序？【推荐算法】

11. 项目challenge

12. 个人经历

>
>
>
>

iterator

13. Collection

Interface(接口):	具体类	算法
Set
List	ArrayList/LinkedList	Collections()
Queue
Deque

Map –> Hashmap

├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
|-HashSet
|-LinkedHashSet
|-TreeSet
Map
├Hashtable
├HashMap
└WeakHashMap

List 必须保持元素特定的顺序
Set 不能有重复元素
Stack 先进后出
Map 一组成对的“键值对”对象

14. final

被final修饰的变量immutable
被 final 修饰的类不可继承 –> String
被 final 修饰的 field 不可修改
被 final 修饰的 method 不可重写

15. Interface & Abstract class

1. 一个类只能继承一个抽象类，而一个类却可以实现多个接口。
2. Interface没有具体实现，抽象类可以有。

16. http状态码

    1. 临时响应
    2. success
    3. 重定向
    4. error ： 404 get method
    5. 服务器error： 503 停机维护

17. get/post（√）

18. RestFul(√)

19. Session & Cookie（√）

20. JAVA多线程实现的三种方式

1、继承Thread类实现多线程

public class MyThread extends Thread {
　　public void run() {
　　 System.out.println("MyThread.run()");
　　}
　　
　　
　　MyThread myThread1 = new MyThread();
    MyThread myThread2 = new MyThread();
    myThread1.start();
    myThread2.start();

2. 实现Runnable接口方式实现多线程

    public class MyThread extends OtherClass implements Runnable {
    　　public void run() {
    　　 System.out.println("MyThread.run()");
    　　}
    }

    MyThread myThread = new MyThread();
    Thread thread = new Thread(myThread);
    thread.start();

    public void run() {
    　　if (target != null) {
    　　 target.run();
    　　}
    }


3. 使用ExecutorService、Callable、Future实现有返回结果的多线程

1. IOC （√）
2. AOP 以及动态代理

Message Queue

servlet是否是线程安全的

https://blog.csdn.net/ClementAD/article/details/50733042

#我的电面

NIO BIO

Exception

什么时候会自己定义一个exception？
继承什么类？

AOP

分布式session

Object类的method

    .clone()
    .toString()

HashTable 和ConcurrentHashMap区别

搜索引擎

B+ tree 为什么可以用来搜索

Array 和 List 区别

Abstract Class 和 Interface 区别

 要答全

• 面经