前言

只有光头才能变强

Redis目前还在看，今天来分享一下我在秋招看过(遇到)的一些面试题(相对比较常见的)

0、final关键字

简要说一下final关键字，final可以用来修饰什么？

这题我是在真实的面试中遇到的，当时答得不太好，现在来整理一下吧。

final可以修饰类、方法、成员变量

• 当final修饰类的时候，说明该类不能被继承

• 当final修饰方法的时候，说明该方法不能被重写

  • 在早期，可能使用final修饰的方法，编译器针对这些方法的所有调用都转成内嵌调用，这样提高效率(但到现在一般我们不会去管这事了，编译器和JVM都越来越聪明了)

• 当final修饰成员变量时，有两种情况：

  • 如果修饰的是基本类型，说明这个变量的所代表数值永不能变(不能重新赋值)！
  • 如果修饰的是引用类型，该变量所的引用不能变，但引用所代表的对象内容是可变的！

值得一说的是：并不是被final修饰的成员变量就一定是编译期常量了。比如说我们可以写出这样的代码：private final int java3y = new Randon().nextInt(20);

你有没有这样的编程经验，在编译器写代码时，某个场景下一定要将变量声明为final，否则会出现编译不通过的情况。为什么要这样设计？

在编写匿名内部类的时候就可能会出现这种情况，匿名内部类可能会使用到的变量：

• 外部类实例变量
• 方法或作用域内的局部变量
• 方法的参数

class Outer {


    // string:外部类的实例变量
    String string = "";


    //ch:方法的参数
    void outerTest(final char ch) {

        // integer:方法内局部变量
        final Integer integer = 1;
        new Inner() {
            void innerTest() {
                System.out.println(string);
                System.out.println(ch);
                System.out.println(integer);
            }
        };

    }
    public static void main(String[] args) {
        new Outer().outerTest(' ');
    }
    class Inner {
    }
}

其中我们可以看到：方法或作用域内的局部变量和方法参数都要显示使用final关键字来修饰(在jdk1.7下)！

如果切换到jdk1.8编译环境下，可以通过编译的~

下面我们首先来说一下显示声明为final的原因：为了保持内部外部数据一致性

• Java只是实现了capture-by-value形式的闭包，也就是匿名函数内部会重新拷贝一份自由变量，然后函数外部和函数内部就有两份数据。
• 要想实现内部外部数据一致性目的，只能要求两处变量不变。JDK8之前要求使用final修饰，JDK8聪明些了，可以使用effectively final的方式

为什么仅仅针对方法中的参数限制final，而访问外部类的属性就可以随意

内部类中是保存着一个指向外部类实例的引用，内部类访问外部类的成员变量都是通过这个引用。

• 在内部类修改了这个引用的数据，外部类再获取时拿到的数据是一致的！

那当你在匿名内部类里面尝试改变外部基本类型的变量的值的时候，或者改变外部引用变量的指向的时候，表面上看起来好像都成功了，但实际上并不会影响到外部的变量。所以，Java为了不让自己看起来那么奇怪，才加了这个final的限制。

参考资料：

• java为什么匿名内部类的参数引用时final？https://www.zhihu.com/question/21395848

一、char和varchar的区别

1. char是固定长度，varchar长度可变。varchar：如果原先存储的位置无法满足其存储的需求，就需要一些额外的操作，根据存储引擎的不同，有的会采用拆分机制，有的采用分页机制。
2. char的存储方式是：英文字符占1个字节，汉字占用2个字节；varchar的存储方式是：英文和汉字都占用2个字节，两者的存储数据都非unicode的字符数据。
3. char是固定长度，长度不够的情况下，用空格代替。varchar表示的是实际长度的数据类型

选用考量：

• 如果字段长度较短和字符间长度相近甚至是相同的长度，会采用char字符类型

二、多个线程顺序打印问题

三个线程分别打印A，B，C，要求这三个线程一起运行，打印n次，输出形如“ABCABCABC....”的字符串。

原博主给出了4种方式，我认为信号量这种方式比较简单和容易理解，我这里粘贴一下(具体的可到原博主下学习)..

public class PrintABCUsingSemaphore {
    private int times;
    private Semaphore semaphoreA = new Semaphore(1);
    private Semaphore semaphoreB = new Semaphore(0);
    private Semaphore semaphoreC = new Semaphore(0);

    public PrintABCUsingSemaphore(int times) {
        this.times = times;
    }

