缓存

why

• 高性能

  例如：把查完的值缓存，下次直接访问

• 高并发

  例如：把请求排队

difference（vs memcached)

redis线程模型

redis 内部使用文件事件处理器 file event handler，这个文件事件处理器是单线程的，所以 redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket，根据 socket 上的事件来选择对应的事件处理器进行处理。

假设一个 Redis 服务器正在运作， 那么这个服务器的监听套接字的 AE_READABLE 事件应该正处于监听状态之下， 而该事件所对应的处理器为连接应答处理器。

如果这时有一个 Redis 客户端向服务器发起连接， 那么监听套接字将产生 AE_READABLE 事件， 触发连接应答处理器执行： 处理器会对客户端的连接请求进行应答， 然后创建客户端套接字， 以及客户端状态， 并将客户端套接字的 AE_READABLE 事件与命令请求处理器进行关联， 使得客户端可以向主服务器发送命令请求。

之后， 假设客户端向主服务器发送一个命令请求， 那么客户端套接字将产生 AE_READABLE 事件， 引发命令请求处理器执行， 处理器读取客户端的命令内容， 然后传给相关程序去执行。

执行命令将产生相应的命令回复， 为了将这些命令回复传送回客户端， 服务器会将客户端套接字的 AE_WRITABLE 事件与命令回复处理器进行关联： 当客户端尝试读取命令回复的时候， 客户端套接字将产生 AE_WRITABLE 事件， 触发命令回复处理器执行， 当命令回复处理器将命令回复全部写入到套接字之后， 服务器就会解除客户端套接字的 AE_WRITABLE 事件与命令回复处理器之间的关联。

key

当具备多个索引的时候，如：KEY 联合索引 (a,b,c)为索引，除(b,c)条件索引不会触发该索引表外，(a,b),(a,c),(a,b,c)均会触发上述联合索引，具体可参见explain的key类型，理论应该显示联立索引

如：

EXPLAIN SELECT * FROM TABLENAME WHERE a=’2222’ AND b=‘222’

如果你设置多个单列索引，在explain下，key的值就为其单列的索引，如上述的a列

definition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

private static class BinaryNode<AnyType>
{
    BinaryNode(AnyType theElement)
    {
        this(theElement, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt)
    {
        element = theElement;
        left = lt;
        right = rt;
    }

    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
}

private BinaryNode<AnyType> root;

posOrder

1
2
3
4
5
6
7
8
9

public void posOrder(BinaryNode<AnyType> Node)
    {
        if (Node != null)
        {
            posOrder(Node.left);
            posOrder(Node.right);
            System.out.print(Node.element + " ");
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public void posOrder(BinaryNode<AnyType> Node)
{
    Stack<BinaryNode> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    int i = 1;
    while(Node != null || !stack1.empty())
    {
        while (Node != null)
        {
            stack1.push(Node);
            stack2.push(0);
            Node = Node.left;
        }

        while(!stack1.empty() && stack2.peek() == i)
        {
            stack2.pop();
            System.out.print(stack1.pop().element + "   ");
        }

        if(!stack1.empty())
        {
            stack2.pop();
            stack2.push(1);
            Node = stack1.peek();
            Node = Node.right;
        }
    }
}

Inner Join

SELECT column_list
FROM t1
INNER JOIN t2 ON join_condition1
INNER JOIN t3 ON join_condition2
…
WHERE where_conditions;

Example

select a.name 市,b.name 区,c.name 名
from address a
join address b on b.parentid = a.id
join address c on c.parentid = b.id
join address d on d.parentid = c.id

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1 2	Input: ["flower","flow","flight"] Output: "fl"

Example 2:

1 2 3

Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int minLength = minLength(strs);
		String same = "";
		boolean isSame=false;
		outer:for(int i=0;i<minLength;i++) {
			char sameCharacter = strs[0].charAt(i);
			isSame = false;
			for(int j=0;j<strs.length;j++) {
				if(strs[j].charAt(i)==sameCharacter) {
					isSame = true;
				}else {
					isSame = false;
					break outer;
				}
			}
			if(isSame=true)same+=sameCharacter;
		}
		return same;
    }
    private int minLength(String[] strs) {
		// TODO Auto-generated method stub
        if(strs.length==0) {
			return 0;
		}
		int min = strs[0].length();
		for(int i=1;i<strs.length;i++) {
			if(strs[i].length()<min) {
				min = strs[i].length();
			}
		}
		return min;
	}
}

key

数学题，没什么关键，但是这个解法，还是存在优化空间

Perfect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        String prefix = strs[0];
        
        for (int i = 1; i < strs.length; ++i) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                
                if (prefix.isEmpty()) {
                    break;
                }
            }
        }
        
        return prefix;
    }
}

Problem

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321
Example 2:

