百度笔试（2014年10.12.14:00）

 算法描写叙述和复杂度分析

发牌程序

c与c++各自是如何动态分配和释放内存的，有什么差别？

c语言提供内存动态分配的函数有：malloc、calloc、realloc，在使用这些函数时必须包括其头文件，分别为：<malloc.h>、<stdlib.h>、<alloc.h>

    1) malloc 函数： void *malloc(unsigned int size)

     在内存的动态分配区域中分配一个长度为size的连续空间。假设分配成功，则返回所分配内存空间的首地址，否则返回NULL，申请的内存不会进行初始化。

    2）calloc 函数： void *calloc(unsigned int num, unsigned int size)

     依照所给的数据个数和数据类型所占字节数，分配一个 num * size 连续的空间。

    calloc申请内存空间后。会自己主动初始化内存空间为 0，可是malloc不会进行初始化，其内存空间存储的是一些随机数据。

    3）realloc 函数： void *realloc(void *ptr, unsigned int size)

     动态分配一个长度为size的内存空间。并把内存空间的首地址赋值给ptr，把ptr内存空间调整为size。

     申请的内存空间不会进行初始化。

   释放的函数为free函数：

   free函数原型为：void free（void *ptr）

    作用：释放由上面3种函数所申请的内存空间。

    參数：ptr:指向须要释放的内存空间的首地址。

   在C++中，内存分成5个区。他们各自是堆、栈、自由存储区、全局/静态存储区和常量存储区。

   申请和释放堆中分配的存储空间，分别使用new 和 delete 的两个运算符来完毕：

   指针变量名 = new 类型名(初始化式)。

  delete 指针名；

   比如：

    int *pi = new int(0)

malloc与free是C++/C语言的标准库函数。new/delete是C++的运算符。它们都能够用于申请动态内存和释放内存。

对于非内部数据类型对象而言。光用malloc/free无法满足动态对象的要求。对象在创建的同一时候要自己主动运行构造函数。对象在消亡之前要自己主动运行析构函数。

因为malloc/free是库函数而不是运算符，不在编译器控制权限之内，不可以把运行构造函数和析构函数的任务强加于malloc/free.

有两个有序整数集合a和b，写一个函数找出它们的交集？

________________________________________

 　　方法一：

 1 　　privatestatic Set<Integer> setMethod(int[] a,int[] b){

 2        Set<Integer> set = new HashSet<Integer>();

 3        Set<Integer> set2 = new HashSet<Integer>();

 4        for(int i=0; i<a.length; i++) {

 5            set.add(a[i]);

 6        }

 7        for(int j=0; j<b.length; j++) {

 8            if(!set.add(b[j]))

 9                 set2.add(b[j]);

10         }

11        return set2;

12    }

　　方法二：

 1 　　privatestatic Set<Integer> forMethod(int[] a,int[] b){

 2        Set<Integer> set=new HashSet<Integer>();

 3        int i=0,j=0;

 4        while(i<a.length && j<b.length){

 5            if(a[i]<b[j])

 6                 i++;

 7            else if(a[i]>b[j])

 8                 j++;

 9            else{

10                 set.add(a[i]);

11                 i++;

12                 j++;

13             }

14        }

15        return set;

16    }

方法三：

 1 　　privatestatic int[] intersect(int[] a, int[] b) {

 2        if (a[0] > b[b.length – 1] || b[0] > a[a.length – 1]) {

 3            return new int[0];

 4        }

 5        int[] intersection = new int[Math.max(a.length, b.length)];

 6         int offset = 0;

 7        for (int i = 0, s = i; i < a.length && s < b.length; i++){

 8            while (a[i] > b[s]) {

 9                 s++;

10             }

11             if (a[i] == b[s]) {

12                 intersection[offset++] =b[s++];

13             }

14             while (i < (a.length – 1)&& a[i] == a[i + 1]) {

15                 i++;

16             }

17        }

18        if (intersection.length == offset) {

19             return intersection;

20        }

21        int[] duplicate = new int[offset];

22        System.arraycopy(intersection, 0, duplicate, 0, offset);

23        return duplicate;

24    }

HTTP

Hypertext Transfer Protocol, 超文本传输协议

Domain Name Server, 域名server

File Transfer Protocol , 文件传送[输]协议

Post Office Protocol, 邮局协议,用于电子邮件的接收

Simple Message Transfer Protocol, 简单邮件传输协议, 用于电子邮件的传输

Internet Control Messages Protocol, 网间控制报文协议

User Datagram Protocol, 用户数据报协议

Transfer Control Protocol, 传输控制协议

MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念”Map（映射）”和”Reduce（归约）”。和他们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。他极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序执行在分布式系统上。当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（归约）函数。用来保证全部映射的键值对中的每个共享同样的键组。

font-��l:�ВЃ�o-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin’>即为对象成员变量赋初始值，总与new运算符一起使用在创建对象的语句中。特别的一个类能够有多个构造函数。可依据其參数个数的不同或參数类型的不同来区分它们即构造函数的重载。

