白小豆

V1

2023/03/10阅读:22主题:默认主题

如何精准拿捏面试官——字节跳动后端最新面试题解析

题目来源:https://www.nowcoder.com/discuss/462309993514094592?sourceSSR=users

1. Java 自动装箱和拆箱,优势

概念

自动装箱和拆箱是指Java编译器在基础数据类型和他们的包装类之间进行的自动转换,如int转为Integer,Double转为double等。基础数据类型转为包装类称之为装箱,包装类转为基础数据类型称之为拆箱。

基础数据类型和包装类

基础数据类型 包装类
byte Byte
short Short
int Integer
long Long
float Float
double Double
char Character
boolean Boolean

区别:基础数据类型存放在栈,引用数据类型存放在堆

如何实现

  • 自动装箱:包装类.valueOf
    • Integer i2 = Integer.valueOf(i1);
  • 自动拆箱:对象.xxValue
    • int i1 = i2.intValue();

优势

  • 节省代码量,保持代码简洁
  • 节省开发人员的精力,不用再关注基础类型和包装类的转换

2. 包装类的缓存

  • 前提:Java中比较对象值需要调用equals方法,如果直接使用==比较的是对象的地址,即是否是同一个对象
public class Test {
 public static void main(String[] args) {
        Integer i1 = 100;
        Integer i2 = 100;

        boolean flag1 = i1 == i2;

        System.out.println("i1 =?= i2 : " + flag1);

        Integer i3 = 200;
        Integer i4 = 200;

        boolean flag2 = i3 == i4;

        System.out.println("i3 =?= i4 : " + flag2);
    }
}

以Integer为例,Integer内部维护了一个缓存,存放着-128 ~ 127的所有Integer对象。当使用自动装箱或valueOf创建Integer对象时,如果创建的值位于[-128, 127]区间内,则将会直接引用缓存中的对象。使用==比较对象时,比较的是对象的地址,所以为true。如果创建的值在此区间之外,则会另外在堆中创建对象。

    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

3. 了解 JUC 的哪些方面

JUC是java.util.concurrent包的简称,在Java5.0中添加,目的是为了更好地支持Java中的并发任务。JUC包下包括atomic包、locks包、多种并发容器以及线程池相关类等。

atomic包

atomic包中的类可以帮助程序在多线程环境下,无锁地进行原子操作。Atomic包中的类多数都是通过Unsafe类来实现的,核心操作是CAS原子操作,效率比加锁高。

import org.apache.commons.lang3.time.StopWatch;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

public class TestAtomic {

    private static int num1 = 0;

    private static int num2 = 0;

    private static AtomicInteger num3 = new AtomicInteger(0);

    private static final int THREAD_NUM = 10000;

