【面试】字节一面

1. 自我介绍

2. LRU怎么实现、LFU呢？

   这两个都是LeetCode上的题，LFU还是个困难级别的。

   package bytedance;
   
   import java.util.HashMap;
   import java.util.Map;
   
   /**
    * @author woniu
    * @date 2022/5/6 16:55
    **/
   public class LRUCache {
   
   
       private int capacity;
   
       private int size;
   
       private Map cache;
   
       private Node head;
   
       private Node tail;
   
       public LRUCache(int capacity) {
           this.capacity = capacity;
           this.size = 0;
           cache = new HashMap<>();
           head = new Node();
           tail = new Node();
           head.next = tail;
           tail.pre = head;
       }
   
       public int get(int key) {
           Node node = cache.get(key);
           if (node == null) {
               return -1;
           }
           // 删节点
           node.next.pre = node.pre;
           node.pre.next = node.next;
           // 加到头部
           node.next = head.next;
           head.next.pre = node;
           node.pre = head;
           head.next = node;
           return node.value;
       }
   
       public void put(int key, int value) {
           if (cache.containsKey(key)) {
               Node node = cache.get(key);
               // 更新节点内容
               node.value = value;
               // 删除节点
               node.next.pre = node.pre;
               node.pre.next = node.next;
               // 添加到头部
               node.next = head.next;
               head.next.pre = node;
               node.pre = head;
               head.next = node;
   
           } else {
               Node node = new Node();
               node.value = value;
               node.key = key;
               // 添加到头部
               node.next = head.next;
               head.next.pre = node;
               head.next = node;
               node.pre = head;
               cache.put(key, node);
               size++;
               if (size > capacity) {
                   // 判断容量
                   System.out.println(tail.pre.key);
                   cache.remove(tail.pre.key);
                   tail.pre.pre.next = tail;
                   tail.pre = tail.pre.pre;
                   size--;
               }
           }
       }
   
   
       class Node {
           int key;
           int value;
           Node pre;
           Node next;
   
       }
   }
   

3. MySQL redo log 、undo log、binlog

​ redo log:

​ 是用来保证事务持久性的; 运行过程中不需要读取; innoDB引擎层; 记录物理格式日志, 对于每个页的修改. 随着事务的不断进行写入的.

​ undo log:

​ 是用来帮助回滚和MVCC *** 作的. 随时可能读写. innoDB引擎层.

​ binlog:

​ 主要用做主从复制. 是MySQL Server层产生, 对于Mysql的任何引擎的 *** 作都会记录. 记录是逻辑日志, 对应的SQL语句. 在commit提交完成后,一次性写入.

4. redis 是扩容时如何保证影响最小

首先，分两种情况，槽位没有迁移，槽位迁移中，槽位迁移完成

​ 槽位还未开始迁移

​ 接受到请求的节点，正常处理

​ 槽位迁移中或者已经迁移完成的槽位

​ 举例说明:如果槽位i， 正在节点7001向节点7002迁移，当前请求正好请求到了7001，会首先检查对应的key是否在自己的数据库中，发现并没有找到，然后检查clusterState.migrating_slots_to[i]，发现槽位i正在向7002迁移，则返回客户端ASK i 120.0.0.1:7002，这个错误表示客户端可以尝试到IP127.0.0.1:7002节点去执行关于槽位i的 *** 作。客户端会先向7002发送一个ASKING，然后再发送对应的命令。

5. 为什么ES会比MySQL快

​ 1）基于分词后的全文检索：例如select * from test where name like ‘%张三%’，对于mysql来说，因为索引失效，会进行全表检索；对es而言分词后，每个字都可以利用FST高速找到倒排索引的位置，并迅速获取文档id列表，大大的提升了性能，减少了磁盘IO。

​ 2）精确检索：进行精确检索，有些时候可能mysql要快一些，当mysql的非聚合索引引用上了聚合索引，无需回表，则速度上可能更快；es还是通过FST找到倒排索引的位置比获取文档id列表，再根据文档id获取文档并根据相关度进行排序。但是es还有个优势，就是es即天然的分布式能够在大量数据搜索时可以通过分片降低检索规模，并且可以通过并行检索提升效率，用filter时，更是可以直接跳过检索直接走缓。

6. 如果一篇博客需要存储并检索，怎么设计？

   目前仍为想到太好的方案, 当时面试时,提供的方案,是将博文信息存储在ES当中,但是面试官并不满意.没有深入.

7. 写一个SQL ， person标， id、name、sex、score 选出分数前三的人

   select * from person where score in (select score from person order by socre limit 3)
   

8. zk实现分布式锁的原理。 wal.

   zookeeper实现分布式锁的原理就是多个节点同时在一个指定的节点下面创建临时会话顺序节点，谁创建的节点序号最小，谁就获得了锁，并且其他节点就会监听序号比自己小的节点，一旦序号比自己小的节点被删除了，其他节点就会得到相应的事件，然后查看自己是否为序号最小的节点，如果是，则获取锁

9. 全排列 , 输入n， 输出全排列。 简化版，输入{1,2,3}, 输出全排列

import java.util.Arrays;

/**
 * 输入N， 输出全排列， 比如输入3， 输入123；132；213；231；312；321
 * @author woniu
 * @date 2022/5/6 16:41
 **/
public class Permutations {

    public void permutations(int n, int index) {
        // 用于存储当前数字是否被选中
        boolean[] flags = new boolean[n + 1];
        // 用于存储当前的路径
        int[] path = new int[n];

        permutations(flags, path, 0, n);
    }

    public void permutations(boolean[] flags, int[] path, int index, int n) {
        if (index == n) {
            System.out.println(Arrays.toString(path));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!flags[i]) {
                path[index] = i;
                flags[i] = true;
                permutations(flags, path, index+1, n);
                flags[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        new Permutations().permutations(4, 0);
    }
}

10. https的访问流程

https://blog.csdn.net/qq_24601199/article/details/104362401?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-104362401-blog-117336452.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-104362401-blog-117336452.pc_relevant_default&utm_relevant_index=1