算法描述和复杂度分析

发牌程序

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, 域名服务器

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（归约）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

大数据的特征  关于大数据的特征，业内专业认识人士表示，可以用很多词语来表示。比较有代表性的即为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个人桌面，它的优点是配置起来非常简单，安装完系统之后，只要硬件不是太新，基本不用进行其他配置，硬件都可以识别并安装好驱动。而且其apt更新源服务器中的软件非常丰富，只要打一条命令，就可以自动从网络下载安装所需软件。ubuntu安装方便，甚至于可以使用wubi将linux安装在windows分区。ubuntu还有很多衍生版本，包括Kubuntu（桌面采用KDE，较为华丽），xubuntu（采用xfce，要求配置较低），eubuntu（面向儿童和教育），用户可以根据需求，偏好，和硬件配置进行选择。

　　suse，被誉为最漂亮的linux发行版本，当然，其本质和其他版本都是一样的，只是在窗口美工上开发者下了一定功夫，而且获得华丽的同时当然也需要付出更高的系统资源占用。其他的linux版本通过一些改造，完全是可以实现suse的效果的。

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

百度笔试（2014年10.12.14:00）