大数据的特征  关于大数据的特征，业内专业认识人士表示，能够用非常多词语来表示。

比較有代表性的即为2001年DougLaney最先提出“3V”模型，包含数量(Volume)、速度(Velocity)和种类 (Variety)【1】。除此之外，在3V的基础上又提出了一些新的特征。关于第四个V的说法不一，IDC 觉得大数据还应当具有价值性(Value)，大数据的价值往往呈现出稀疏性的特点。

而IBM 觉得大数据必定具有真实性(Veracity)。维基百科对大数据的定义则简单明了：大数据是指利用经常使用软件工具捕获、管理和处理数据所耗时间超过可容忍时间的数据集【2】。现在，业内人士已经将其扩展到了11个V。包含有效性、可见性等。  以下就眼下使用最多的“4V”模型进行分析。

“4V”特征主要体如今以下方面：  1.规模性（volume）        Volume指的是数据巨大的数据量以及其规模的完整性。数据的存储TB扩大到ZB。

这与数据存储和网络技术的发展密切相关。数据的加工处理技术的提高，网络宽带的成倍添加，以及社交网络技术的迅速发展。使得数据产生量和存储量成倍增长。

实质上，在某种程度上来说。数据的数量级的大小并不重要。重要的是数据具有完整性。数据规模性的应用有例如以下的体现，比方对每天12 tb的tweets进行分析，了解人们的心理状态，能够用于情感性产品的研究和开发；基于Facebook上成千上万条信息的分析。能够帮助人们处理现实中的朋友圈的利益关系。

2.快速性（Velocity）    Velocity主要表现为数据流和大数据的移动性。

现实中则体如今对数据的实时性需求上。随着移动网络的发展。人们对数据的实时应用需求更加普遍，比方通过手持终端设备关注天气、交通、物流等信息。

快速性要求具有时间敏感性和决策性的分析——能在第一时间抓住重要事件发生的信息。比方。当有大量的数据输入时（须要排除一些没用的数据）或者须要立即做出决定的情况。比方：一天之内须要审查500万起潜在的贸易欺诈案件。须要分析

5亿条日实时呼叫的具体记录，以预測客户的流失率。    3.多样性（variety）        Variety指有多种途径来源的关系型和非关系型数据。

这也意味着要在海量、种类繁多的数据间发现其内在关联。互联网时代，各种设备通过网络连成了一个总体。进入以互动为特征的Web2．0时代，个人计算机用户不仅能够通过网络获取信息。还成为了信息的制造者和传播者。这个阶段，不仅是数据量開始了爆炸式增长。数据种类也開始变得繁多【3】。除了简单的文本分析外。还能够对传感器数据、音频、视频、日志文件、点击流以及其它不论什么可用的信息。比方。在客户数据库中不仅要关注名称和地址，还包含客户所从事的职业、兴趣爱好、社会关系等。利用大数据多样性的原理就是：保留一切你须要的对你实用的信息，舍弃那些你不须要的；发现那些有关联的数据，加以收集、分析、加工，使得其变为可用的信息。

  4.价值性（value）      Value体现出的是大数据运用的真实意义所在。其价值具有稀缺性、不确定性和多样性。

“互联网女皇”Mary Meeker在2012年互联网发展趋势中。用一幅生动的图像来描写叙述大数据。一张是整整齐齐的稻草堆。另外一张是稻草中缝衣针的特写。寓意通过大数据技术的帮助，能够在稻草堆中找到你所须要的东西，哪怕是一枚小小的缝衣针。这两幅图揭示了大数据技术一个非常重要的特点，价值的稀疏性【4】。

Linux版本号

centos与rhel类似。

　　fedora。这个版本号每次发行都比較冒进。以至于非常多驱动程序都不能非常好的配置，但最新的fedora10还是非常保守和稳定的。

yu软件源基于rpm包管理

。安装软件非常方便。

　　ubuntu，基于debian，桌面环境以gnome为主，是眼下最流行的linux个人桌面，它的长处是配置起来很easy。安装完系统之后。仅仅要硬件不是太新，基本不用进行其它配置，硬件都能够识别并安装好驱动。并且其apt更新源server中的软件很丰富。仅仅要打一条命令，就能够自己主动从网络下载安装所需软件。ubuntu安装方便。甚至于能够使用wubi将linux安装在windows分区。

ubuntu还有许多衍生版本号，包含Kubuntu（桌面採用KDE，较为华丽），xubuntu（採用xfce，要求配置较低）。eubuntu（面向儿童和教育），用户能够依据需求，偏好，和硬件配置进行选择。

　　suse。被誉为最美丽的linux发行版本号，当然，其本质和其它版本号都是一样的，仅仅是在窗体美工上开发人员下了一定功夫。并且获得华丽的同一时候当然也须要付出更高的系统资源占用。其它的linux版本号通过一些改造，全然是能够实现suse的效果的。

　　redflag。中科院开发的linux版本号，主要面向政府用户。其个人桌面版免费。这个版本号的美工上与windows非常接近，是使用者的入门难度减少。但实际上桌面也是基于KDE的，非常寻常。