The advantages of Consistent Hashing

It's one specific hash method. For Linear Hashing, it has to almostly rehash all the keys when triggered rehash. Howerver, the Consistent Hashing would just change the K / n keys. K is for the amount of keys, n is for the amount of slots.Therefore, there are some advantages of consistent hashingStorage BalanceLoad BalanceOversmootReferenc[1]. Consistent Hashing. https://en.wikipedia.org/wiki/C... Read More

滴滴研发 & 测试岗位内推集锦(持续更新)

最近更新:2020年04月09日为什么加入滴滴?成就感:用技术改变生活,成就感爆棚个人待遇:工资福利待遇优越,发展前景可期用户量:服务于中国以及海外若干国家的一站式出行平台行业地位:互联网独角兽在招岗位有哪些?Go/PHP/Java 后端研发工程师/架构师服务端技术/运营引擎滴滴网约车最核心的后台研发团队,参与网约车公司核心出行、出行中台、智能补贴引擎、广告、内容等公司级核心项目的研发。和顶级工程师一起,提升负责项目的核心指标,团队技术氛围浓厚,成长快。要求对技术充满热情,强悍的代码能力,至少擅长一门语言对新事物保持强烈好奇心,主动性强,有强烈的成长欲望前端研发工程师/架构师前端技术滴滴网约车前端技术团队,负责微信/支付宝滴滴出行 WebAPP 及小程序,各用户产品前端,内部平台的前端以及 Node 服务研发工作。团队技术氛围好,有小程序框架MPX、移动端组件库CubeUI、Better... Read More

60分钟搞定Tarjan算法求解无向图的割点与桥

本人在学习 Tarjan 算法求解无向图的割点与桥的问题时,很快发现了一篇简洁易懂的文章。很顺利地了解算法的思路,并写出了“高效”的代码,此时内心飘过 —— So Easy。然而,当我翻开《算法竞赛进阶指南》这本书的有关篇章时,我发现其中经过精简优化的代码有几条语句让我不得其所。以至于,花了较多心思和时间来思考🤔这段真正高效的 Tarjan 算法的工作原理以及代码的编写。关于 Tarjan 算法,我将会写若干篇系列文章,来完整系统地介绍 Tarjan 算法的原理以及其主要解决的问题。而在本章我主要讲一个问题 —— 如何使用 Tarjan 算法求解无向图的割点与桥。在讲述问题之前,我们先来简单地了解下什么是 Tarjan 算法?Tarjan 算法Tarjan 算法是基于深度优先搜索的算法,用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥,进一步地可以求解无向图的... Read More

递归

递归递归是什么?递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法 。维基百科简单说,就是自身调用自身。为什么使用递归?往往面对一类问题时,如果它的规模足够小或者说达到既定的边界条件时,我们可以直接获取答案。但是,当这类问题的规模比较大时,却往往无法直接获取答案。那么,这个时候就可以通过“自身调用自身”的方式,来不断地减小问题的规模,直到问题的规模被缩减到足够小时,直接将答案返回上层的调用者,最终获取到原问题的解。如果将求解的过程逆过来,那么就是所谓的递推。通过这种方式,我们可以写出“优雅”的代码去解决规模比较大的问题。进而,避免了通过递推的方式,在每一次递推时产生的复杂的条件判断的问题。上文中提到经过递归调用,会不断地减小问题的规模,有些作者认为这是一种减治法。递归的特性自身调用自身在上文中,已经提到了这个特性,而且也非常好理解,不再赘述。... Read More

后缀数组(Suffix Array)

