携程笔试&面经整理

面试完没回答上来的

在并发编程中，如何确保i++的原子性

1
2
3

1.一般来说，可以使用syn关键字，将调用i++的方法修饰
2.使用 AtomicInteger 或 AtomicLong
AtomicInteger 和 AtomicLong 提供了原子性操作，适用于高并发环境。

死锁问题

主键索引和非主键索引的区别

1 2	主键索引列中的值唯一并且不为空，创建表的时候回自动创建非主键索引：列的值可以为空，需要手动创建，

创建数据库的时候，主键是怎么设计的，为什么要自增

1 2	主键一般选用uuID，自然主键等不会重复的自增的话就是，简单方便，因为自增的话，主键就不会重复了

一个数组取前K个较大的元素，说出你的算法思路

/*优先队列，最小堆
创建一个大小为K的最小堆（优先队列）。
遍历数组：将元素加入堆中，如果堆的大小超过K，则移除堆顶元素（即最小值）。
最终堆中的元素就是前K个最大的元素。*/

import java.util.PriorityQueue;

public List<Integer> findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return new ArrayList<>(minHeap);
}

String类型的方法，字符串匹配，indexof()底层是怎么实现的

字符串匹配
获取源字符串和目标子字符串的字符数组及长度。
从源字符串的起始位置开始，逐字符扫描，寻找与目标子字符串首字符匹配的位置。
一旦找到首字符匹配位置，逐字符比较源字符串和目标子字符串的剩余字符。
如果全部字符匹配成功，返回起始匹配位置索引；如果匹配失败，继续扫描源字符串。
若遍历完整个源字符串未找到匹配，返回 -1。

背包问题

二位动态规划

笔试1：一个正整数，取出所有的值为奇数的数字，按照原有的顺序拼成新的数，计算取模p的值

//思路：构建StringBuilder保存奇数字符串，用valueof转为数字，再%取模
package package6;

import java.math.BigInteger;
import java.util.*;
/**
 * @author
 * @date 2024/05/18 15:32
 **/
public class Main06 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String x = scanner.nextLine();
        int p = scanner.nextInt();

        StringBuilder sb = new StringBuilder();
        for(char c : x.toCharArray()){
            if((c-'0') % 2 != 0){
                sb.append(c);
            }
        }
        BigInteger bigInteger = new BigInteger(sb.toString());
        BigInteger bigInteger1 = BigInteger.valueOf(p);
        BigInteger mod = bigInteger.mod(bigInteger1);
        System.out.println(mod);
    }
}

笔试2：一个正整数，重排所有数位，不包含前导0，使其变成素数

//思路：
/*
使用HashSet<String> per存储所有可能的排列。
递归调用genarate方法生成所有可能的排列，并将它们添加到per集合中。
遍历per集合，将每个排列转换为整数，并检查它是否是质数。如果找到一个质数，将其赋值给res并跳出循环。
输出找到的最大质数res。*/

package package6;

import java.util.HashSet;
import java.util.Scanner;

/**
 * @author
 * @date 2024/05/20 19:18
 **/
public class Main07 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String x = scanner.next();
        scanner.close();

        HashSet<String> per = new HashSet<>();
        genarate("",x,per);

        int res = -1;
        for(String prem : per){
            int num = Integer.parseInt(prem);
            if(isPrime(num)){
                res = num;
                break;
            }
        }
        System.out.println(res);
    }

    private static boolean isPrime(int num) {
        if(num <=1) return false;
        if(num <=3) return true;
        if(num %2 == 0 || num%3 ==0) return false;
        for (int i = 5; i * i <=num; i+=6) {
            if(num % i == 0 || num % (i+2) == 0){
                return false;
            }
        }
        return true;
    }

    //prefix：当前已经生成的前缀字符串。
	//remaining：剩余未使用的字符组成的字符串。
	//per：存储所有排列的集合
    //递归的遍历去找到所有的可能
    private static void genarate(String prefix, String remaining, HashSet<String> per) {
        int n = remaining.length();
        if(n == 0){
            if(!prefix.startsWith("0"))
                per.add(prefix);
        }else {
            for (int i = 0; i <n; i++) {
                genarate(prefix+remaining.charAt(i),remaining.substring(0,i)+remaining.substring(i+1,n),per);
            }
        }
    }
}