    public static void main(String[] args) {
        PrintABCUsingSemaphore printABC = new PrintABCUsingSemaphore(10);

        // 非静态方法引用  x::toString   和() -> x.toString() 是等价的！
        new Thread(printABC::printA).start();
        new Thread(printABC::printB).start();
        new Thread(printABC::printC).start();

        /*new Thread(() -> printABC.printA()).start();
        new Thread(() -> printABC.printB()).start();
        new Thread(() -> printABC.printC()).start();
*/
    }

    public void printA() {
        try {
            print("A", semaphoreA, semaphoreB);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void printB() {
        try {
            print("B", semaphoreB, semaphoreC);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void printC() {
        try {
            print("C", semaphoreC, semaphoreA);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    private void print(String name, Semaphore current, Semaphore next)
            throws InterruptedException {
        for (int i = 0; i < times; i++) {
            current.acquire();
            System.out.print(name);
            next.release();
        }
    }
}

• 作者：cheergoivan
• 链接：https://www.jianshu.com/p/40078ed436b4
• 來源：简书

2018年9月14日18:15:36 yy笔试题就出了..

三、生产者和消费者

在不少的面经都能看到它的身影哈~~~基本都是要求能够手写代码的。

其实逻辑并不难，概括起来就两句话：

• 如果生产者的队列满了(while循环判断是否满)，则等待。如果生产者的队列没满，则生产数据并唤醒消费者进行消费。
• 如果消费者的队列空了(while循环判断是否空)，则等待。如果消费者的队列没空，则消费数据并唤醒生产者进行生产。

基于原作者的代码，我修改了部分并给上我认为合适的注释(下面附上了原作者出处，感兴趣的同学可到原文学习)

生产者：

import java.util.Random;
import java.util.Vector;
import java.util.concurrent.atomic.AtomicInteger;

public class Producer implements Runnable {

    // true--->生产者一直执行，false--->停掉生产者
    private volatile boolean isRunning = true;

    // 公共资源
    private final Vector sharedQueue;

    // 公共资源的最大数量
    private final int SIZE;

    // 生产数据
    private static AtomicInteger count = new AtomicInteger();

    public Producer(Vector sharedQueue, int SIZE) {
        this.sharedQueue = sharedQueue;
        this.SIZE = SIZE;
    }

    @Override
    public void run() {
        int data;
        Random r = new Random();

        System.out.println("start producer id = " + Thread.currentThread().getId());
        try {
            while (isRunning) {
                // 模拟延迟
                Thread.sleep(r.nextInt(1000));

                // 当队列满时阻塞等待
                while (sharedQueue.size() == SIZE) {
                    synchronized (sharedQueue) {
                        System.out.println("Queue is full, producer " + Thread.currentThread().getId()
                                + " is waiting, size：" + sharedQueue.size());
                        sharedQueue.wait();
                    }
                }

                // 队列不满时持续创造新元素
                synchronized (sharedQueue) {
                    // 生产数据
                    data = count.incrementAndGet();
                    sharedQueue.add(data);

                    System.out.println("producer create data:" + data + ", size：" + sharedQueue.size());
                    sharedQueue.notifyAll();
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
            Thread.currentThread().interrupted();
        }
    }

    public void stop() {
        isRunning = false;
    }
}

消费者：

import java.util.Random;
import java.util.Vector;

public class Consumer implements Runnable {

    // 公共资源
    private final Vector sharedQueue;

    public Consumer(Vector sharedQueue) {
        this.sharedQueue = sharedQueue;
    }

    @Override
    public void run() {

        Random r = new Random();

        System.out.println("start consumer id = " + Thread.currentThread().getId());
        try {
            while (true) {
                // 模拟延迟
                Thread.sleep(r.nextInt(1000));

                // 当队列空时阻塞等待
                while (sharedQueue.isEmpty()) {
                    synchronized (sharedQueue) {
                        System.out.println("Queue is empty, consumer " + Thread.currentThread().getId()
                                + " is waiting, size：" + sharedQueue.size());
                        sharedQueue.wait();
                    }
                }
                // 队列不空时持续消费元素
                synchronized (sharedQueue) {
                    System.out.println("consumer consume data：" + sharedQueue.remove(0) + ", size：" + sharedQueue.size());
                    sharedQueue.notifyAll();
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
            Thread.currentThread().interrupt();
        }
    }
}

Main方法测试：

import java.util.Vector;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Test2 {


    public static void main(String[] args) throws InterruptedException {

        // 1.构建内存缓冲区
        Vector sharedQueue = new Vector();
        int size = 4;

        // 2.建立线程池和线程
        ExecutorService service = Executors.newCachedThreadPool();
        Producer prodThread1 = new Producer(sharedQueue, size);
        Producer prodThread2 = new Producer(sharedQueue, size);
        Producer prodThread3 = new Producer(sharedQueue, size);
        Consumer consThread1 = new Consumer(sharedQueue);
        Consumer consThread2 = new Consumer(sharedQueue);
        Consumer consThread3 = new Consumer(sharedQueue);
        service.execute(prodThread1);
        service.execute(prodThread2);
        service.execute(prodThread3);
        service.execute(consThread1);
        service.execute(consThread2);
        service.execute(consThread3);

        // 3.睡一会儿然后尝试停止生产者(结束循环)
        Thread.sleep(10 * 1000);
        prodThread1.stop();
        prodThread2.stop();
        prodThread3.stop();

        // 4.再睡一会儿关闭线程池
        Thread.sleep(3000);

        // 5.shutdown()等待任务执行完才中断线程(因为消费者一直在运行的，所以会发现程序无法结束)
        service.shutdown();


    }
}

• 作者：我没有三颗心脏
• 链接：https://www.jianshu.com/p/3f0cd7af370d
• 來源：简书

另外，上面原文中也说了可以使用阻塞队列来实现消费者和生产者。这就不用我们手动去写wait/notify的代码了，会简单一丢丢。可以参考：

• 使用阻塞队列解决生产者-消费者问题：https://www.cnblogs.com/chenpi/p/5553325.html

四、算法[1]

我现在需要实现一个栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值，你会怎么做呢？你可以假设栈里面存的都是int整数

解决方案：

• 使用一个min变量来记住最小值，每次push的时候，看看是否需要更新min。

  • 如果被pop出去的是min，第二次pop的时候，只能遍历一下栈内元素，重新找到最小值。
  • 总结：pop的时间复杂度是O(n)，push是O(1),空间是O(1)

• 使用辅助栈来存储最小值。如果当前要push的值比辅助栈的min值要小，那在辅助栈push的值是最小值

  • 总结：push和pop的时间复杂度都是O(1)，空间是O(n)。典型以空间换时间的例子。

import java.util.ArrayList;
import java.util.List;

public class MinStack {

    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> mins = new ArrayList<Integer>();

    public void push(int num) {
        data.add(num);
        if (mins.size() == 0) {
            // 初始化mins
            mins.add(num);
        } else {
            // 辅助栈mins每次push当时最小值
            int min = getMin();
            if (num >= min) {
                mins.add(min);
            } else {
                mins.add(num);
            }
        }
    }

    public int pop() {
        // 栈空，异常，返回-1
        if (data.size() == 0) {
            return -1;
        }
        // pop时两栈同步pop
        mins.remove(mins.size() - 1);
        return data.remove(data.size() - 1);
    }

    public int getMin() {
        // 栈空，异常，返回-1
        if (mins.size() == 0) {
            return -1;
        }
        // 返回mins栈顶元素
        return mins.get(mins.size() - 1);
    }

}

继续优化：

• 栈为空的时候，返回-1很可能会带来歧义(万一人家push进去的值就有-1呢？)，这边我们可以使用Java Exception来进行优化

• 算法的空间优化：上面的代码我们可以发现：data栈和mins栈的元素个数总是相等的，mins栈中存储几乎都是最小的值(此部分是重复的!)

  • 所以我们可以这样做：当push的时候，如果比min栈的值要小的，才放进mins栈。同理，当pop的时候，如果pop的值是mins的最小值，mins才出栈，否则mins不出栈！
  • 上述做法可以一定避免mins辅助栈有相同的元素！

但是，如果一直push的值是最小值，那我们的mins辅助栈还是会有大量的重复元素，此时我们可以使用索引(mins辅助栈存储的是最小值索引，非具体的值)！

最终代码：

import java.util.ArrayList;
import java.util.List;


public class MinStack {

    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> mins = new ArrayList<Integer>();

    public void push(int num) throws Exception {
        data.add(num);
        if(mins.size() == 0) {
            // 初始化mins
            mins.add(0);
        } else {
            // 辅助栈mins push最小值的索引
            int min = getMin();
            if (num < min) {
                mins.add(data.size() - 1);
            }
        }
    }

    public int pop() throws Exception {
        // 栈空，抛出异常
        if(data.size() == 0) {
            throw new Exception("栈为空");
        }
        // pop时先获取索引
        int popIndex = data.size() - 1;
        // 获取mins栈顶元素，它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        // 如果pop出去的索引就是最小值索引，mins才出栈
        if(popIndex == minIndex) {
            mins.remove(mins.size() - 1);
        }
        return data.remove(data.size() - 1);
    }

    public int getMin() throws Exception {
        // 栈空，抛出异常
        if(data.size() == 0) {
            throw new Exception("栈为空");
        }
        // 获取mins栈顶元素，它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        return data.get(minIndex);
    }

}

参考资料：

• 【面试现场】如何实现可以获取最小值的栈？
• 作者：channingbreeze 出处： 互联网侦察

五、多线程下的HashMap

众所周知，HashMap不是一个线程安全的类。但有可能在面试的时候会被问到：如果在多线程环境下使用HashMap会有什么现象发生呢？？

结论：

• put()的时候导致的多线程数据不一致(丢失数据)

• resize()操作会导致环形链表

  • jdk1.8已解决环链的问题(声明两对指针，维护两个连链表)
• fail-fast机制，对当前HashMap同时进行删除/修改会抛出ConcurrentModificationException异常

参考资料：

• 谈谈HashMap线程不安全的体现：http://www.importnew.com/22011.html
• jdk1.8 hashmap多线程put不会造成死循环:https://blog.csdn.net/qq_27007251/article/details/71403647

六、Spring和Springboot区别

一、SpringBoot是能够创建出独立的Spring应用程序的

二、简化Spring配置

• Spring由于其繁琐的配置，一度被人成为“配置地狱”，各种XML、Annotation配置，让人眼花缭乱，而且如果出错了也很难找出原因。

• Spring Boot项目就是为了解决配置繁琐的问题，最大化的实现convention over configuration(约定大于配置)。

  • 提供一系列的依赖包来把其它一些工作做成开箱即用其内置一个’Starter POM’，对项目构建进行了高度封装，最大化简化项目构建的配置。

三、嵌入式Tomcat，Jetty容器，无需部署WAR包

七、G1和CMS

G1收集器的设计目标是取代CMS收集器，它同CMS相比，在以下方面表现的更出色：

• G1是一个有整理内存过程的垃圾收集器，不会产生很多内存碎片。

  • CMS采用的是标记清除垃圾回收算法，可能会产生不少的内存碎片
• G1的Stop The World(STW)更可控，G1在停顿时间上添加了预测机制，用户可以指定期望停顿时间。

拓展阅读：

• G1 垃圾收集器介绍：https://javadoop.com/post/g1

八、海量数据解决方案

海量数据的处理也是一个经常考的知识点，无论在面试还是在笔试中都是比较常见的。有幸读了下面的文章，摘录了一些解决海量数据的思路：

• Bloom filter布隆过滤器

  • 适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

• Hashing

  • 适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

• bit-map

  • 适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

• 堆

  • 适用范围：海量数据前n大，并且n比较小，堆可以放入内存

• 双层桶划分----其实本质上就是【分而治之】的思想，重在“分”的技巧上！

  • 适用范围：第k大，中位数，不重复或重复的数字

• 数据库索引

  • 适用范围：大数据量的增删改查

• 倒排索引(Inverted index)

  • 适用范围：搜索引擎，关键字查询

• 外排序

  • 适用范围：大数据的排序，去重

• trie树

  • 适用范围：数据量大，重复多，但是数据种类小可以放入内存

• 分布式处理 mapreduce

  • 适用范围：数据量大，但是数据种类小可以放入内存

详细可参考原文：

• 十道海量数据处理面试题与十个方法大总结：https://blog.csdn.net/v_JULY_v/article/details/6279498

九、幂等性

9.1HTTP幂等性

昨天去做了一套笔试题，经典的HTTP中get/post的区别。今天回来搜了一下，发现跟之前的理解有点出入。

如果一个人一开始就做Web开发，很可能把HTML对HTTP协议的使用方式，当成HTTP协议的唯一的合理使用方式。从而犯了以偏概全的错误

单纯以HTTP协议规范来说，可能我们之前总结出的GET/POST区别就没用了。(但通读完整篇文章，我个人认为：如果面试中有GET/POST区别，还是默认以Web开发场景下来回答较好，这也许是面试官想要的答案)

参考资料：

• GET和POST有什么区别？及为什么网上的多数答案都是错的。http://www.cnblogs.com/nankezhishi/archive/2012/06/09/getandpost.html

---

其中也学习到了幂等性这么一个概念，于是也做做笔记吧~~~

Methods can also have the property of “idempotence” in that (aside from error or expiration issues) the side-effects of N > 0 identical requests is the same as for a single request.

从定义上看，HTTP方法的幂等性是指一次和多次请求某一个资源应该具有同样的副作用。

• 这里简单说一下“副作用”的意思：指当你发送完一个请求以后，网站上的资源状态没有发生修改，即认为这个请求是无副作用的

HTTP的GET/POST/DELETE/PUT方法幂等的情况：

• GET是幂等的，无副作用

  • 比如我想要获得订单ID为2的订单：http://localhost/order/2，使用GET多次获取，这个ID为2的订单(资源)是不会发生变化的！

• DELETE/PUT是幂等的，有副作用

  • 比如我想要删除或者更新ID为2的订单：http://localhost/order/2，使用PUT/DELETE多次请求，这个ID为2的订单(资源)只会发生一次变化(是有副作用的)！但继续多次刷新请求，订单ID为2的最终状态都是一致的

• POST是非幂等的，有副作用的

  • 比如我想要创建一个名称叫3y的订单：http://localhost/order，使用POST多次请求，此时可能就会创建多个名称为3y的订单,这个订单(资源)是会多次变化的，每次请求的资源状态都会变化！

题外话：

HTTP协议本身是一种面向资源的应用层协议，但对HTTP协议的使用实际上存在着两种不同的方式：一种是RESTful的，它把HTTP当成应用层协议，比较忠实地遵守了HTTP协议的各种规定(充分利用了HTTP的方法)；另一种是SOA的，它并没有完全把HTTP当成应用层协议，而是把HTTP协议作为了传输层协议，然后在HTTP之上建立了自己的应用层协议

参考资料：

• 理解HTTP幂等性http://www.cnblogs.com/weidagang2046/archive/2011/06/04/2063696.html#!comments
• 如何理解RESTful的幂等性http://blog.720ui.com/2016/restful_idempotent/
• 浅谈HTTP中Get与Post的区别http://www.cnblogs.com/hyddd/archive/2009/03/31/1426026.html
• HTTP 请求中 POST 和 GET 请求的区别？https://www.zhihu.com/question/27622127/answer/37676304

9.2接口幂等性

在查阅资料的时候，可以发现很多博客都讲了接口的幂等性。从上面我们也可以看出，POST方法是非幂等的。但我们可以通过一些手段来令POST方法的接口变成是幂等的。

说了那么多，那接口设计成幂等的好处是什么？？？？

举个例子说一下非幂等的坏处：

• 3y大一的时候是要抢体育课的，但学校的抢课系统做得贼烂(延迟很高)。我想要抢到课，就开了10多个Chrome标签页去抢(即使某个Chrome标签页崩了，我还有另外的Chrome标签页是可用的)。我想抢到乒乓球或者羽毛球。
• 抢课时间一到，我就轮着点击我要想抢的乒乓球或者羽毛球。如果系统设计得不好，这个请求是非幂等的(或者说事务控制得不好)，我手速足够快&&网络足够好，那我很可能抢到了多次乒乓球或者羽毛球的课程了。(这是不合理的，一个人只能选一门课，而我抢到了多门或者多次重复的课)
• 涉及到商城的应用场景可能就是：用户下了多个重复的订单了

如果我的抢课接口是幂等的话，那就不会出现这个问题了。因为幂等是多次请求某一个资源应该具有同样的副作用。

• 在数据库后台最多只会有一条记录，不存在抢到多门课的现象了。

说白了，设计幂等性接口就是为了防止重复提交的(数据库出现多条重复的数据)！

网上有博主也分享了几条常见解决重复提交的方案：

1. 同步锁（单线程，在集群可能会失效）
2. 分布式锁如redis（实现复杂）
3. 业务字段加唯一约束（简单）
4. 令牌表+唯一约束（简单推荐）---->实现幂等接口的一种手段
5. mysql的insert ignore或者on duplicate key update（简单）
6. 共享锁+普通索引（简单）
7. 利用MQ或者Redis扩展（排队）
8. 其他方案如多版本控制MVCC 乐观锁 悲观锁 状态机等。。

参考资料：

• 分布式系统接口幂等性http://blog.brucefeng.info/post/api-idempotent
• 如何避免下重复订单https://www.jianshu.com/p/e618cc818432
• 关于接口幂等性的总结https://www.jianshu.com/p/6eba27f8fb03
• 使用数据库唯一键实现事务幂等性http://www.caosh.me/be-tech/idempotence-using-unique-key/
• API接口非幂等性问题及使用redis实现简单的分布式锁https://blog.csdn.net/rariki/article/details/50783819

最后

如果以上有理解错的地方，或者说有更好的理解方式，希望大家不吝在评论区下留言。共同进步！

可能感兴趣的链接：

• 文章的目录导航(微信公众号端)：https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang
• 文章的目录导航(PC端)：http://www.zhongfucheng.bitcron.com/post/shou-ji/pcduan-wen-zhang-dao-hang
• 海量精美脑图：http://www.zhongfucheng.bitcron.com/post/shou-ji/nao-tu-da-quan