Hailiang Dong

Ph.D. & M.S. in Computer Science, B.S. in Mathematics

Find Majority Element in Linear Time

Problem DescriptionInput: an array of elements with size $N​$, and there exists an element $M​$ accounts for more than 50% of the array (called Majo..


KMP字符串匹配算法

问题描述字符串匹配是一个很经典的问题,具体描述如下: 给定两个字符串:主串S和模式串P,判断S中是否包含P,如果包含则返回S中出现的第一个P的位置( S中出现的所有的P的位置),否则返回-1(NULL)。 在下文中,为了便于分析,我们记主串S的长度为n,模式串P的长度为m。此外,我们用符号i..


C语言无符号数据读取

背景像C语言这种语言对输入输出的要求极其严格,你必须要制定你读取的数据类型以及格式。现在的问题是如果你读取的时候指定了错误的数据类型,会发生什么? 案例分析加入说你要读取64位无符号整数类型数据,所以你的程序可能大概是这样子的。12unsigned long val=0;scanf("..


电梯的停留楼层数量分析

问题描述假设现在一个楼栋共有M层,有一个电梯一次性最多能装N个人。问题是,假如说现在该电梯在一楼进入了N个乘客,不考虑从中间楼层上的乘客问题,那么该电梯大概需要停留几次才能将所有的乘客送到目的地。也就是说,这N个乘客选出不同楼层的数量X的期望是多少? 按照定义求解首先,我们可以分析出随机变量X可..


多桶哈希的冲突数量分析

介绍传统的哈希方式采用一个大的连续空间来存储元素,当元素满了之后,它需要将空间的容量扩充为两倍,并将之前所有的元素重新哈希到新的空间里面,这个过程成为Rehash. 现在我们有一个问题是, 如果将数据按照范围等分成K份,将一个大的空间等分成K个桶。然后将每一份数据分别hash到对应的桶里面,..


阿里笔试编程题-相亲的次数问题

问题描述一个未婚男青年要和N个女孩相亲,由于他不记录已经相亲过的女孩,而是每一次随机从这N个女孩中挑选一个进行相亲。由于相亲的女孩可能是已经相亲过的,那么现在的问题就是他平均要相亲多少次,才能将所有的女孩都相亲一遍(期望)。 问题分析其实呢,这道题只是一道披着编程外表的数学题。他就是要求男孩相亲..


阿里算法工程师编程小测试-取石子游戏

问题描述现在有一堆石子,共有N个。两个人轮流取石子,先拿完的人获胜。规定第一次不能拿N个,并且每一次拿的石子数量介于1和上一次拿的数量之间。现在的问题是,如果你作为先手,对于给定的N个石子,在保证能获胜的情况下,你最多能拿多少个?如果先手不能获胜,输出0即可。 问题分析这个题有意思的地方就在于每..


计算二项分布的期望

基本概念二项分布即重复N次独立的伯努利试验。在每次试验中只有两种可能的结果(成功和失败),而且两种结果发生与否互相对立,并且相互独立,与其它各次试验结果无关,事件发生与否的概率在每一次独立试验中都保持不变。设随机变量X为N次实验中成功的次数,则如何求X的期望? 按照定义求解假设成功的概率为$p$..


内核程序访问用户地址空间

背景由于做实验需要在Linux内核中添加一些系统调用,我们在一台机器上完成了系统调用的编写,并顺利通过了所有的测试,用户程序的运行也完全正常。不够由于实验数据的增大,我们需要一台内存更大的电脑。为了方便,我们直接把那台机器的硬盘拆下来,放到别的机器上,然后从那块硬盘启动进入系统做实验。 然后神奇..


K-Means 算法基础

基本原理K-Means 作为一种最简单的聚类算法,在数据挖掘中有着比较广泛的应用。如下图所示,给你一批数据(绿色的点),让你将数据划分成2类,这就是K-Means要解决的问题。 总的来说,K-MEANS的具体计算方法可分为如下的四步 随机选取K个中心点 图(b) 遍历所有数据,将每个数据划分..