[数据结构与算法]实战实战实战

阿里

1、SpringBoot与Spring区别

2、Aop应用

3、服务治理

4、微服务划分

5、微服务调用

6、10个线程实现10000个数的相加

// 使用countDownLatch
public class CalculateThread {
    private int[] sum = new int[10];
    public void calculate(int start, int sumIndex, CountDownLatch countDownLatch) {
        for (int i = start; i< start+100; i++) {
            sum[sumIndex] += i;
        }
        countDownLatch.countDown();
    }
    public int getSum() {
        int ret = 0;
        for (int i =0; i<sum.length; i++) {
            ret+= sum[i];
        }
        return ret;
    }
    public static void main(String[] args) {
        CountDownLatch countDownLatch = new CountDownLatch(10);
        CalculateThread calculateThread = new CalculateThread();
        for (int i = 0;i < 10; i++) {
            final int j = i;
            new Thread(new Runnable() {
                @Override
                public void run() {
                    calculateThread.calculate(j * 100, j, countDownLatch);
                }
            }).start();
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println(calculateThread.getSum());
    }
}

8、两个不同长度的链表相交，求交点

• A长度为 a, B长度为b， 假设存在交叉点，此时 A到交叉点距离为 c， 而B到交叉点距离为d
• 后续交叉后长度是一样的，那么就是 a-c = b-d -> a+d = b+c
• 这里意味着只要分别让A和B额外多走一遍B和A，那么必然会走到交叉，最后为交叉点为空说明两个没交叉，最后交叉点不为空则说明有交叉
  

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currentA = headA;
        ListNode currentB = headB;
        while (currentA != currentB) {
           currentA = currentA == null ? headB : currentA.next;
            currentB = currentB == null ? headA : currentB.next;
        }
        return currentA; 
    }
}

快手

1、静态内部类和内部类的区别

• 可以对比静态属性和非静态属性来理解

• 内部类

  • 内部类可以无条件访问外部类的属性和方法(包括私有的)，外部类在访问内部属性和方法时必须先创建一个实例
  • 创建内部类实例的时候必须先创建一个外部类实例
  • 内部类不能定义static元素和方法，但是允许static final常量

• static 内部类

  • 是内部类的一个特例，一旦内部类被static修饰则该类变成了顶层类，只能访问外部类的静态属性和方法
  • 可以直接创建静态内部类的实例
  • 可以在内部定义static元素

2、LinkedList的底层实现是啥， ArrayList的底层实现，两者各自优缺点

• linkedList底层实现是双向链表，内部主要维护first和last两个节点，非哨兵节点，插入删除效率高，索引方式查找时会判断index是否大于链表长度的一半，如果大于从后向前找，如果小于从0向后找
• ArrayList底层是一个数组，默认初始化大小是10，当添加元素达到数组现有大小后会按1.5倍来扩容，并拷贝原来的数据
• linkedList插入和删除元素效率很高，只需要修改链表元素的指针即可，而ArrayList需要整体移动元素，效率很低
• ArrayList按索引查询时效率比LinkedList高

3、MySql为什么习惯用自增序列作为主键

innoDB存储引擎在选择聚簇索引时的顺序是这样的：如果有主键选用主键，如果没有选用唯一且非空的字段作为聚簇索引，如果都没有则自己生成一个Row_ID作为聚簇索引，使用自增序列不使用uuid是这样考虑的：

• uuid是一般字符串比较长，比较占用空间
• 自增序列插入效率高：插入数据可以顺序写入；如果不是自增的，则可能导致大量页分裂和页移动，还有可能写入的目标页已经写入到磁盘中而不仅仅是在内存中，又或者目标页还没有被加载到内存中，这样会导致IO操作，效率低下

4、手写一个阻塞队列

// 参考：https://zhuanlan.zhihu.com/p/64156753
public class BlockQueue {
    private List<String> dataContainer;
    private int size;
    private Lock lock = new ReentrantLock();
    private Condition condition = lock.newCondition();
    public BlockQueue(int size) {
        this. size = size;
        dataContainer = new LinkedList<>();
    }
    public void put(String element) {
        lock.lock();
        try {
            while (dataContainer.size() >= size) {
                condition.await();
            }
            dataContainer.add(element);
            condition.signalAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
    public String pop() {
        lock.lock();
        String element = null;
        try {
            while (dataContainer.size() == 0) {
                condition.await();
            }
            element = dataContainer.get(0);
            dataContainer.remove(0);
            condition.signalAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        finally {
            lock.unlock();
        }
        return element;
    }
}

4、谈谈你对泛型的理解

• 泛型即参数化类型， 分为 泛型类、泛型方法、泛型接口, 泛型类型变量不能是基本数据类型，因为擦除后是以Object代替原来的类型T的

• 泛型只在编译阶段有效，编译时先检查代码中泛型的类型，编译之后程序会擦除泛型，泛型信息不会进入到运行时阶段,因此我们可以利用反射来给我们定义好的list添加任意类型的元素

   public static void main(String args[]) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
          ArrayList<Integer> array=new ArrayList<Integer>();
          // 这样调用add方法只能存储整形，因为泛型类型的实例为Integer
          array.add(1);
          // 通过泛型可以突破泛型类型约束
          array.getClass().getMethod("add", Object.class).invoke(array, "asd");
          for (int i=0;i<array.size();i++) {
              System.out.println(array.get(i));
              // 如果这里这样定义, 会报类型转换的错误，编译器在这里自动插入int的强制类型转换
              // int a = array.get(i);
          }
    // 这段代码不会报任何的错
   }
  

• PECS原则(Producer Extends Consumer Super)

  • 频繁往外读取内容的，适合用上界Extends。
  • 经常往里插入的，适合用下界Super。

• 参考文章:

  • https://blog.csdn.net/sunxianghuang/article/details/51982979
  • https://segmentfault.com/a/1190000005179142