本文介绍后缀数组的定义与构建的过程。首先,文章介绍什么是后缀数组,随后讲解了最自然的朴素算法。为了引出更高效的算法,文章提及了倍增思想与基数排序的背景基础知识。接着,通过模拟演练的方式一步一步地演示如何创建后缀数组。将构建的抽象过程形象地展示出来,使读者更易理解。定义给定字符串,其所有后缀有。(6为字符串的长度)。如下所示S = "banana"s1 = "banana"s2 = "anana"s3 = "nana"s4 = "ana"s5 = "na"s6 = "a"后缀数组即为由构成的有序的(字典序升序排列的)字符串数组。vector<string> sa{"a", "ana", "anana", "banana", "na", "nana"};构建后缀数组的动态过程演示动画: https://visualgo.net/zh/suffixarra思路如何构建后缀数组?若字符串的长... Read More

树状数组(Binary Indexed Tree)

树状数组或二叉索引树(英语:Binary Indexed Tree),又以其发明者命名为Fenwick树。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和, 区间和。它可以以的时间得到任意前缀和,并同时支持在时间内支持动态单点值的修改。空间复杂度。摘自维基百科文章先介绍低位运算(lowbit)的基本知识,再提及如何将一个整数划分为个区间的运算过程,进而延展到如何将线性序列以树行结构进行存取,接着介绍了高级数据结构——树状数组的两个基本操作——查询前缀和与单点增加,最后介绍了树状数组的一个应用——求解逆序对数。lowbit(低位)运算定义为非负整数在二进制表示下“最低位的1及其后边所有的0”构成的数值。比如:,其二进制表示为 ,则其低位。公式如何计算一个整数中二进制表示下所有位是1的数值?比如,则其二进制表示下所有位是1的数值有:,。... Read More

动态规划与分治法的思考

如果一个问题具有最优子结构的性质,此外子问题具有重叠性质,那么可以采用自底向上的动态规划的思路进行求解。同时,往往可以用递归的方式自顶向地进行求解,即分治法。如果用分治法去求解这个问题时,能够利用备忘录法进行避免对于子问题的重复计算,那么其计算的效率可以和动态规划的计算效率相比。文章来源:胡小旭 =>动态规划与分治法的思考 Read More

分治法与回溯法的思考

共同的递归性质在广义上来说,所有递归的算法都属于分治法。无非是将问题分解成一个规模更小的问题,还是将问题分解成若干个,甚至和输入规模多项式级别的子问题。那么对于前者,有些作者称作是减治法,后者称作分治法。那么对于回溯法(以深度优先搜搜方式进行)来说,目前为止我见过的都是通过递归的形式来实现的,那么从这个意义上来讲,回溯算法就是分治法的一种。回溯状态的有无再说,之所以称作是回溯法,是因为在搜索的过程中需要回溯到问题的某个状态,所以这往往需要保存回溯时的一些状态属性。然而,分治法通常并不需要考虑回溯状态的保存。分解问题的规模分治法往往是将问题分解成若干个子问题的形式,然而回溯法往往是将问题分解成规模更小的一个子问题。由于分治法将问题分解成若干个子问题,故当前问题的解需要依赖于若干个子问题,也就是若干个搜索路径的解,所以重点在于如何合并子问题的解;而然回溯法问题规模就为1个,当前的搜索路径的问题... Read More

一只青蛙跳出来的分治法、回溯法与动态规划

从2018年7月份开始,基础薄弱的我从0开始刷LeetCode题目。目的性很明确,也很简单——就是为了提高解决问题的思考实践能力,也为了提升自己的核心竞争力。也许,牛人会觉得这并不算什么竞争力。是的,我同意的。但,这是我目前能做的比较基础的事情罢了。迄今(2018年12月28日)为止,已经刷了108道题目。顺序基本上是按照出现的频率(Frequency)来刷的,这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后,有那么一些题目会觉得“似曾相识”了,也会有一种触类旁通的感觉了。所以,我觉得应该适当放慢刷题的速度,同时做做总结了。所以,计划了一项视频解说计划,在YouTubeh和B站都建立了《小旭解说算法之路》的频道,欢迎订阅,多多提建议。那么,进入正题。经过了108道题的历练之后,我来说说对于分治法、回溯法和动态规划的理解。我觉得他们三者是一个相互有交集的概念,并不... Read More

