秋招知识点

1、一致性哈希结构

解决分布式系统，分发定位，节点增删，大量数据迁移的问题

将hash值（Int类型0~MAX）映射到圆形数轴，逆时针递增
当节点加入分布式系统时，计算节点的hash，放入数轴
当数据/请求过来，计算其节点值，放入数轴
数据hash值沿着顺时针的方向遇到的第一个节点，就是其定位的节点
为了解决分布不均匀的问题可以使用虚拟节点

2、MySql Join执行与优化

参考1 参考2

Inner Join
- 在MySql中其执行与书写的顺序无关，MySql会进行相关的优化：
- 小表驱动大表
- 在连接阶段考虑where条件
Outer Join
- 尽量不要使用
- 驱动表为from后面的表
- 执行分两个阶段，先执行on进行连接，然后才能使用where进行过滤
- 所以有一种优化，将where过滤写在on子句中减少连接表大小（where中的语句也要存在，因为：on语句和where语句的区别）

3、synchronized与Lock的区别

参考

synchronized
- 同步控制由虚拟机实现，在Hotspot中由ObjectMonitor实现。
- ObjectMonitor与被锁对象关联，用户不可感知
- 最终都是调用底层part方法实现线程阻塞
- 使用更加一致性
Lock
- 同步控制由Java实现java.util.concurrent.locks.AbstractQueuedSynchronizer（AQS）
- 线程阻塞由Parker对象实现（C++实现），依赖底层mutex，condition
- Parker与线程关联
- 更细粒度的控制，如：手动请求释放锁、可以获得锁状态、可以非阻塞尝试获得锁、可设置公平非公平

本质区别，一个同步控制由虚拟机实现（不可感知），一个由Java实现（可感知）

4、快排实现

private static boolean isEmpty(int[] n) {
        return n == null || n.length == 0;
    }

    // ///////////////////////////////////////////////////
    /**
     * 快速排序算法思想——挖坑填数方法：
     *
     * @param n 待排序的数组
     */
    public static void quickSort(int[] n) {
        if (isEmpty(n))
            return;
        quickSort(n, 0, n.length - 1);
    }

    public static void quickSort(int[] n, int l, int h) {
        if (isEmpty(n))
            return;
        if (l < h) {
            int pivot = partion(n, l, h);
            quickSort(n, l, pivot - 1);
            quickSort(n, pivot + 1, h);
        }
    }

    private static int partion(int[] n, int start, int end) {
        int tmp = n[start];
        while (start < end) {
            while (n[end] >= tmp && start < end)
                end--;
            if (start < end) {
                n[start++] = n[end];
            }
            while (n[start] < tmp && start < end)
                start++;
            if (start < end) {
                n[end--] = n[start];
            }
        }
        n[start] = tmp;
        return start;
    }

5、全文索引、倒排索引、搜索引擎

全文索引和搜索引擎一般都会依赖倒排索引。

（1）倒排索引理解

倒排索引和普通的索引没有什么原理区别，主要区别在语义上的限制。一般的索引都是一个id（数字），我们会根据id查找内容。

倒排索引是根据关键字查找id的过程

（2）例子

数据库中由n篇中文文章。现在要求实现文章内容的快速搜索，文章存在article(id, content)表中

实现方式1：使用sql like语句

这张方案不可能用于生产环境。原因在于，利用不到索引，相当于暴力求解。时间复杂度为O(n)

实现方式2：使用倒排索引

对每个文章进行分词，将每个提取出来的词汇和文章id放入数据库的索引表中，简单方式 word2article(word, articleIds)， articlesId是一个字符串，存放着文章id列表，比如1,3,5

比较好的设计：

word(id, word)
word2article(wordId, articleId)

这样查询就可以按照索引进行可以达到O(logn)

（3）全文索引

全文索引的底层实现就是倒排索引

MySQL 5.7.6开始，MySQL内置了ngram全文检索插件，用来支持中文分词，并且对MyISAM和InnoDB引擎有效

创建方式

FULLTEXT(title, body)
ALTER TABLEstudentADD FULLTEXT INDEX ft_stu_name (name)

使用全文索引

WHERE MATCH(columnName) AGAINST('string')

默认分词级别配置

[mysqld]
ngram_token_size=2

（4）搜索引擎

搜索引擎的核心之一也是倒排所用

6、一个圆上三个点形成钝角的概率是多少

思路：

