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

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

智能推荐

使用nginx解决浏览器跨域问题_nginx不停的xhr-程序员宅基地

文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的，浏览器出于安全考虑是禁止的。警告信息如下：不过jQuery对跨域问题也有解决方案，使用jsonp的方式解决，方法如下：$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr

在 Oracle 中配置 extproc 以访问 ST_Geometry-程序员宅基地

文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry，也就是我们所说的使用空间SQL 的方法，官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下，主要就分为以下几个步骤。..._extproc

Linux C++ gbk转为utf-8_linux c++ gbk->utf8-程序员宅基地

文章浏览阅读1.5w次。linux下没有上面的两个函数，需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数，转换过程中受到系统编码类型的影响，需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8

IMP-00009: 导出文件异常结束-程序员宅基地

文章浏览阅读750次。今天准备从生产库向测试库进行数据导入，结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误，google一下，发现可能有如下原因导致imp的数据太大，没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件，向高版本imp导出的dmp文件出错传输dmp文件时，文件损坏解决办法：imp时指定..._imp-00009导出文件异常结束

python程序员需要深入掌握的技能_Python用数据说明程序员需要掌握的技能-程序员宅基地

文章浏览阅读143次。当下是一个大数据的时代，各个行业都离不开数据的支持。因此，网络爬虫就应运而生。网络爬虫当下最为火热的是Python，Python开发爬虫相对简单，而且功能库相当完善，力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页，按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息，通过分析请求信息可以了解请..._初级python程序员能力要求

Spring @Service生成bean名称的规则（当类的名字是以两个或以上的大写字母开头的话，bean的名字会与类名保持一致）_@service beanname-程序员宅基地

文章浏览阅读7.6k次，点赞2次，收藏6次。@Service标注的bean，类名：ABDemoService查看源码后发现，原来是经过一个特殊处理：当类的名字是以两个或以上的大写字母开头的话，bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname

随便推点

二叉树的各种创建方法_二叉树的建立-程序员宅基地

文章浏览阅读6.9w次，点赞73次，收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立

解决asp.net导出excel时中文文件名乱码_asp.net utf8 导出中文字符乱码-程序员宅基地

文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能，如果文件名出现中文，便会以乱码视之。解决方法： fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码

笔记-编译原理-实验一-词法分析器设计_对pl/0作以下修改扩充。增加单词-程序员宅基地

文章浏览阅读2.1k次，点赞4次，收藏23次。第一次实验词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别，找出文件中所有的合法的单词，并给出一定的信息作为最后的结果，用于后续语法分析程序的使用；本实验针对 PL/0 语言的文法、词汇表编写一个词法分析程序，对于每个单词根据词汇表输出： (单词种类, 单词的值) 二元对。词汇表：种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词

android adb shell 权限,android adb shell权限被拒绝-程序员宅基地

文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限

投影仪-相机标定_相机-投影仪标定-程序员宅基地

文章浏览阅读6.8k次，点赞12次，收藏125次。1. 单目相机标定引言相机标定已经研究多年，标定的算法可以分为基于摄影测量的标定和自标定。其中，应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统，在标定过程中，相机拍摄多个角度下（至少两个角度，推荐10~20个角度）的标定板图像（相机和标定板都可以移动），即可对相机的内外参数进行标定。下面介绍张氏标定法（以下也这么称呼）的原理。原理相机模型和单应矩阵相机标定，就是对相机的内外参数进行计算的过程，从而得到物体到图像的投影_相机-投影仪标定

Wayland架构、渲染、硬件支持-程序员宅基地

文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的硬件支持简述：　翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构；一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。内核是从一个输入设备中获取一个事件，并通过 evdev 输入_wayland