Input: -123
Output: -321
Example 3:

Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int reverse(int x) {
		if (x == 0) {
			return 0;
		}
		int result =0;
		long result_l = 0;
		while (x != 0) {
			result_l = result_l * 10 + x % 10;
			x = x / 10;
		}
		
		if(result_l >= Integer.MAX_VALUE||result_l <= Integer.MIN_VALUE) {
			return 0;
		}else {
			result = (int) result_l;
		}
		return result;
    }
}

keys

1.倒序很简单，取余赋给新数就可以了，不过注意JavaScript或者Python的int–>float的情况

2.题目下面其实提示了int的范围，改题目1032个测试数据，有大概7个是超范围的验证数据，所以java中可以巧利用Integer.MAX来进行处理。

perfect

1
2
3
4
5
6
7
8

public int reverse(int x) {
        long res = 0;
        while (x != 0) {
            res = res * 10 + x % 10;
            x = x / 10;
        }
        return (int)res == res ? (int)res : 0;
    }

从实习到后来的两份工作也写了不少的项目，在最近的一份工作用到了大量的消息队列（客服系统，会有大量的访客咨询消息），让我重新回顾了一下在大数据面前，为什么要用消息队列，怎么用好消息队列

理由

• 解耦
• 异步
• 削峰

解耦

通过一个 MQ，Pub/Sub 发布订阅消息这么一个模型，不同微服务之间通信会更加解耦，A给BCDEF发送消息的时候，就不需要考虑他们是否宕机，如何重发等，只需要将信息发送到队列里，让他们自己去取就好了

异步

假设用户请求需要写表，那么吧任务放进队列里，等待写入，前端可以先返回，可以减少用户的等待时间，或者采用多个机器同时写数据的不同部分，加快数据的处理

削峰

就和平时用电一样，晚上电网的压力肯定会很大，如果直接把大量请求压到服务器，会直接宕机，但如果把请求排成队列，然后服务器从里面顺序取，虽然会增加延迟，但是不会宕机，满负荷运作而已

实际生产环境

咨询系统大致分为：咨询核心，端模块，微信模块，分配模块等等，访客发送的咨询信息（web）可能先经过端模块，在咨询核心模块处理前进入队列，然后，分配模块根据用户的设置，如接入客服还是机器人，按什么权重进行分配，分配给哪一个业务组进行操作，来减轻咨询核心的压力

缺点

1.系统可用性降低（MQ挂了咋整）

2.复杂度提升（消息没有重复消费，不会丢失）

3.一致性问题有待解决

所以中小型公司，用 RabbitMQ 是不错的选择

大型公司，基础架构研发实力较强，用 RocketMQ 是很好的选择

如果是大数据领域的实时计算、日志采集等场景，用 Kafka 是业内标准的，绝对没问题，社区活跃度很高，绝对不会黄，何况几乎是全世界这个领域的事实性规范。

递归优化

原因：

在 Java 中，每个线程都有独立的 Java 虚拟机栈。栈具有后入先出的特点，递归调用也是需要后调用的方法先返回，因此使用栈来存储递归调用的信息。这些信息存储在栈帧中，每个 Java 方法在执行时都会创建一个栈帧，用来存储局部变量表、操作数栈、常量池引用等信息。在调用方法时，对应着一个栈帧入栈，而方法返回时，对应着一个栈帧出栈。

随着栈帧frame的增多，将会导致Stack Overflow的报错，例如

1
2
3
4
5
6
7

int f(int i)
{
    if(i == 1 || i == 2)
        return 1;
    else
        return (f(i - 1) + f(i - 2));
}

解决方法1：递归–>非递归

其实很简单，就是用一个临时变量，来保存中间的值，而不是压入堆栈中，

1
2
3
4
5
6
7
8
9
10
11

//费波纳列数列，前两位是1，之后没位数是前两位数的和
private static void fibonacci(int n) {
    int temp1=1,temp2=1,temp;
    for (int i = 1; i <=n ; i++) {
        temp=temp1+temp2;
        temp1=temp2;
        temp2=temp;
    }
    System.out.println();
}
//粘贴于网上

解决办法2：递归–>尾递归

尾递归就是当函数在最后一步（尾部）调用自身，如：

1
2
3

function f(x){
  return g(x);
}

以下算法来自阮一峰教程：

1
2
3
4
5
6

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

该算法并非是尾递归，因为其在返回值的时候进行了一个乘法操作，所以还是普通的递归，复杂度为O(n)，而如果改成尾递归，则：

1
2
3
4
5
6

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

该算法只需要计算

factorial(5,1)

factorial(4,5)

factorial(3,20)

factorial(2,60)

factorial(1,120)

在进入新的递归函数时，尾递归不再需要使用栈帧保存数据，允许抛弃旧的栈帧，那么只需要保存一个栈帧即可

参考资料：

• [阮一峰尾递归]（http://www.ruanyifeng.com/blog/2015/04/tail-call.html）