任意一个圆内三角形必然有一个点所在的角是最大的，以这个点为基准点A（或称角A）考虑B、C（角B、角C）点的分布
因为A角最大，所以BA或CA组成的圆心角的范围为分别为120度。所以BC组成的圆心角为230度
若ABC为钝角三角形，则BC组成的圆心角的取值范围为0到180度，若三角形为锐角圆心角的取值范围为180到230度
所以
- 钝角三角形概率为 180/230 = 3/4
- 锐角三角形概率为 (230-180)/230 = 1/4

7、Java spi机制

全称为 (Service Provider Interface) ，是JDK内置的一种服务提供发现机制。

实现步骤

定义好接口
实现接口
在META-INF/services/目录下添加名字为接口全名的文件，此文件包含一行：此接口实现的类全名
使用java.util.ServiceLoader即可创建实例

用途

JDBC的实现包含相关内容，不使用Class.forName即可获得连接
SpringMVC实现无web.xml启动

spi与api区别

spi与api是一个级别的概念
api是类库，第三方提供的已经实现的代码
spi是标准，标准与实现的关联使用spi内容机制实现

8、ClassLoader

参考

类加载机制
可自定义类加载器从某些地方动态加载类
推荐使用双亲委托机制
- 实现方式：
  - 组合，每个类加载器包含一个parent指向父加载
  - 当调用loadClass时，首先调用parent的loadClass
  - loadClass定义在ClassLoader中，不建议覆写
ClassLoader抽象类
- loadClass(String)，实现双亲委派机制，不建议覆写。
- findClass(String)，若父亲无法加载类，将调用此方法加载类；自定义类加载器主要覆写的方法
- defineClass(byte[] b, int off, int len)，调用本地方法，将一段字节转换为Class对象（加载到虚拟机）
sun.misc.Launcher 包含 ExtClassLoader 和 AppClassLoader的初始化过程
双亲委派模型的破坏者-线程上下文类加载器
- 如SPI实现，SPI核心类由Bootstrap类加载器加载。但是SPI实现在第三方的包内，Bootstrap找不到，所以只能通过Thread.getContextClassLoader()加载
类加载器与安全管理器、访问控制器相关

例子

package cn.rectcircle.test;

import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;

public class App {

	public static void main(String[] args) throws ClassNotFoundException {
		String rootDir = "D:\\learn\\Test";

		FileClassLoader loader1 = new FileClassLoader(rootDir);
		Class<?> pc1 = loader1.loadClass("Person");
		System.out.println(pc1.getClassLoader());


	}
}

class FileClassLoader extends ClassLoader {
	private String rootDir;

	public FileClassLoader(String rootDir) {
		this.rootDir = rootDir;
	}

	/**
	 * 编写findClass方法的逻辑
	 *
	 * @param name
	 * @return
	 * @throws ClassNotFoundException
	 */
	@Override
	protected Class<?> findClass(String name) throws ClassNotFoundException {
		// 获取类的class文件字节数组
		byte[] classData = getClassData(name);
		if (classData == null) {
			throw new ClassNotFoundException();
		} else {
			// 直接生成class对象
			return defineClass(name, classData, 0, classData.length);
		}
	}

	/**
	 * 编写获取class文件并转换为字节码流的逻辑
	 *
	 * @param className
	 * @return
	 */
	private byte[] getClassData(String className) {
		// 读取类文件的字节
		String path = classNameToPath(className);
		try {
			InputStream ins = new FileInputStream(path);
			ByteArrayOutputStream baos = new ByteArrayOutputStream();
			int bufferSize = 4096;
			byte[] buffer = new byte[bufferSize];
			int bytesNumRead = 0;
			// 读取类文件的字节码
			while ((bytesNumRead = ins.read(buffer)) != -1) {
				baos.write(buffer, 0, bytesNumRead);
			}
			return baos.toByteArray();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return null;
	}

	/**
	 * 类文件的完全路径
	 *
	 * @param className
	 * @return
	 */
	private String classNameToPath(String className) {
		return rootDir + File.separatorChar + className.replace('.', File.separatorChar) + ".class";
	}
}

9、高并发、高流量处理方式

（1）高并发处理

前后端分离
前台
- 静态资源使用CDN，缓存技术
后台开发
- 使用异步方式
- 资源池化（线程池、连接池）
- 负载均衡+多实例多机器
- 使用缓存、中间件
- 分库分表
- 分布式数据库

（2）高流量处理

拒绝服务（指向错误页面）
排队或等待
降级（返回兜底数据或默认数据，如商品详情页库存默认有货）
限流
- 限制总并发数
- 限制瞬时并发数
- 限制时间窗口内的平均速率
- 其他还有如限制远程接口调用速率、限制MQ的消费速率
- 还可以根据网络连接数、网络流量、CPU或内存负载等来限流

10、消息中间件

（1）如何保证幂等性

消息可能出现重复，所以需要在消费者处理时保证

使用全局唯一个id作保证

去重方案

（2）有序消息如何处理

方式1

使用路由协议保证同一id的被发送到同一个队列

方式2

使用通知机制

（3）push 与 pull

push （推送）：发布订阅，消息队列主动推送消息到消费者，此时需要在消息服务和消费者之间保持一个长连接
pull （拉取）：轮询，消费者轮询消息队列

如何选择

场景1：Producer 的速率大于 Consumer 的速率
- Push 将导致消费者负载加剧
- Pull 只需控制好轮询频率
场景2：强调消息的实时性
- push 实时性好
- pull 实时性差
场景3：Pull 的长轮询
- 当pull请求没有数据，连接将保持直到有数据
场景4：部分或全部Consumer不在线
- Push 无法预知 Consumer 状态，对堆积数据难以处理
- Pull 消息队列不在关心 Consumer 状态

11、LRUCache实现

算法描述：

一个容器，容器容量有界（固定），当容器满了，插入元素时，淘汰最久未访问的元素
- 元素被访问的情况下
  - 元素第一次被插入
  - 元素被更新
  - 元素被读取
两个基本操作：
- put(k, v)添加元素
- get(k) 从缓存中获取元素

实现思路

元素放在一个队列中
当元素被访问时将元素插入（移动）到队首
若容器满，删除队尾元素

为了加速访问，为元素建立hash索引

import java.util.HashMap;
import java.util.Map;


class LRUCache <K, V> {
	private final int capacity;
	private final Map<K, Node<K, V>> map;
	private final Node<K, V> head; // 带头结点的双向循环链表

