计算机与软件工程-研究生复试-专业面试-零碎基础知识-2_排序算法背后的数学模型-程序员宅基地

Java和C 在构造器和编译器在多继承方面区别

你觉得数据结构的算法和机器学习的算法有什么区别

数据结构让我掌握如何与机器交互，用计算机的视角去思考问题，机器学习教会计算机如何理解人类世界的问题，用人的角度去思考

思考一下排序算法背后的数学模型

给定a、b两个文件，各存放50亿个url，每个url各占64B，内存限制是4GB，请找出a、b两个文件共同的url

分析：

由于每个url需要占64B，所以50亿个url占用空间大小为50亿×64=5GB×64=320GB.由于内存大小只有4GB，因此不可能一次性把所有的url加载到内存中处理。对于这种题目，一般采用分治法，即把一个文件中的url按照某一特征分成多个文件，使得每个文件的内容都小于4GB，这样就可以把这个文件一次性读入到内存中进行处理。

解答：

1、遍历文件a，对遍历带的url求hash(url)%500，根据计算结果把遍历到的url分别存放到a0,a1,a2,a3...,a499（计算结果为i的url存储到文件ai中），这样每个文件的大小大约为600MB。当某一个文件中的url的大小超过2GB时，可以按照类似的方法把这个文件继续分为更小的子文件（例如a1文件的大小超过2GB，则把文件继续分为a11，a12...)

2、使用同样的方法遍历文件b，把文件b的url分别存储到文件b0,b1,b2...b499中去。

3、通过之前的划分，与ai中的url相同的url一定在bi中。由于ai与bi中所有的url的大小不会超过4GB，因此可以把它们同时读入内存中进行处理。具体为：遍历文件ai，把遍历到的url存入hash_set中，接着遍历文件bi中的url，如果这个url在hash_set中存在，那么说明这个url是这两个文件共同的url，可以把这个url保存到另一个单独的文件中。当把文件a0~a499都遍历完成后，就找到了两个文件共同的url。

如何从大量数据中找出高频词？

第一步、先对这批海量 数据预处理，在O（N）的时间内用Hash表 完成统计（之前写成了排序，特此订正。July、2011.04.27）；

第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。

即，借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。ok，更多，详情，请参考原文。

或者：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

如何找出某一天访问百度网站最多的 IP？

首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

或者如下阐述（雪域之鹰）：

算法思想：分而治之+Hash

1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；

2.可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；

3.对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；

4.可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；

如何在大量的数据中找出不重复的整数？

方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

如何在大量的数据中判断一个数是否存在？

腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

与上第6题类似，我的第一反应时快速排序+二分查找。以下是其它更好的方法：

方案1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

方案2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下：

又因为2^32为40亿多，所以给定一个数可能在，也可能不在其中；

这里我们把40亿个数中的每一个用32位的二进制来表示

假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类:

1.最高位为0

2.最高位为1

并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；

与要查找的数的最高位比较并接着进入相应的文件再查找

再然后把这个文件为又分成两类:

1.次最高位为0

2.次最高位为1

并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；

与要查找的数的次最高位比较并接着进入相应的文件再查找。

.......

以此类推，就可以找到了,而且时间复杂度为O(logn)，方案2完。

附：这里，再简单介绍下，位图方法：

使用位图法判断整形数组是否存在重复

判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。

位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

如何查询最热门的查询串？

如何统计不同电话号码的个数？

如何从 5 亿个数中找出中位数？

　这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

　　实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

如何按照 query 的频度排序？

还是典型的TOP K算法，解决方案如下：

方案1：

顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。

对这10个文件进行归并排序（内排序与外排序相结合）。

方案2：

一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

方案3：

与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。

如何找出排名前 500 的数？

不基于比较的排序

计数排序

桶排序

假设检验

我们在生活中经常会遇到对一个总体数据进行评估的问题，但我们 又不能直接统计全部数据，这时就需要从总体中抽出一部分样本，用样本来估计总体情况。

所以做假设检验时会设置两个假设：

一种叫原假设，也叫零假设，用H0表示。原假设一般是统计者想要拒绝的假设。

另外一种叫备择假设，用H1表示。备则假设是统计者想要接受的假设。

我们通过样本数据来判断总体参数的假设是否成立，但样本时随机的，因而有可能出现小概率的错误。这种错误分两种，一种是弃真错误，另一种是取伪错误。