笔试3：合并魔法球，每次合并两个魔力相等的魔法球K，生成一个K+2魔法球，合并到无法合并为止

输入：第一行n，接下来n行，每行两个数，表示每个球的魔力和数量

输出：m(表示魔法球最后数量)，pi（魔法球的魔力值，从小到大输出）

/*思路：因为要有序合并，考虑使用一个有序的map集合来保存，先分别将元素和元素个数存放进去
然后，while(tree)循环遍历消除相邻的大于2的，加入k+2的，保存到一个新的treemap中，并更新flag==true
如果没有大于2的，说明没有重复的了，就break退出循环，最后遍历输出即可
*/
public class Main08 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        TreeMap<Integer, Long> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int magicValue = scanner.nextInt();
            long count = scanner.nextLong();
            map.put(magicValue, map.getOrDefault(magicValue, 0L) + count);
        }
        scanner.close();
        while (true) {
            boolean merged = false;
            TreeMap<Integer, Long> newmap = new TreeMap<>();
            for (int key : map.keySet()) {
                Long value = map.get(key);
                if (value >= 2) {
                    long pairs = value / 2;
                    int newKey = key + 2;
                    newmap.put(newKey, newmap.getOrDefault(newKey, 0L) + pairs);
                    value = value % 2;
                    merged = true;
                }

                if (value == 1) {
                    newmap.put(key, newmap.getOrDefault(key, 0L) + 1);
                }
            }
            map = newmap;
            if (!merged) {
                break;
            }
        }
        System.out.println(map.size());
        for (int key : map.keySet()) {
            Long count = map.get(key);
            for (int i = 0; i < count; i++) {
                System.out.print(key + " ");
            }
        }
    }
}

笔试4：一棵树，每个节点上都有一个小写字母，选择一条路径，使得存在you三种字母，有多少种合法的路径

无向图，u->v和v->u是一样的

输入描述：

4
yuio
1 2
1 3
1 4

n，节点数量

youi字符串

u v 边链接

输出描述：合法路径的数量

//思路：深度优先遍历
public class Main09 {

    private static List<List<Integer>> tree;
    private static char[] letters;
    private static int count = 0;
    private static final int TRAGET_MASK = (1 << ('y' - 'a') | (1 << ('o' - 'a')) | (1 << ('u' - 'a')));

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String letterString = scanner.nextLine();

        letters = letterString.toCharArray();
        tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            tree.get(u).add(v);
            tree.get(v).add(u);
        }
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            dfs(i, visited, 0);
        }
        System.out.println(count / 2);
    }

    private static void dfs(int node, boolean[] visited, int mask) {
        if (visited[node]) return;
        visited[node] = true;
        mask |= 1 << (letters[node] - 'a');
        if ((mask & TRAGET_MASK) == TRAGET_MASK) {
            count++;
        }
        for (int neighbor : tree.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, mask);
            }
        }
        visited[node] = false;
    }
}

牛客上的面经

1.场景：缓存穿透的时候，写空值到Redis里面，如果我有个缓存穿透的线程，打入数据库（数据库中存在这条记录）的时候超时了，抛出异常，写入空值到缓存里面，用户下次访问拿到空值怎么解决？
区分不出这个空值是超时写入的还是不在数据库里面写入的了吗？

1
2
3

1.标记空值的原因：在缓存中写入空值的同时，用时间戳或者状态标记出来
2.使用不同的缓存过期时间：超时短，不存在的长
3.对超时的情况，异步重试

2.面向对象的三大特性，多态的好处，什么时候用到多态等

封装继承多态
封装：通过将数据和操作封装在类中，实现了信息隐藏和数据保护；
继承：允许子类继承父类的属性和方法，实现了代码重用和扩展；
多态：允许同一方法在不同对象上表现出不同行为，提高了代码的灵活性和扩展性。

多态性质：同一操作对不同的对象，有不同的解释，就是多态性（父类的引用指向子类的对象）
通过方法重写 override 或者方法重载

3.JVM相关知识，在JVM模块整理吧

4.ArrayList和LinkedList

都是list接口的实现类
ArrayList底层是数组，linkedList底层是链表
所以ArrayList查找效率高，插入删除效率低
LinkedList查找效率低，插入删除效率高