    public static void main(String[] args) throws Exception {
        StopWatch sw = new StopWatch();
        
        List<Thread> threads1 = new ArrayList<>();
        CountDownLatch latch1 = new CountDownLatch(THREAD_NUM);

        for (int i=0; i<THREAD_NUM; i++) {
            threads1.add(new Thread(() -> {
                for (int j=0; j<1000; j++) {
                    num1++;
                }
                latch1.countDown();
            }));
        }

        sw.start();
        threads1.forEach(Thread::start);
        latch1.await();

        sw.stop();
        System.out.printf("num1: %d, cost time: %d ns\n", num1, sw.getNanoTime());

        sw.reset();

        List<Thread> threads2 = new ArrayList<>();
        CountDownLatch latch2 = new CountDownLatch(THREAD_NUM);

        for (int i=0; i<THREAD_NUM; i++) {
            threads2.add(new Thread(() -> {
                for (int j=0; j<1000; j++) {
                    synchronized (TestAtomic.class{
                        num2++;
                    }
                }
                latch2.countDown();
            }));
        }

        sw.start();
        threads2.forEach(Thread::start);
        latch2.await();

        sw.stop();
        System.out.printf("num2: %d, cost time: %d ns\n", num2, sw.getNanoTime());

        sw.reset();

        List<Thread> threads3 = new ArrayList<>();
        CountDownLatch latch3 = new CountDownLatch(THREAD_NUM);

        for (int i=0; i<THREAD_NUM; i++) {
            threads3.add(new Thread(() -> {
                for (int j=0; j<1000; j++) {
                    num3.incrementAndGet();
                }
                latch3.countDown();
            }));
        }

        sw.start();
        threads3.forEach(Thread::start);
        latch3.await();

        sw.stop();
        System.out.printf("num3: %d, cost time: %d ns\n", num3.get(), sw.getNanoTime());
    }
}

locks包

locks包中的类是Java中常用的一些并发控制工具,面试中可以列举几个常用的类

ReentrantLock
  • CAS锁
  • 使用ReentrantLock可以完成和synchronized同样的功能,但需要注意的是,必须要手动释放锁
  • 使用synchronized关键字时,遇到异常,jvm会自动释放锁,但ReentrantLock必须手动释放,因此经常在finally中进行锁的释放。
  • 使用ReentrantLock可以进行“尝试锁定”,这样无法锁定或在执行时间内无法锁定时,线程可以执行不同的逻辑
  • 使用ReentrantLock可以调用lockInteruptibly方法,可以对线程interupt方法做出响应。在一个线程等待锁的过程中,可以被打断。
  • synchronized默认为不公平锁,Reentrantlock可以指定为公平锁,即谁处于等待队列的队头,谁得到锁
CountDownLatch
  • 门闩
  • 阻塞
  • 构造方法:new CountDownLatch(int count);
  • await()  阻塞
  • latch.countDown()  令count减1,直到count为0,阻塞放开
ReadWriteLock
  • 读写锁
  • 共享锁、排他锁
  • 写锁排他,读锁共享
  • 用于读多写少的场景,读线程访问时,上读锁,其他读线程可以访问,写线程不能访问。写线程访问时,其他写线程和读线程都不能访问

常用的并发容器

ConcurrentHashMap
  • 可以在并发情况下使用的Map,线程安全
  • 底层数据结构:1.7之前使用分段锁,1.8之后数组+链表+红黑树
  • 保证线程安全机制:1.7 之前采用 Segment 的分段锁机制实现线程安全,其中 Segment 继承自 ReentrantLock 。JDK1.8 采用 CAS+synchronized 保证线程安全。
  • 锁的粒度:JDK1.7 是对需要进行数据操作的 Segment 加锁,JDK1.8 调整为对每个数组元素加锁(Node)。
  • 链表转化为红黑树:定位节点的 hash 算法简化会带来弊端,hash 冲突加剧,因此在链表节点数量大于 8(且数据总量大于等于 64)时,会将链表转化为红黑树进行存储。
  • 查询时间复杂度:从 JDK1.7的遍历链表O(n), JDK1.8 变成遍历红黑树O(logN)
CopyOnWriteList
  • 写时复制
  • 读时不加锁,写时加锁。
  • 写的时候copy一份,加一格,放入新元素引用指向新List
BlockingQueue
  • void put(E e) throws InterruptedException;
    • 如果队列已满则阻塞
  • E take() throws InterruptedException;
    • 如果队列为空则阻塞
  • 最适合实现生产者消费者的容器
  • 通过Condition实现
    • await()
    • signal()
final ReentrantLock lock;

private final Condition notEmpty;

private final Condition notFull;

public ArrayBlockingQueue(int capacity, boolean fair) {
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull = lock.newCondition();
}

public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        // 队满
        while (count == items.length)
            notFull.await();
        enqueue(e);  // notEmpty.signal();
    } finally {
        lock.unlock();
    }
}

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
 lock.lockInterruptibly();
 try {
        while (count == 0)
            notEmpty.await();
        return dequeue();  // notFull.signal();
    } finally {
        lock.unlock();
    }

}

4. 可重入锁和非可重入锁

  • 不可重入锁:只会判断锁的状态,只要对象被锁,所有申请锁的线程都会被要求等待
  • 可重入锁:不仅记录锁的状态,还会记录持锁的线程。如果持锁线程还可以再次访问临界资源,此时锁的次数会+1
Lock lock = new ReentrantLock();
lock.lock();
lock.lock();
lock.unlock();
lock.unlock();

5. 为什么有可重入锁

可重入锁可以实现递归调用,不可重入锁在递归调用时会发生死锁。