	public LRUCache(int capacity){
		this.capacity = capacity;
		this.map = new HashMap<>(capacity);
		head = new Node<>();
	}

	public V get(K key){
		Node<K, V> node = map.get(key);
		if(node == null){
			return null;
		}
		moveToFirst(node);
		return node.value;
	}

	public void put(K key, V value){
		Node<K, V> node = map.get(key);
		if(node != null){ //更新
			// 更新不改变LRU的顺序
			node.value = value;
			// 更新改变LRU顺序，打开以下代码
			// moveToFirst(node);
		} else { // 新增
			if(map.size()>=capacity){ //淘汰
				map.remove(head.prev.key);
				head.prev.remove();
			}
			node = new Node<>(key, value);
			map.put(key, node);
			head.insert(node);
		}
	}

	private void moveToFirst(Node<K, V> ele) {
		ele.remove();
		head.insert(ele);
	}

	class Node<K, V> {
		K key;
		V value;
		Node<K, V> prev;
		Node<K, V> next;

		public Node(){
			prev = this;
			next = this;
		}
		public Node(K key, V value) {
			this.key = key;
			this.value = value;
		}
		public void remove(){
			prev.next = next;
			next.prev = prev;
		}
		public void insert(Node<K, V> node){
			node.next = next;
			node.prev = this;
			next.prev = node;
			this.next = node;
		}
	}
}

public class App {
	public static void main(String[] args) throws ClassNotFoundException {
		LRUCache<Integer, Integer> cache = new LRUCache<>(2);
		cache.put(1, 1);
		cache.put(2, 2);
		cache.put(3, 3); //淘汰1
		System.out.println(cache.get(1)); //null
		System.out.println(cache.get(2)); // 2
		cache.put(4, 4); //淘汰3
		System.out.println(cache.get(3)); // null
		System.out.println(cache.get(2)); // 2
		System.out.println(cache.get(4)); // 4
	}
}

12、滑动窗口最值问题

问题基本描述

给一个数组a={2,3,4,2,6,2,5,1}，和一个滑动窗口k=3。求滑动窗口滑动过程中的某些最值。

问题1

求每个滑动窗口的最值？

使用一个双端队列维护窗口情况。双端队列中元素是数组的下标，其值单调递减（队首最大，队尾最小）

当有窗口滑动时

若队首元素（最大的值），超出滑动窗口的范围，弹出

新加入的元素循环与队尾比较，如果队尾小于等于当前值，弹出，否则将元素插入队尾

public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<>();
if(size == 0) return res;
int begin;
Deque<Integer> q = new ArrayDeque<>();
for(int i = 0; i < num.length; i++){
    begin = i - size + 1;
    if(q.isEmpty())
        q.add(i);
    else if(begin > q.peekFirst())
        q.pollFirst();

    while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
        q.pollLast();
    q.add(i);
    if(begin >= 0)
        res.add(num[q.peekFirst()]);
}
return res;
}

问题2（美团2018秋招笔试）

在所有区间内（所有窗口），某个数字出现次数大于等t的区间个数

