前言

8月27日上午11点钟，我进行了网易有道三面。
这一轮是总监面，我本来以为会有一些场景题，然后手撕算法，但是都没有。
面试官在发现我对分布式微服务中间件所知甚少之后，就对我丧失了兴趣，给我出了一道比较难的题目，想看看我的算法是否特别出众。
但是遗憾的是，我的算法菜的一笔，让我在面试的时候手撕一道从未见过的、目测难度为hard的算法题实在心有余而力不足，最后挥手道别之后就把我挂了。
最令人感到伤心的是，连封感谢信都没收到，仅仅就是在官网上显示了面试未通过。

聊项目

我说完自己在实验室做的两个项目之后，面试官对第一个垃圾网吧项目表示乏陈可味，说到第二个项目中的数据库优化才表示出了一些兴趣，详细地询问了我是如何进行优化的，问了问具体的业务场景，最后问我知不知道数据库索引实现的原理。

Redis

说完项目之后就开始分布式和中间件连击，首先问我用过Redis的哨兵模式和集群模式吗？知道如何向Redis的集群中新增加一个节点吗？

哨兵模式之前还是有看过，所以还能说一说，集群模式只记得哈希槽之类的相关内容了，所以说自己不知道是如何向Redis集群中新增加一个节点的。

后来看了看《Redis设计与实现》，大概明白了。
每个新建的节点都是一个单独的集合，要向原来的集群发送以下指令：

//127.0.0.1 7001为新增加的IP和端口
CLUSTER MEET 127.0.0.1 70012

但是这个时候新建的节点还没有分配哈希槽，所以还需要重新分配哈希槽，把一部分节点放到新的Redis中去。
在重新分配的过程中Redis也是使用的渐进式Hash的方式，逐步搬迁到新的节点中，同样的如果客户端访问这个Redis的时候发现没有目标key，那么说明该key可能已经移动到新的节点中了，那么就需要重新访问。
如果该key确定已经移动了，那么客户端会修改自己保存的哈希表，之后就会每次访问新的节点而不用走原来的节点。

消息中间件

说完了Redis之后，就问我对消息中间件了解吗？
我就说了说项目中用到的NetMQ和Redis是如何作为消息中间件的。
但是看表情和后来的反应似乎不是很满意，可能想听kafka或者RocketMQ之类的中间件？

算法题

到这里其实只面了6分钟，我已经感觉到面试官对我兴趣不大了，他说，我们来做道算法题吧，于是给我出了这道题。

计算数组的小和

限定语言：C、Python、C++、Javascript、Python 3、Java、Go
数组小和的定义如下：
例如，数组s = [1, 3, 5, 2, 4, 6]，在s[0]的左边小于或等于s[0]的数的和为0；在s[1]的左边小于或等于s[1]的数的和为1；在s[2]的左边小于或等于s[2]的数的和为1+3=4；在s[3]的左边小于或等于s[3]的数的和为1；
在s[4]的左边小于或等于s[4]的数的和为1+3+2=6；在s[5]的左边小于或等于s[5]的数的和为1+3+5+2+4=15。所以s的小和为0+1+4+1+6+15=27
给定一个数组s，实现函数返回s的小和
[要求]
时间复杂度为O(nlogn)，空间复杂度为O(n)

示例1
输入
[1,3,5,2,4,6]
输出
27

分析：
没有分析，我根本不会做，我一开始想先说说自己的思路，但是面试官并不想听，就说你先写吧。
然而并没有想出来，我以为是先使用暴力写出n^2的算法，然后使用logn的二分进行优化，但是想了很久都没有想明白应该如何优化。
面试官也没有说这道题应该怎么去做，就只是叫我下去之后自己看看。

面试结束之后我上网搜了一下，发现原来一开始的思路就错了，这个道题是采用类似《剑指offer》逆序那道题的归并排序来解决的，
所以这个nlogn不是n^2的二分优化，而是归并排序的nlogn，很显然，逆序对是《剑指offer》里面为数不多的困难题，我觉得我在面试时候如果没见过的话肯定做不出来。

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		int[] arr= {1,3,5,2,4,6};
		int[] copy=new int[arr.length];
		System.arraycopy(arr, 0, copy, 0, arr.length);//!!!
		int smallSum=getSmallSum(arr,copy,0,arr.length-1);
		System.out.println(smallSum);
	}
	
	public static int getSmallSum(int[] arr,int[] copy,int l,int r) {
		if(l==r) {
			return 0;
		}
		int mid=(l+r)>>1;
		int leftSum=getSmallSum(copy,arr,l,mid);
		int rightSum=getSmallSum(copy,arr,mid+1,r);
		
		int i=l;
		int j=mid+1;
		int copyIdx=l;//
		int smallSum=0;
		
		while(i<=mid&&j<=r) {
			if(arr[i]>arr[j]) {
				copy[copyIdx++]=arr[j++];
			}
			else {
				smallSum+=arr[i]*(r-j+1);//
				copy[copyIdx++]=arr[i++];
			}
		}
		while(i<=mid) {
			copy[copyIdx++]=arr[i++];
		}
		while(j<=r) {
			copy[copyIdx++]=arr[j++];
		}
		return smallSum+leftSum+rightSum;
	}
}

结局

算法题没有做出来之后，我就已经知道自己凉了，然后在结束之前，面试官又问了几个问题。
Spring源码看过吗？
答：我说看过一点，知道他是如何启动的。但是这边他也没打算问下去。
SpringBoot用过吗？你们现在打的是war包对吗？你知道打包和编译的原理吗？
答：不知道。
你对SpringCloud、微服务、云服务、XXX（一个我从没听过的技术）也没有了解对吧？
答：是的。

好吧，你的情况我知道了，你还有什么想问的吗？
面成这个样子，我再蠢也知道自己凉了，也就没有腆着脸问自己面的怎么样，就问问你们用的什么技术栈，自己现在还应该学点什么东西。

最后的最后，面试官和我道了再见，并且挥了挥手，仿佛就在说沙扬娜拉一般。