图 简单来说，图是由一组点和相对应边组成的，可以表示为G=<V,E>,V为Vertex(点集)，E为Edge(边集)。细分下来根据点集之间的对等关系又可以分为，有向图(又可分为带权和无权有向图)，无向图，混合图。图中点包含的另外一个的重要信息就是各自的出度(outdeg)和入度(indeg)，表示了以该点作为出边和入边的个数。 图的复杂度 对于无向图而言，所有点的度之和为sum(deg)=2*|E|，度之和为边的数目的两倍。对于有向图而言，所有点的入度之和自然等于出度之和，也会等于边的数目，毕竟每一条边存在源…
字符串匹配算法 匹配的目的就是给定两个字符串，s 和 pattern, pattern是要查找的字符串，s是被查找的文本，要求找到pattern在s中第一次出现的位置，假定pattern为 acd, s为acfgacdem, 那么s在t中第一次出现的位置就是4。常见的匹配算法有以下几种： 算法 预处理时间 匹配时间 暴力匹配 $O(n)$ $O((n-m+1)*m)$ Rabin Karp $O(m)$ $O((n-m+1)*m)$ Finite automaton $O(m| \sum |)$…
大数据设计 面试中设计的大数据设计题的场景通常不会太复杂，因此不需要给出细致的操作，给出大致的思路即可。但是有时候依旧考虑的不全面 :disappointed_relieved: :disappointed_relieved: :disappointed_relieved:借此机会记录下来巩固自己这方面的知识。 数据流采样 这是一个经典的采样问题，如果之前没见过一时半会想不出来解决办法。基本场景如下： 有一个无限的整数数据流，如何从中随机地抽取k个整数出来？使得每一个数被抽中的概率相同。 现实场景可以描述为：现有一…
Go当中的字符串为何物？ 不像Java中有String，以及Python中有str类型的数据结构，在Go语言中没有字符类型，字符只是整数的特殊用例，使用了byte(uint8)和rune(int32)作为别名 Go的字符串默认使用UTF-8的编码来表示 byte和rune byte和rune在Go内部分别为uint8以及int32的别名： // byte is an alias for uint8 and is equivalent to uint8 in all ways. It is // used, by c…
哈希(Hash) Hash又称为预映射，是通过散列算法将任意长度的输入变换成固定长度的输出，输出值称为散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能得到相同的输出，所以不可能从散列值来确定唯一的输入值。 将输入映射为输出的过程可以称之为hash运算过程，常见的hash函数可以划分为：加法Hash；位运算Hash；乘法Hash；除法Hash；查表Hash；混合Hash；例如常见的MD5，MD4，SHA-1算法等，都是基于一系列的复杂的运算构成的。虽然运算过程复杂，但还是不可避免…
HTTP HTTP全程Hypertext Transfer Protocol，超文本传输协议，作为万维网初期的产物，影响十分巨大。但是HTTP自诞生以来就像存在一些不可避免的缺点，最大的问题就是"透明传输"，所有的数据在网络上都是“裸奔”，这对于用户是十分致命的。而且存在中间人攻击，被窃听的风险。 HTTPS 为了解决HTTP存在的缺点，引入了HTTPS=HTTP+S，其中S代表SSL或者TLS加密协议。从传输层的角度来看，HTTPS在HTTP的TCP三次握手之后还有SSL/TLS四次握手，在之后的数据传输以及通信…
什么是上下文管理 with open('text.txt','r') as f: lines=f.readlines() 打开文件的with操作是代码中很常见的操作，这就是一个简单的上下文管理，而with open('text.txt','r') as f就是上下文表达式；其中open('text.txt','r')是上下文管理器，f为资源对象(说白了就是一个实例化的类)。 如何实现上下文管理器 上下文管理器是基于上下文管理协议锁生成的，其中最重要的上下文管理协议就是__enter__()以及__exit__()方…
epoll 如果说epoll和select/poll在什么地方具有相同点，那么他们的共同点在于epoll也是需要将监听的文件描述符纳入自己的"监管"。但是select和poll存在自己的一些“天生”的缺点，比如都需要不断地在用户空间和内核空间进行反复的拷贝传递，以及它们在轮询查找可读可写事件的时间复杂度都是线性时间复杂度(表现在select/poll返回值包括了就绪的事件和未就绪的事件，而之后是需要我们自己去判断哪一个文件描述符是就绪了的)。但是，一旦并发量上来了(到达10W和100W级别)，如果还是线性的轮询时间…