转载

【Java】几道常见的秋招面试题

只有光头才能变强

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？ www.zhihu.com/question/21…

一、char和varchar的区别

char是固定长度，varchar长度可变。varchar： 如果原先存储的位置无法满足其存储的需求 ，就需要一些额外的操作，根据存储引擎的不同，有的会采用 拆分机制 ，有的采用 分页机制 。
char的存储方式是：英文字符占1个字节，汉字占用2个字节；varchar的存储方式是： 英文和汉字都占用2个字节 ，两者的存储数据都非unicode的字符数据。
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
链接： www.jianshu.com/p/40078ed43…
來源：简书

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();


    }
}
复制代码

作者：我没有三颗心脏
链接： www.jianshu.com/p/3f0cd7af3…
來源：简书

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

使用阻塞队列解决生产者-消费者问题： www.cnblogs.com/chenpi/p/55…

四、算法[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线程不安全的体现： www.importnew.com/22011.html
jdk1.8 hashmap多线程put不会造成死循环: blog.csdn.net/qq_27007251…

六、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 垃圾收集器介绍：javadoop.com/post/g1

八、海量数据解决方案

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

Bloom filter布隆过滤器
- 适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
Hashing
- 适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存
bit-map
- 适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下
堆
- 适用范围：海量数据前n大，并且n比较小，堆可以放入内存
双层桶划分----其实本质上就是【分而治之】的思想，重在“分”的技巧上！
- 适用范围：第k大，中位数，不重复或重复的数字
数据库索引
- 适用范围：大数据量的增删改查
倒排索引(Inverted index)
- 适用范围：搜索引擎，关键字查询
外排序
- 适用范围：大数据的排序，去重
trie树
- 适用范围：数据量大，重复多，但是数据种类小可以放入内存
分布式处理 mapreduce
- 适用范围：数据量大，但是数据种类小可以放入内存

详细可参考原文：

十道海量数据处理面试题与十个方法大总结： blog.csdn.net/v_JULY_v/ar…

九、幂等性

9.1HTTP幂等性

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

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

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

参考资料：

GET和POST有什么区别？及为什么网上的多数答案都是错的。 www.cnblogs.com/nankezhishi…

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

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幂等性 www.cnblogs.com/weidagang20…
如何理解RESTful的幂等性 blog.720ui.com/2016/restfu…
浅谈HTTP中Get与Post的区别 www.cnblogs.com/hyddd/archi…
HTTP 请求中 POST 和 GET 请求的区别？ www.zhihu.com/question/27…

9.2接口幂等性

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

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

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

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

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