null - 程序员宅基地

计算机与软件工程-研究生复试-专业面试-零碎基础知识-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

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

智能推荐

oracle 12c 集群安装后的检查_12c查看crs状态-程序员宅基地

文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下：http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态：[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态

解决jupyter notebook无法找到虚拟环境的问题_jupyter没有pytorch环境-程序员宅基地

文章浏览阅读1.3w次，点赞45次，收藏99次。我个人用的是anaconda3的一个python集成环境，自带jupyter notebook，但在我打开jupyter notebook界面后，却找不到对应的虚拟环境，原来是jupyter notebook只是通用于下载anaconda时自带的环境，其他环境要想使用必须手动下载一些库：1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境

国内安装scoop的保姆教程_scoop-cn-程序员宅基地

文章浏览阅读5.2k次，点赞19次，收藏28次。选择scoop纯属意外，也是无奈，因为电脑用户被锁了管理员权限，所有exe安装程序都无法安装，只可以用绿色软件，最后被我发现scoop，省去了到处下载XXX绿色版的烦恼，当然scoop里需要管理员权限的软件也跟我无缘了（譬如everything）。推荐添加dorado这个bucket镜像，里面很多中文软件，但是部分国外的软件下载地址在github，可能无法下载。以上两个是官方bucket的国内镜像，所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn

Element ui colorpicker在Vue中的使用_vue el-color-picker-程序员宅基地

文章浏览阅读4.5k次，点赞2次，收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了，例如：这里的:sty..._vue el-color-picker

迅为iTOP-4412精英版之烧写内核移植后的镜像_exynos 4412 刷机-程序员宅基地

文章浏览阅读640次。基于芯片日益增长的问题，所以内核开发者们引入了新的方法，就是在内核中只保留函数，而数据则不包含，由用户（应用程序员）自己把数据按照规定的格式编写，并放在约定的地方，为了不占用过多的内存，还要求数据以根精简的方式编写。boot启动时，传参给内核，告诉内核设备树文件和kernel的位置，内核启动时根据地址去找到设备树文件，再利用专用的编译器去反编译dtb文件，将dtb还原成数据结构，以供驱动的函数去调用。firmware是三星的一个固件的设备信息，因为找不到固件，所以内核启动不成功。_exynos 4412 刷机

Linux系统配置jdk_linux配置jdk-程序员宅基地

文章浏览阅读2w次，点赞24次，收藏42次。Linux系统配置jdkLinux学习教程，Linux入门教程（超详细）_linux配置jdk

随便推点

matlab(4)：特殊符号的输入_matlab微米怎么输入-程序员宅基地

文章浏览阅读3.3k次，点赞5次，收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图：_matlab微米怎么输入

C语言程序设计-文件(打开与关闭、顺序、二进制读写)-程序员宅基地

文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件，可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中，对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数，而关闭则使用fclose函数。在C语言中，可以使用fread和fwrite函数进行二进制读写。‍ Biaoge 于2024-03-09 23:51发布阅读量：7 ️文章类型：【 C语言程序设计】在C语言中，用于打开文件的函数是____，用于关闭文件的函数是____。

Touchdesigner自学笔记之三_touchdesigner怎么让一个模型跟着鼠标移动-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏13次。跟随鼠标移动的粒子以grid（SOP）为partical（SOP）的资源模板，调整后连接【Geo组合+point spirit（MAT)】，在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in（CHOP)鼠标位置到metaball的坐标，实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动

【附源码】基于java的校园停车场管理系统的设计与实现61m0e9计算机毕设SSM_基于java技术的停车场管理系统实现与设计-程序员宅基地

文章浏览阅读178次。项目运行环境配置：Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX（Webstorm也行）+ Eclispe（IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持）。项目技术：Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成，B/S模式 + Maven管理等等。环境需要1.运行环境：最好是java jdk 1.8，我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计

Android系统播放器MediaPlayer源码分析_android多媒体播放源码分析时序图-程序员宅基地

文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多，会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析，后面会慢慢更新。另外，博客只作为自己学习记录的一种方式，对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析时序图

java 数据结构与算法 ——快速排序法-程序员宅基地

文章浏览阅读2.4k次，点赞41次，收藏13次。java 数据结构与算法 ——快速排序法_快速排序法