5.为什么ArrayList是线程不安全的，设计一个线程安全的ArrayList

因为ArrayList里面的add方法在添加的时候没有加锁
允许多个线程同时添加
所以可能会导致底层数组越界
解决方法就是，加锁，使用syconizied关键字修饰
或者使用古老实现类vector

6.手撕单例模式，（啊？不会）

1	确保一个类只有一个实例，并且提供一个全局访问点

7.volatile如何保证可见性的

volatile 关键字可以确保变量的可见性。
具体来说，当一个线程修改了 volatile 变量的值时，
其他线程能够立即看到这个修改的值，而不会使用缓存中的旧值。
这是因为 volatile 变量的写操作会立即被刷新到主内存中，
而读操作会从主内存中重新读取最新的值，从而确保了可见性。

8。手撕线程池（啊？不会）

线程池：管理线程的池子，可以容纳多个线程，省去了频繁创建线程的操作
Java中有几种常见的线程池，都是去实现了ThreadPoolExecutor这个类
用这个类的构造器，去设置参数，核心线程，最大线程，超时时长，任务队列等
可以直接用，然后重写run方法实现的


设计一个线程池嘛
1.创建N个线程
2.把任务提交给线程运行
3.线程满的话，就放入队列
4，空闲时，从队列去除执行

使用场景：异步处理的时候要用到线程池开启线程，并发处理的时候也需要

线程池的参数中最大线程数可以设得比核心线程数小吗

1
2
3

核心线程数是，线程中保持活跃的线程数
最大线程数是，允许的最大的可以扩的线程的数量
所以可以

9.了解过JIT嘛？（真不了解）

1	JIT编译：在运行的时候，将字节码编译成本地机器代码的技术

10.对于数组，怎么查询是否有重复元素

1	可以放到集合set或者map中去

11.HashMap介绍一下，key值可以设置为null吗？

HashMap是map的实现类，用来存储一对key-value数据
然后底层是数组+链表+红黑树的实现方式
先是创建数组，计算key的hashcode值存放
若存放的位置不为空，用链表存在后面
如果链表长度够长的话，转为红黑树提高查询效率

ConcurrentHashMap 怎么保证线程安全

HashMap是线程不安全的，因为put方法没有加锁，多线程下会不安全
解决方法就是加锁
如果对整个put方法加锁的话，就锁的颗粒度太大了
性能大大降低
分段锁：对数据结构分段加锁，降低锁的颗粒度

12.多线程同时操作一个数，有什么问题？怎么解决？

1.线程不安全问题，导致数据不一致，脏数据
解决方法：syn或者Lock加锁（syn不需要手动释放，Lock需要）
2.多个线程都等待对付释放资源而无法执行，造成死锁
解决：解决锁死锁，1.一次性锁定所有的资源 2.按顺序加锁

13.项目中的rabbitmq怎么保证消息一定发出去且收到了

1.消息持久化
2.生产者确认机制：
生产者可以采用发布确认模式（Publisher Confirm）来确保消息的可靠发送。
就是将信道设置为confirm模式，调用方法
在该模式下，生产者发送消息后，会等待 RabbitMQ 返回确认消息，
如果超时或者没有收到确认消息，则可以进行重发。

java创建线程的方式

1 2	继承Thread类，重写run方法，然后start来启动线程实现runnable接口：重写run方法，start实现

线程之间的通信方式

volatile关键字
JUC工具类
ThreadLocal类
ThreadLocal提供了线程局部变量功能，每个线程拥有独立的副本，解决了线程间共享变量的隔离问题。
实例表明即使多个线程引用同一个ThreadLocal实例，它们各自存储和获取的数据互不影响。

索引的类型

1	单例索引，多例索引，主键索引，唯一索引等

联合索引

它由多个列组成，可以同时对这些列进行排序和过滤。
联合索引的创建可以基于多个列，而不仅仅是单个列。
CREATE INDEX idx_student_grade ON students (student_id, grade);

反问：进公司要学习什么技术栈，对我的评价和建议

面试完没回答上来的

携程笔试&面经 整理

面试完没回答上来的

牛客上的面经

携程笔试&面经整理