弃真错误也叫第I类错误或α错误：它是指原假设实际上是真的，但通过样本估计总体后，拒绝了原假设。明显这是错误的，我们拒绝了真实的原假设，所以叫弃真错误，这个错误的概率我们记为α。这个值也是显著性水平，在假设检验之前我们会规定这个概率的大小。

取伪错误也叫第II类错误或β错误：它是指原假设实际上假的，但通过样本估计总体后，接受了原假设。明显者是错误的，我们接受的原假设实际上是假的，所以叫取伪错误，这个错误的概率我们记为β。

显著性水平

显著性水平是指当原假设实际上正确时，检验统计量落在拒绝域的概率，简单理解就是 犯弃真错误的概率。这个值是我们做假设检验之前统计者根据业务情况定好的。

检验方式

检验方式分为两种：双侧检验和单侧检验。单侧检验又分为两种：左侧检验和右侧检验。

检验统计量

定义：据以对原假设和备择假设作出决策的某个样本统计量，称为检验统计量。

拒绝域

定义：拒绝域是由显著性水平围成的区域

拒绝域的功能主要用来判断假设检验是否拒绝原假设的。如果样本观测计算出来的检验统计量的具体数值落在拒绝域内，就拒绝原假设，否则不拒绝原假设。给定显著性水平α后，查表就可以得到具体临界值，将检验统计量与临界值进行比较，判断是否拒绝原假设。

双侧检验拒绝域：

假设检验步骤

* 提出原假设与备择假设

* 从所研究总体中出抽取一个随机样本

* 构造检验统计量

* 根据显著性水平确定拒绝域临界值

* 计算检验统计量与临界值进行比较

https://zhuanlan.zhihu.com/p/86178674

54张扑克牌,分3堆,每堆18张,问大小王在同一堆的概率?

M=(C54，18)*(C36，18)*(C18，18) 大小王在同一份N=(C3，1)*(C52，16)*(C36，18)*(C18，18) P=N /M=17/53

如何一次遍历计算方差

DX^2=EX^2-(EX)^2

double deviation2(int* a, int n){

if (a==NULL || n<1) return -1.0;

double sumX= 0.0;

double sumX2= 0.0;

for ( int i= 0; i < n; i++ ){

sumX+= a[i];

sumX2+= a[i]*a[i];

}

return sumX2/n- (sumX/n)*(sumX/n);

}

敏捷开发 以用户需求为核心，采用迭代(时间周期)、增量(循序渐进，功能模块)的方式开发软件，目的在于快速覆盖、响应市场需求

在敏捷开发中，软件项目的构建被切分成多个子项目，各个子项目的成果都经过测试，具备集成和可运行的特征。

简单地来说，敏捷开发并不追求前期完美的设计、完美编码，而是 力求在很短的周期内开发出产品的核心功能，尽早发布出可用的版本。然后在后续的生产周期内，按照新需求不断迭代升级，完善产品。

Scrum是橄榄球运动的一个专业术语，表示 “争球”的动作。橄榄球是一项单位场地内寸土必争的运动，一方获得进攻权利，就会一步步地推进敌方阵营。这样就类似团队进行开发项目时， 通过团队合作把项目一步步推进，和打橄榄球一样迅速、充满激情，所以把这样的一个开发流程取名为Scrum。开发团队利用Scrum方法，可以高效运作。

个体和互动高于流程和工具

工作的软件高于详尽的文档

客户合作高于合同谈判

响应变化高于遵循计划

燃尽图

https://blog.csdn.net/u013205623/article/details/80493938

极限编程是一个轻量级的、灵巧的软件开发方法；同时它也是一个非常严谨和周密的方法。它的基础和价值观是交流、朴素、反馈和勇气；即，任何一个软件项目都可以从四个方面入手进行改善：加强交流；从简单做起；寻求反馈；勇于 实事求是。

XP是一种近 螺旋式的开发方法，它将复杂的开发过程分解为一个个相对比较简单的 小周期；通过积极的交流、反馈以及其它一系列的方法，开发人员和客户可以非常清楚开发进度、变化、待解决的问题和潜在的困难等，并根据实际情况及时地调整开发过程。

角色

XP的客户角色负责编写、排列故事优先以及编写和执行测试，已验证故事按照预期进行开发。

12个实践

XP的12个实践是高度协作和相互依存的。

短交付周期（small releases）

计划游戏(the planning game)——计划游戏的主要思想就是先快速地制定一份概要的计划，然后，随着项目细节的不断清晰，再逐步完善这份计划。计划游戏产生的结果是一套用户故事及后续的一两次迭代的概要计划。