6. 线程池有那些常用的参数

  • corePoolSize:核心线程数
  • maximumPoolSize:最大线程数
  • keepAliveTime:生存时间
    • 线程多长时间不工作,会归还给操作系统。但核心线程不会归还(可以通过参数指定是否归还:allowCoreThreadTimeOut
  • TimeUnit:时间单位
  • BlockingQueue:任务队列
    用不同的Queue存储的时候会产生不同的线程池
    • ArrayBlockingQueue:固定长度的阻塞队列
    • LinkedBlockingQueue:最大长度是Integer.MAX_VALUE
  • ThreadFactory:线程工厂,传入的参数必须implements ThreadFactory
    • Executors.defaultThreadFactory()
    • new CustomizableThreadFactory(".")
  • RejectedExecutionHandler:拒绝策略
    • 线程池忙,且任务队列满时,执行拒绝策略
    • 拒绝策略线程池默认提供四种
      • AbortPolicy:抛异常
      • DiscardPolicy:默默丢弃
      • DiscardOldestPolicy:丢弃任务队列中已等待时间最长的任务
      • CallerRunsPolicy:交付线程自己执行(谁提交的谁自己运行)
    • 还可以执行自定义策略(需要继承策略的接口),一般会保存到Kafka,Redis,DB

7. 核心线程数一般设置成多少(根据什么参考)

根据计算机CPU核数和任务类型,设N = CPU核数

  • 计算密集型:核心线程数 = N + 1
  • IO密集型:核心线程数 = N / (1 - 阻塞系数),阻塞系数一般取0.8 ~ 0.9,根据系统要求和表现不断调整

8. 什么决定并发量

  • 服务器网络带宽
  • 服务器内存
  • CPU性能
  • Web容器
  • 程序代码

9. 并发和并行

  • 并行:同一时刻有多条指令在CPU上同时执行
  • 并发:同一时刻只有一条指令在执行,但多个进程指令被快速轮换执行,使得在宏观上有多个进程同时执行的效果。
  • 并发和并行的目标都是最大化CPU的使用率,将cpu的性能充分压榨出来。但并行只能在多处理器系统中存在,并发可以在单处理器和多处理器系统中都存在

10. 线程池的最大线程数量

设 N = CPU核数

  • 计算密集型:最大线程数 = N + 1
  • IO密集型:最大线程数 = 2N + 1

11. 线程池中某个线程异常了怎么处理

  • 线程自身捕获异常
  • 线程工厂使用Thread.setUncaughtExceptionHandler设置线程自己的异常处理
  • 重写线程池的afterExecute方法

12. CAS能解决什么问题

在线程安全的解决方案中,synchronized,ReentrantLock等都是悲观锁,每次访问临界资源前都要加锁,线程拿到锁才可以运行,并发性下降。CAS是一种乐观锁的算法实现,并发量不大时性能要比悲观锁高得多。但线程数过多时会过分消耗CPU资源。

13. CAS 底层是通过什么实现的

CAS中包含了3个操作数:

  • 需要读写的变量值V
  • 更新前的期望值E
  • 需要写入的新值U

当且仅当V == E时,CAS通过原子方式用新值U更新V,否则不会执行任何操作
以AtomicInteger源码为例

 /**
  * var2:V
  * var5:E
     * var4 + var5:U
     */

 public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            // 获取期望值,赋值给var5
            var5 = this.getIntVolatile(var1, var2);
            // CAS,native方法 
            // var5 =?= var2 
            // var2 = var5+var4
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

14. CAS 能解决 ABA 的问题吗

  • ABA问题对基础数据类型没有影响
  • 最常用的解决办法是增加版本号机制,在引用数据类型中增加版本号、时间戳或校验码机制

15. 算法题:二叉树的右视图

算法思路

利用树的广度优先遍历的思想,使用队列。队列中首先是树的根节点,每次出队时将节点的左右子节点放入队列,并记录该层树的节点数量,如果判断节点是该层树的最右节点,则将其加入结果集合

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

欢迎关注微信公众号《写bug的白小豆》,获取互联网学习、编码、求职知识

分类:

后端

标签:

后端

作者介绍

白小豆
V1