Category Archives: 笔面题

蓄水池算法

问题描述

要求从N个元素中随机的抽取k个元素,其中N无法确定(N是个流,可能无穷大)。

这种应用的场景一般是数据流的情况下,由于数据只能被读取一次,而且数据量很大,并不能全部保存,因此数据量N是无法在抽样开始时确定的;但又要保持随机性,于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”,怎么才能是随机的抽取元素呢?我们设想,买彩票的时候,由于所有彩票的中奖概率都是一样的,所以我们才是“随机的”买彩票。那么要使抽取数据也随机,必须使每一个数据被抽样出[......]

继续阅读

数据结构重读 - 有向无环图、AOV网和拓扑排序

DAG和概念
有向无环图:顾名思义,有向图,且不含环,directed acycline graph,简称DAG图。

无向图检查环:若深度优先遍历过程遇到回边(先前访问过的顶点的边),则必定存在环。

有向图检查环:从某个顶点v出发,在dfs(v)结束前,出现一条从顶点u到顶点v的回边,由于u在生成树上是v的子孙,则有向图必定存在包含顶点v和u之间的环。

DAG图是描述工程的有效工具。一个工程可以用一个DAG图表示,每一个顶点是一个子工程,工程的先后关系用弧表示。

围绕着[......]

继续阅读

C语言实现BitMap

BitMap的原理不用多说了。

主要说下位操作。

我们假设每个基础存储单元为char,则BYTESIZE = 8,如果为int则16 or 32。

当设置i时,首先ptr+=i/BYTESIZE,到达要操作的那个char。

然后对*ptr |= 0x01<<(i%BYTESIZE)即可。这里在同一个机器上,可以忽略大小端的问题。

检查的时候,也是首先ptr+=i/BYTESIZE,然后查 (*ptr&0x01<<(i%BYTESIZE[......]

继续阅读

天平比较找出轻球

用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的(条件是y个球中y-1个重量相等,其他一个轻),
使用x 次天平,最多可以从y 个小球中找出较轻的那个,求y 与x 的关系式。

其实,这是一个“三分查找问题”。

当y=3时,x=1(一次称重即可):

3个球中任选两个放到天平两端,若相等,则没称的那个是轻球。

若有一个轻,则轻的就是。

递归可以分析出来x = log3(y)。

 [......]

继续阅读

软件工程中三种软件开发模型

1、瀑布开发模型(Waterfall Model)

将软件生命周期划分为制定计划、需求分析、软件设计、程序编写、软件测试和运行维护等六个活动。一个阶段完成后再将其输出作为下一个阶段的输入,逐层开发。缺点是难以适应业务需求变化,风险管控不够。

2、快速原型模型(Rapid Prototype Model )

迅速建造一个可以运行的软件原型 ,以便理解和澄清问题,使开发人员与用户达成共识,最终在确定的客户需求基础上开发客户满意的软件产品。优点是可以快速摸清客户需求且成本低风险低。缺[......]

继续阅读