重构(refactoring)——重构的目的是降低变化引发的风险、使得代码优化更加容易。

测试(testing)

结对编程(pair programming)——主要是结对编程大大降低了沟通的成本，提高了工作的质量。

持续一致的速度(sustainnable pace)

团队代码所有权(team code ownership)

编码标准(coding standard)——拥有编码标准可以避免团队在一些与开发进度无关的细枝末节问题上发生争论，而且会给重构、结对编程带来很大的麻烦。不过，XP 方法的编码标准的目的不是创建一个事无巨细的规则列表，而是要能够提供一个确保代码清晰，便于交流的指导方针。

简单设计(simple design)——定义了四个约束：业务代码和测试代码充分表达程序员的意图、没有重复代码、系统使用最少数量的类、系统使用最少数量的方法

隐喻(metaphor)——隐喻常用于四个方面：寻求共识、发明共享语汇、创新的武器、描述架构。

持续集成(continuous intergration)

客户现场(on-site customer)——客户讲和开发团队坐在一起，客户编写故事和验收测试，并当场尽快回答团队的问题。

极限编程的价值—— 四大价值

单反通气

沟通——XP重视沟通，面对面沟通、谈话、回应等
简单——关注当下遇到的问题创建解决方案
反馈——XP团队重视反馈，反馈越快越好
勇气——XP团队重视勇气，例如有勇气重构他们的代码

极限编程的原则—— 五项基本原则

快速反馈

假设简单

增量变化

拥抱变化

高品质的产品

本文链接：https://blog.csdn.net/m0_37302219/article/details/106069307

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

分布式光纤传感器的全球与中国市场2022-2028年：技术、参与者、趋势、市场规模及占有率研究报告_预计2026年中国分布式传感器市场规模有多大-程序员宅基地

文章浏览阅读3.2k次。本文研究全球与中国市场分布式光纤传感器的发展现状及未来发展趋势，分别从生产和消费的角度分析分布式光纤传感器的主要生产地区、主要消费地区以及主要的生产商。重点分析全球与中国市场的主要厂商产品特点、产品规格、不同规格产品的价格、产量、产值及全球和中国市场主要生产商的市场份额。主要生产商包括：FISO TechnologiesBrugg KabelSensor HighwayOmnisensAFL GlobalQinetiQ GroupLockheed MartinOSENSA Innovati_预计2026年中国分布式传感器市场规模有多大

07_08 常用组合逻辑电路结构——为IC设计的延时估计铺垫_基4布斯算法代码-程序员宅基地

文章浏览阅读1.1k次，点赞2次，收藏12次。常用组合逻辑电路结构——为IC设计的延时估计铺垫学习目的：估计模块间的delay，确保写的代码的timing 综合能给到多少HZ，以满足需求！_基4布斯算法代码

OpenAI Manager助手（基于SpringBoot和Vue）_chatgpt网页版-程序员宅基地

文章浏览阅读3.3k次，点赞3次，收藏5次。OpenAI Manager助手（基于SpringBoot和Vue）_chatgpt网页版

关于美国计算机奥赛USACO，你想知道的都在这_usaco可以多次提交吗-程序员宅基地

文章浏览阅读2.2k次。USACO自1992年举办，到目前为止已经举办了27届，目的是为了帮助美国信息学国家队选拔IOI的队员，目前逐渐发展为全球热门的线上赛事，成为美国大学申请条件下，含金量相当高的官方竞赛。USACO的比赛成绩可以助力计算机专业留学，越来越多的学生进入了康奈尔，麻省理工，普林斯顿，哈佛和耶鲁等大学，这些同学的共同点是他们都参加了美国计算机科学竞赛（USACO)，并且取得过非常好的成绩。适合参赛人群USACO适合国内在读学生有意向申请美国大学的或者想锻炼自己编程能力的同学，高三学生也可以参加12月的第_usaco可以多次提交吗

MySQL存储过程和自定义函数_mysql自定义函数和存储过程-程序员宅基地

文章浏览阅读394次。1.1 存储程序1.2 创建存储过程1.3 创建自定义函数1.3.1 示例1.4 自定义函数和存储过程的区别1.5 变量的使用1.6 定义条件和处理程序1.6.1 定义条件1.6.1.1 示例1.6.2 定义处理程序1.6.2.1 示例1.7 光标的使用1.7.1 声明光标1.7.2 打开光标1.7.3 使用光标1.7.4 关闭光标1.8 流程控制的使用1.8.1 IF语句1.8.2 CASE语句1.8.3 LOOP语句1.8.4 LEAVE语句1.8.5 ITERATE语句1.8.6 REPEAT语句。_mysql自定义函数和存储过程