数组或hashmap: cnt，cnt[num]记录当先窗口元素num出现的次数
sum记录当前窗口内cnt[num]>=t的数的个数
当窗口滑动时
- cnt[淘汰值]–, 如果cnt[淘汰值]==t-1, sum–;
- cnt[新增值]++, 如果cnt[新增值]==t, sum++;
- 如果sum>0, ans++;

13、链表成环判断

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

链表长度大于3，否则返回null
设置快慢指针fast=root.next.next;slow=root.next;
迭代直到相遇，若有一个指针为null，说明无环返回null
fast=root，fast与slow以1的速度同时前进，相遇点为环入口

证明：

设出发点到环入口距离为x，环长度为c，出发点到快慢指针相遇点为
则有：
slow = x + mc + a
fast = x + nc + a
2 slow = fast
化简得
x = (n-2m-1)c + (c-a)
所以从两个指针分别从相遇点和起点出发必然在环入口相遇

实现

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {


    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead==null|| pHead.next==null|| pHead.next.next==null) {
            return null;
        }

        ListNode fast=pHead.next.next;
        ListNode slow=pHead.next;
        while(fast!=slow){
            if(fast.next!=null&& fast.next.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }else{
                return null;
            }
        }
        fast=pHead;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

14、CORS

参考：MDN文档

CORS(Cross-Origin Resource Sharing, 跨域资源共享) W3C的新标准，对跨域请求的验证

将求求方法分为两类

简单请求
- GET
- HEAD
- POST
预检请求
- PUT
- DELETE
- CONNECT
- OPTIONS
- TRACE
- PATCH

主域为http://foo.example，请求http://bar.other的资源，使用AJAX请求

当服务端设置了CORS之后，前端JS代码不变即可实现跨域，但是请求次数可能不同

（1）简单请求

流程和非跨域一致

client   server
  | ---1--> |
	| <--2--- |

请求头和响应头为

//1
GET /resources/public-data/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
Referer: http://foo.example/examples/access-control/simpleXSInvocation.html
Origin: http://foo.example

//2
HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 00:23:53 GMT
Server: Apache/2.0.61
Access-Control-Allow-Origin: *
Keep-Alive: timeout=2, max=100
Connection: Keep-Alive
Transfer-Encoding: chunked
Content-Type: application/xml

[XML Data]

注意响应头的Access-Control-Allow-Origin: *，表示允许所有请求
允许某些域请求：Access-Control-Allow-Origin: http://foo.example

（2）预检请求

流程和非跨域一致

client   server
  | ---1--> |
	| <--2--- |
  | ---3--> |
	| <--4--- |

请求头和响应头为

//1
OPTIONS /resources/post-here/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
Origin: http://foo.example
Access-Control-Request-Method: POST
Access-Control-Request-Headers: X-PINGOTHER, Content-Type

//2
HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 01:15:39 GMT
Server: Apache/2.0.61 (Unix)
Access-Control-Allow-Origin: http://foo.example
Access-Control-Allow-Methods: POST, GET, OPTIONS
Access-Control-Allow-Headers: X-PINGOTHER, Content-Type
Access-Control-Max-Age: 86400
Vary: Accept-Encoding, Origin
Content-Encoding: gzip
Content-Length: 0
Keep-Alive: timeout=2, max=100
Connection: Keep-Alive
Content-Type: text/plain

//3
POST /resources/post-here/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
X-PINGOTHER: pingpong
Content-Type: text/xml; charset=UTF-8
Referer: http://foo.example/examples/preflightInvocation.html
Content-Length: 55
Origin: http://foo.example
Pragma: no-cache
Cache-Control: no-cache

<?xml version="1.0"?><person><name>Arun</name></person>

//4
HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 01:15:40 GMT
Server: Apache/2.0.61 (Unix)
Access-Control-Allow-Origin: http://foo.example
Vary: Accept-Encoding, Origin
Content-Encoding: gzip
Content-Length: 235
Keep-Alive: timeout=2, max=99
Connection: Keep-Alive
Content-Type: text/plain

[Some GZIP'd payload]

15、概率题

（1）两个人轮流抛硬币，规定第一个抛出正面的人赢，请问先抛的人赢的概率多大？

分析：这是一个先手后手的问题。可以按照博弈先后手轮转的思路来做

设先手赢概率为p1，后手概率为p2，则有：

p1 = 1/2 + 1/2*p2
- 1/2表示第一次抛就赢的概率
- 1/2*p2表示第一次抛出后，先手此时变成后手，而后手赢的概率为p2，所以得到此
p1+p2=1

解方程得到p1=2/3