Diameter of Tree
Definition of diameter In a given tree, the diameter is defined as the longest path between any two nodes. For instance, the diameter of th…
Latest
Timer on Flink
Timer on ProcessFunction and KeyedProcessFunction Flink distinguishes between two key notions of time: processing time and event time. Proc…
Loading data periodically in Flink
Stream API (SourceFunction, AbstractSourceFunction and RichSourceFunction) in Flink In Flink's streaming API, there is a critical interface…
Maximum Manhattan Distance of Two Points in Points Set
Manhattan Distance Definition: The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ in a 2D plane is defined as $dis = |…
Dynamic Segment Tree
Why Dynamic Segment Tree? As know for segment tree, the space complexity is is up to 4 n, which n is upper bound of data range. However, :-…
Golang--GMP(Goroutine, Machine, Processor)模型
前言 Goroutine是Golang中实现的协程，它保证了Golang的高并发的可用性，这些Goroutine分配、负载、调度到处理器上采用的是G-M-P模型。 进程、线程、Goroutine 进程是操作系统进行资源分配调度的最小单元，而线程则是CPU进行调度的最小单元。进程…
非技术篇-7 Habits of Highly Effective People [By Stephen R. Covey]
引言 Covey在书中用一个小例子描述了“个人看法的重要性”，他儿子在学校的表现不尽人意，做父母的经常鼓励孩子，然而却是于事无补，随着Covey对儿子的看法转变，即便是不刻意鼓励孩子，他也能飞快的进步。也即引出了书中最为重要的观点：“为了达成真正的改变，必须对自我认知做出改变，…
系统设计之——Twitter时间线、搜索功能
Timeline & Search 简介 系统设计中，时间线(timeline)功能是十分常见的，诸如朋友圈，微博，Twitter等社交平台都会涉及到，主要功能就是按时间线看到已经关注的人发送的消息。而搜索功能则是公开社交平台的重要功能。 Pull vs. Push 为了实现时…
API限速设计
给定一个公共API，限制每个用户每秒只能调用1000次，如何实现？这个一个经典的API限速问题(API rate limiting)。 初始想法 最朴素的想法就是给每一个用户配额，此时为Q，在第一次调用的时候分配给用户，然后在接下来的时间段，如果访问的此时大于Q，就直接拒绝用户…
雪花算法及Golang实现
雪花算法能解决什么问题？ 雪花算法能够生成全局唯一的ID编码作为其他地方的标记。且生成一系列的ID满足如下的性质： 生成的系列ID是递增的 高可用性：任何时候都能够生成唯一的ID 再高并发的条件下也能够保证服务 SnowFlake的组成 最高位是符号位，始终为0 41位的时间戳…
温故而知新 - 图
图 简单来说，图是由一组点和相对应边组成的，可以表示为G=<V,E>,V为Vertex(点集)，E为Edge(边集)。细分下来根据点集之间的对等关系又可以分为，有向图(又可分为带权和无权有向图)，无向图，混合图。图中点包含的另外一个的重要信息就是各自的出度(outdeg)和入度…
Rabin Karp-字符串匹配算法
字符串匹配算法 匹配的目的就是给定两个字符串，s 和 pattern, pattern是要查找的字符串，s是被查找的文本，要求找到pattern在s中第一次出现的位置，假定pattern为 acd, s为acfgacdem, 那么s在t中第一次出现的位置就是4。常见的匹配算法有…
Golang
大数据系统设计题(简易版本)
大数据设计 面试中设计的大数据设计题的场景通常不会太复杂，因此不需要给出细致的操作，给出大致的思路即可。但是有时候依旧考虑的不全面 :disappointed_relieved: :disappointed_relieved: :disappointed_relieved:借此…
算法
极角排序
前言 感谢 LeetCode 让我又接触到了一个知识:sleeping: 极角排序 高中学习的极角，指的是极坐标系中的一个点相对极点有唯一的极坐标($\rho$, $\theta$)，其中$\rho$表示选定点到极点的距离，$\theta$表示选定点和极轴逆时针的夹角，且$0…
数据结构/图论
红黑树-旋转的艺术
红黑树的定义和性质 红黑树的出现之前，先有的二叉查找树(BST)以及平衡二叉树(AVL树)： BST根节点的值大于所有左子树的所有值，小于右子树的所有值。 AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的高度差为小于等于1。 AVL的出现改变了BS…
Golang
Go：字节字符，字符串遍历
Go当中的字符串为何物？ 不像Java中有String，以及Python中有str类型的数据结构，在Go语言中没有字符类型，字符只是整数的特殊用例，使用了byte(uint8)和rune(int32)作为别名 Go的字符串默认使用UTF-8的编码来表示 byte和rune by…
Python
哈希(Hash)，字典(Dict)，集合(Set)
哈希(Hash) Hash又称为预映射，是通过散列算法将任意长度的输入变换成固定长度的输出，输出值称为散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能得到相同的输出，所以不可能从散列值来确定唯一的输入值。 将输入映射为输出的过程可以称之为h…
计算机网络
说一说HTTPS中的"S"
HTTP HTTP全程Hypertext Transfer Protocol，超文本传输协议，作为万维网初期的产物，影响十分巨大。但是HTTP自诞生以来就像存在一些不可避免的缺点，最大的问题就是"透明传输"，所有的数据在网络上都是“裸奔”，这对于用户是十分致命的。而且存在中间人…
Python
python上下文管理
什么是上下文管理 打开文件的with操作是代码中很常见的操作，这就是一个简单的上下文管理，而 就是上下文表达式；其中 是上下文管理器，f为资源对象(说白了就是一个实例化的类)。 如何实现上下文管理器 上下文管理器是基于上下文管理协议锁生成的，其中最重要的上下文管理协议就是 以及…
Linux
I/O多路复用之epoll
epoll 如果说epoll和select/poll在什么地方具有相同点，那么他们的共同点在于epoll也是需要将监听的文件描述符纳入自己的"监管"。但是select和poll存在自己的一些“天生”的缺点，比如都需要不断地在用户空间和内核空间进行反复的拷贝传递，以及它们在轮询查…
Linux
I/O多路复用之poll
poll select, poll, epoll是IO多路复用当中的重要的三种实现方式，poll和epoll相对于select而言，只能在Linux下使用，但是select是跨平台的。同时poll相对于select而言，没有最大监听数量的限制。但是也是监管一系列的文件描述符，阻…
Linux
I/O多路复用之select
题外话：服务器单机理论最大能连接多少个客户端？ 答案是：对于IPV4而言，粗略估计有 个连接。计算机标识一个唯一的socket连接依赖的是唯一四元组-(源ip，源端口，本机ip，本机端口)，其中本机的ip和socket初始化的端口是不能变的，因此源ip和源端口都是可变的。那么本…
算法
摩尔投票
摩尔投票是什么？ 摩尔投票用于寻找集合中出现多数的元素，并且出现多数可以定义为大于n//2或者n//3或者是其他自定义的频次(实际上，如果希望求出超过n//3频次的元素，那么是三个元素相互抵消)。摩尔投票的基本流程为： - 投票阶段：投票人之间进行抵消。 - 技术阶段：计算对抗…
数据库
MySQL当中的窗口函数
窗口函数概述 窗口函数（Window Function）针对查询中的每一行数据，基于和它相关的一组数据计算出一个结果。 顾名思义，每一行都会对应一个计算结果，而不是将一组结果聚合计算成一条结果，原始数据有多少行，窗口函数计算之后还是有多少行。 创建数据 聚合函数和窗口函数的区别…