[LeetCode]743. Network Delay Time

原题There areNnetwork nodes, labelled1toN.Giventimes, a list of travel times asdirectededgestimes[i] = (u, v, w), whereuis the source node,vis the target node, andwis the time it takes for a signal to travel from source to target.Now, we send a signal from a certain nodeK. How long will it take for all nodes to receive the signal? If it is impossible, return-1.NoteNwill be in the range[1, 100].Kwil... Read More

最大流问题之Ford-Fulkerson算法

Ford-Fulkerson算法(亦即标号法?)的输入与步骤如下输入给定一个容量为c的图G=(V, E),源点s与汇点(终点)步骤对图G中每一个边(u, v)的流量f(u, v)进行初始化为查询过程:寻找(DFS、深度优先搜索方式)图G中的一条路径p,其中每一条边(u, v) ∈p,都有fc(u, v) = c(u, v) - f(u, v) > 0(c(u, v) 代表当前边的容量,f(u, v) 代表当前边已有的流量,即c(u, v) - f(u, v)代表当前边可用的最大流量,即剩余流量调整过程:计算当前路径下每条边的最小剩余容量,cf(p) = min{fc(u, v) : (u, v) ∈p},然后对于每条边进行如下操作f(u, v) = f(u, v) + cf(p) (前向狐f(v, u) = f(v, u) - cf(p) (后向狐往复上述2与3步骤,直至无法找到路径p为止... Read More

[LeetCode]Sum of Subarray Minimums

原题Given an array of integersA, find the sum ofmin(B), whereBranges overevery (contiguous) subarray ofA.Since the answer may be large,return the answer modulo10^9 + 7.Example 1Input: [3,1,2,4Output: 1Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.Note1 <= A.length <= 300001 <= A[i] <题解首先明确题... Read More

滴滴出行业务平台研发岗位内推

有意者欢迎骚扰:huxu@didichuxing.co更新于:2018.05.25 15:5【在线业务研发工程师(PHP/Golang)我们需要一个这要的你有志于参与一场出行行业的变革;对于大流量高并发业务场景的技术挑战心潮澎湃。用你的代码影响成千上万人负责快车、专车、拼车、优步、优享、出租车等核心业务的服务端研发工作;负责接送机、站点拼车、跨城、小巴等垂直出行场景的服务建设和通勤、休娱、商旅等新出行场景孵化。【中台建设&中间件研发工程师/众里寻你千百度每一次将复杂世界变得简单都让你心花怒放;每一次你的系统都能云淡风轻跨越一座座流量洪峰,而你依然心若止水。你来协助我们提升生产力负责打磨现有产品业务流程,深入了解司乘两端业务,对出行场景进行抽象优化;负责出行中台&中间件架构设计和优化工作,提供新业务的快速扩展和接入能力。有意者欢迎骚扰:huxu@didichuxing.co... Read More

[维护中]基于文本图形(ncurses)的文本搜索工具 ncgrep

源码下载http://github.com/ncgrep/ncgre背景作为一个VIM党,日常工作开发中,会经常利用grep进行关键词搜索,以快速定位到文件。如图但是,这一过程会有两个效率问题展示的结果无法进行直接交互,需要手动粘贴文件路径在打开展示的结果没有进行分组,直接将结果罗列出来可想而知,当搜索的内容结果集比较大时,可谓痛苦。那可以用Vim中的Ag插件进行搜索啊?是的,但他只解决了交互的问题。仍然没有解决结果集分组分类的痛点。思路在使用Eclipse等IDE进行文本全局搜索时,在加载效果(懒加载)可视化方面有很大优势。那么,期望基于linux系统,提供一个类似的搜索工具。优点(功能)如下结果集可以直接交互结果集可以进行分组展示结果集通过“懒加载”方式装载基于文本图形界面的类库是什么呢?网上大致了解了下VIM、htop类似的软件,其都是基于一个叫ncurses的类库实现的。项目... Read More