半导体基础知识与PN结_本征半导体电流为0-程序员宅基地

文章浏览阅读188次。半导体二极管——集成电路最小组成单元。_本征半导体电流为0

随便推点

【Unity3d Shader】水面和岩浆效果_unity 岩浆shader-程序员宅基地

文章浏览阅读2.8k次，点赞3次，收藏18次。游戏水面特效实现方式太多。咱们这边介绍的是一最简单的UV动画（无顶点位移），整个mesh由4个顶点构成。实现了水面效果（左图），不动代码稍微修改下参数和贴图可以实现岩浆效果（右图）。有要思路是1，uv按时间去做正弦波移动2，在1的基础上加个凹凸图混合uv3，在1、2的基础上加个水流方向4，加上对雾效的支持，如没必要请自行删除雾效代码(把包含fog的几行代码删除)S..._unity 岩浆shader

广义线性模型——Logistic回归模型（1）_广义线性回归模型-程序员宅基地

文章浏览阅读5k次。广义线性模型是线性模型的扩展，它通过连接函数建立响应变量的数学期望值与线性组合的预测变量之间的关系。广义线性模型拟合的形式为：其中g(μY)是条件均值的函数（称为连接函数）。另外，你可放松Y为正态分布的假设，改为Y 服从指数分布族中的一种分布即可。设定好连接函数和概率分布后，便可以通过最大似然估计的多次迭代推导出各参数值。在大部分情况下，线性模型就可以通过一系列连续型或类别型预测变量来预测正态分布的响应变量的工作。但是，有时候我们要进行非正态因变量的分析，例如：（1）类别型.._广义线性回归模型

HTML+CSS大作业环境网页设计与实现(垃圾分类) web前端开发技术 web课程设计网页规划与设计_垃圾分类网页设计目标怎么写-程序员宅基地

文章浏览阅读69次。环境保护、保护地球、校园环保、垃圾分类、绿色家园、等网站的设计与制作。总结了一些学生网页制作的经验：一般的网页需要融入以下知识点：div+css布局、浮动、定位、高级css、表格、表单及验证、js轮播图、音频视频 Flash的应用、ul li、下拉导航栏、鼠标划过效果等知识点，网页的风格主题也很全面：如爱好、风景、校园、美食、动漫、游戏、咖啡、音乐、家乡、电影、名人、商城以及个人主页等主题，学生、新手可参考下方页面的布局和设计和HTML源码（有用点赞△）一套A+的网_垃圾分类网页设计目标怎么写

C# .Net 发布后,把dll全部放在一个文件夹中,让软件目录更整洁_.net dll 全局目录-程序员宅基地

文章浏览阅读614次，点赞7次，收藏11次。之前找到一个修改 exe 中 DLL地址的方法, 不太好使,虽然能正确启动, 但无法改变 exe 的工作目录,这就影响了.Net 中很多获取 exe 执行目录来拼接的地址 ( 相对路径 ),比如 wwwroot 和代码中相对目录还有一些复制到目录的普通文件等等,它们的地址都会指向原来 exe 的目录, 而不是自定义的 “lib” 目录,根本原因就是没有修改 exe 的工作目录这次来搞一个启动程序,把 .net 的所有东西都放在一个文件夹,在文件夹同级的目录制作一个 exe._.net dll 全局目录

BRIEF特征点描述算法_breif description calculation 特征点-程序员宅基地

文章浏览阅读1.5k次。本文为转载，原博客地址：http://blog.csdn.net/hujingshuang/article/details/46910259简介 BRIEF是2010年的一篇名为《BRIEF:Binary Robust Independent Elementary Features》的文章中提出，BRIEF是对已检测到的特征点进行描述，它是一种二进制编码的描述子，摈弃了利用区域灰度..._breif description calculation 特征点

房屋租赁管理系统的设计和实现，SpringBoot计算机毕业设计论文_基于spring boot的房屋租赁系统论文-程序员宅基地

文章浏览阅读4.1k次，点赞21次，收藏79次。本文是《基于SpringBoot的房屋租赁管理系统》的配套原创说明文档，可以给应届毕业生提供格式撰写参考，也可以给开发类似系统的朋友们提供功能业务设计思路。_基于spring boot的房屋租赁系统论文