大端格式：

在这种格式中，字数据的高字节存储在低地址中，而字数据的低字节则存放在高地址中，如图2.1所示：

小端格式：

与大端存储格式相反，在小端存储格式中，低地址中存放的是字数据的低字节，高地址存放的是字数据的高字节。如图2.2所示：

 请写一个C函数，若处理器是Big_endian的，则返回0；若是Little_endian的，则返回1

解答：

int checkCPU( )

{

   {

          union w

          {  

                 int a;

                 char b;

          } c;

          c.a = 1;

           return(c.b ==1);

   }

}

库函数atoi c语言实现

库函数原型：

#inclue <stdlib.h>

int atoi(const char *nptr);

用法：将字符串里的数字字符转化为整形数，返回整形值。

注意：转化时跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再遇到非数字或字符串结束符号时('/0')才结束转换，并将结果返回。

例：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char *ptr1 = "-12345.12";
    char *ptr2 = "+1234w34";
    char *ptr3 = "   456er12";
    char *ptr4 = "789 123";
    int a,b,c,d;

    a = atoi(ptr1);
    b = atoi(ptr2);
    c = atoi(ptr3);
    d = atoi(ptr4);

    printf("a = %d, b = %d, c = %d, d = %d/n", a,b,c,d);

    return 0;
}

输出结果：a = 12345， b = 1234， c = 456， d = 789

***************************************************

不调用库函数用C语言实现atoi函数的功能：

#include <stdio.h>
#include <stdlib.h>

int my_atoi(const char *str);

int main(int argc, char *argv[])
{
    char *ptr = " 1234 3455";
    int n;

    n = my_atoi(ptr);
    printf("myAtoi:%d/n", n);

    n = atoi(ptr);
    printf("atoi:%d/n", n);
    return 0;
}

int my_atoi(const char *str)
{
    int value = 0;
    int flag = 1; //判断符号

    while (*str == ' ')  //跳过字符串前面的空格
    {
        str++;
    }

    if (*str == '-')  //第一个字符若是‘-’，说明可能是负数
    {
        flag = 0;
        str++;
    }
    else if (*str == '+') //第一个字符若是‘+’，说明可能是正数
    {
        flag = 1;
        str++;
    }//第一个字符若不是‘+’‘-’也不是数字字符，直接返回0
    else if (*str >= '9' || *str <= '0') 
    {
        return 0;    
    }

    //当遇到非数字字符或遇到‘/0’时，结束转化
    while (*str != '/0' && *str <= '9' && *str >= '0')
    {
        value = value * 10 + *str - '0'; //将数字字符转为对应的整形数
        str++;
    }

    if (flag == 0) //负数的情况
    {
        value = -value;
    }

    return value;
}

五大算法：贪心法，动态规划法，分治法

http://blog.sina.com.cn/s/blog_3f135d4601010lsk.html

字符串逆序

中文需要单独处理的，一个中文占两个字节，反转时顺序不变。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void reverse(char* s)

{

int len = strlen(s);

char* pNewStr = (char*)malloc(len + 1) ;

char* pNewMove = pNewStr;

char* pStr = s + len - 1;

while(pStr >= s)

{

unsigned char ch = *pStr;

if(ch > 127) //中文判断 不太确定，这个条件是否严谨，在本机测试没问题

{

*pNewMove = *(pStr - 1);

pNewMove ++;

*pNewMove= *pStr;

pNewMove ++;

pStr -= 2;

}else

{

*pNewMove =*pStr;

pNewMove ++;

pStr--;

}

}

pNewStr[len] = '';

strcpy(s,pNewStr);

free(pNewStr);

}

int main()

{  

char str[201];

printf("输入要反转的字符串n");

scanf("%s",str);

reverse(str);

printf("反转后字符变为:n %s n",str);

system("pause");

return 0;

}

top命令是Linux下常用的性能分析工具，能够实时显示系统中各个进程的资源占用状况，类似于Windows的任务管理器。

Linux下2种定时执行任务方法

　　(1)at命令

　　假如我们只是想 要让特定任务运行一次,那么，这时候就要用到at监控程序了。

　　设置at命令很简单，指示定运行的时间，那么就会在哪个时候运行。at类似打印 进程，会把任务放到/var/spool/at目录中，到指定时间运行它 。at命令相当于另一个shell，运行at time命令时，它发送一个个命令，可以输入任意命令或者程序。at now + time命令可以在指示任务。

　　假设处理一个大型数据库，要在别人不用系统时去处理数据，比如凌晨3点10分。那么我们就应该先建立/home/kyle/do_job脚本管理数据库，计划处理/home/kyle/do_job文件中的结果。正常方式是这样启动下列命令:

　　# at 2:05 tomorrow

　　at>/home/kyle/do_job

　　at> Ctrl+D

　　AT Time中的时间表示方法

　　-----------------------------------------------------------------------

　　时 间 例子 说明

　　-----------------------------------------------------------------------

　　Minute at now + 5 minutes 任务在5分钟后运行

　　Hour at now + 1 hour 任务在1小时后运行

　　Days at now + 3 days 任务在3天后运行

　　Weeks at now + 2 weeks 任务在两周后运行

　　Fixed at midnight 任务在午夜运行

　　Fixed at 10:30pm 任务在晚上10点30分

　　注意：一定要检查一下atq的服务是否启 动，有些操作系统未必是默认启动的， linux默认为不启动，而ubuntu默认为启动的。检查是否启动，用service atd检查语法，用service atd status检查atd的状态，用service atd start启动atd服务。

　　查看at执行的具体内容：一般位于/var/spool/at目录下面， 用vi打开，在最后一部分就是你的执行程序

　　(2)crontab

　　cron是一个linux下 的定时执行工具，可以在无需人工干预的情况下运行作业。由于Cron 是Linux的内置服务，但它不自动起来，可以用以下的方法启动、关闭这个服务：

　　/sbin/service crond start //启动服务

　　/sbin/service crond stop //关闭服务

　　/sbin/service crond restart //重启服务

　　/sbin/service crond reload //重新载入配置

　　/sbin/service crond status //查看服务状态

　　你也可以将这个服务在系统启 动的时候自动启动：

　　在/etc/rc.d/rc.local这个脚本的末尾加上：

　　/sbin/service crond start

　　现在Cron这个服务已经在进程里面了，我们就可以用这个服务了，Cron服务提供以下几种接口供大家使用：

　　1、直接用crontab命 令编辑

　　cron服务提供 crontab命令来设定cron服务的，以下是这个命令的一些参数与说明：

　　crontab -u //设定某个用户的cron服务，一般root用户在执行这个命令的时候需要此参数

　　crontab -l //列出某个用户cron服务的详细内容

　　crontab -r //删除某个用户的cron服务

　　crontab -e //编辑某个用户的cron服务

　　比如说root查看自己的cron设置：crontab -u root -l

　　再例 如，root想删除fred的cron设置：crontab -u fred -r

　　基本格式 :

　　*　　*　　*　　*　　*　　command

　　分　 时　 日　 月　 周　 命令

　　第1列表示分钟1～59 每分钟用*或者 */1表示

　　第2列表示小时1～23(0表示0点)

　　第3列表示日期1～31

　　第4列表示月份1～12

　　第5列标识号星期0～6(0表示星期天)

　　第6列要运行的命令

　　crontab文件的一些例子：

　　#每晚的21:30重启apache。

　　30 21 * * * /usr/local/etc/rc.d/lighttpd restart

　　#每月1、10、22日

　　45 4 1,10,22 * * /usr/local/etc/rc.d/lighttpd restart

　　#每天早上6点10分

　　10 6 * * * date

　　#每两个小时

　　0 */2 * * * date

　　#晚上11点到早上8点之间每两个小时，早上8点

　　0 23-7/2，8 * * * date

　　#每个月的4号和每个礼拜的礼拜一到礼拜三的早上11点

　　0 11 4 * mon-wed date

　　#1月份日早上4点

　　0 4 1 jan * date

malloc,free和new,delete有区别吗？如果有，是什么？

1,malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
2, 对于非内部数据类型的对象而言，光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。
3,因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new，以一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。
4,C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存

进程是程序的一次执行，线程可以理解为进程中的执行的一段程序片段。在一个多任务环境中下面的概念可以帮助我们理解两者间的差别：  
      进程间是独立的，这表现在内存空间，上下文环境；线程运行在进程空间内。  
      一般来讲（不使用特殊技术）进程是无法突破进程边界存取其他进程内的存储空间；而线程由于处于进程空间内，所以同一进程所产生的线程共享同一内存空间。
      同一进程中的两段代码不能够同时执行，除非引入线程。  
线程是属于进程的，当进程退出时该进程所产生的线程都会被强制退出并清除。  
      线程占用的资源要少于进程所占用的资源。  
      进程和线程都可以有优先级。  
      在线程系统中进程也是一个线程。可以将进程理解为一个程序的第一个线程。

以下程序的输出结果是：0120；

#include <stdio.h>
void eit(int n);
int main(void)
{
    int a = 3;
    eit(a);
    return 0;
}
void eit(int n)
{
    if (n > 0)
    {
        eit(--n);
        printf("%d", n);
        eit(--n);
    }
}

c++面试题：#define MIN(A,B) ( (A) <= (B) ? (A) : (B) )

搜索引擎是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。百度和谷歌等是搜索引擎的代表。

就是对地图中的特征点如何获取

1、给定一个数组a[N],我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。在构造过程：
不允许使用除法；
要求O(1)空间复杂度和O(n)时间复杂度；
除遍历计数器与a[N] b[N]外，不可使用新的变量(包括栈临时变量、对空间和全局静态变量等)；
请用程序实现并简单描述。
解答：数组分割

10 void output(long long* a, int len)
20 /*
21 题目要求的算法
22 */
23 /************************************************************************/
24 void problem(int* a, long long* b, int N)
25 {
26     b[0] = 1;
27     for(int i = 1; i < N; ++i)
28     {
29         b[i] = b[i-1] * a[i-1]; // 分水岭的前半段乘积
30     }
31
32     b[0] = a[N - 1];
33     for(int i = N - 2; i >= 1; --i)
34     {
35         b[i] *= b[0];
36         b[0] *= a[i]; // 分水岭的后半段乘积，是从数组尾部向前循环的
37     }
38 }
1.一个正确的二分法。
  
二分查找用于在多条记录中快速找到待查找的记录。它的思想是：每次将查找的范围缩小一半，直到最后找到记录或者找不到记录返回。
  
二分查找的时间复杂度为O(logn)
   二分法的递归和非递归算法如下
 i.非递归算法。



[cpp] view plaincopyprint?


1. int binary_search(int arr[],int n ,int key){ 

2.     int mid; 

3.     int low = 0,high = n-1; 

4.     while(low <= high){  //防止死循环

5.         mid =  low + (high - low)/2;   //中间元素，防止溢出  

6.         if(key == arr[mid]) return mid;//找到时返回
7.  

8.         else if(key > arr[mid]){ 

9.             low = mid + 1;//在更高的区间搜索  

10.         }else{ 

11.             high = mid - 1;//在更低的区间搜索  

12.         } 

13.     } 

14.     return -1;//没有找到元素，返回-1
15.  

16. } 


   ii.递归算法：



[cpp] view plaincopyprint?


1. int binary_search(int arr[],int low,int high,int key){ 

2.     if(low > high) return -1; 

3.     int mid =  low + (high - low)/2   //中间元素，防止溢出  

4.     if(key == arr[mid])return mid;//找到时返回
5.  

6.     else if(key > arr[mid]){ 

7.         return binary_search(arr,mid + 1,high,key);/在更高的区间搜索 

8.     }else{ 

9.         return binary_search(arr,low,mid - 1,key);/在更低的区间搜索 

10.     } 

11.    } 
12.
经典书籍推荐，主要是linux C方面的，我把我看过或者了解的简单说一下。
C语言：
C程序设计语言 --
没有太细的看，而且修为不够，所以没啥感觉
C和指针 -- 感觉这本书倒很适合做大一的教材，比较经典。
C陷阱与缺陷 --
两天就能看完吧，比较简单，只要了解一些变态语法就行。
C专家编程 --
我没看。但九度貌似有word版总结这几本书的，那个word看完了。确实总结的很不错。
个人重点推荐C和指针 +
C陷阱缺陷

C++
C++ Primer -- 看了两遍吧；实习生面试前一遍；暑假一遍；
高质量程序设计指南C/C++ --
6月初看的一遍，这本书很不错，很多黑体重要结论，引经据典，回答C++的问题能够拎上的话加分不少。
深度搜索C++对象模型 --
6月份看的，有点小难，而且意义不是很大，了解一个逻辑模型就可以了，而且里面本身就有很多错误。
STL源码剖析 --
暑假看的更是扫描的看的。重原理，轻细节，纠结详尽的模板语法对菜鸟来说估计会死。
Effective C++ --
每天整理两三个条款，我觉得这种条款类的书很适合闲暇时间看。
More Effective C++ --
就挑了几个常考的条款看了看，挺好的。
Effective STL --
仅看了几个条款。

软件基础知识，个人认为最好都通晓点：
数据结构 & 算法设计分析 --
算法导论对我这菜鸟实在啃不动。就整了考研时李春葆的课本 + 清华那本计算机算法设计与分析。
操作系统原理 -- 汤子瀛的课本 整了整进程调度 +
内存那块。
计算机网络 -- 谢希仁的课本 整了整网络层 + 传输层。
数据库系统实现 --
结合pg源码看的。同样，也是看到编译执行，并发事务没看。
搜索引擎-信息检索实践 --
9月中旬才买的书，忽悠搜索引擎用的，但整天在面试，基本没看。但看看挺好的。忽悠百度、搜狗、有道啥的有用。
大话设计模式 --
就看了几个模式。本来就一个暑假，不可能样样都知道，实验室老板还逼着看Totem源代码（实验室基于PostgreSQL自己开发的扩展版数据库，代码更改了近三分之一啊感觉，也就不奇怪当年开发实验室自己数据库那帮人很多去搞Oracle
DB2了，武大最后三年制变两年制的最后一届）
个人推荐：数据结构和算法最重要啊还是，另外，建议大家买的专业课考研资料不要卖啊。看重点很有用。

Linux/Unix程序设计部分
Linux程序设计，过年开学正月十五去光谷玩时在华科买的，5月份差不多主要部分就看完了。了解了这么些系统调用。啥的。
UNIX环境高级编程
6月18号 - 7月30号 看了两遍，并做了笔记。挺好的。
POSIX多线程程序设计
第二遍看APUE时附带看的，这本书很早就绝版了，电子版貌似也不多。
TCP/IP Sockets编程(C语言实现)
简单的入门书。200页很薄。
TCP/IP高效编程
真本书是条款的，44个条款。大概也就看了前十多个条款。挺好的，有时间的话这两本加起来基本可以了，UNIX网络编程那两卷加起来都可以镇宅用了，能看？
重点推荐UNIX环境高级编程
+
TCP/IP高效编程啊。后边那本书44个条款对网络编程绝对是一个很好的总结。另外shell/python啥的，反正找工作时候自学了一点，基本不会。也没重点去看，所以没啥推荐的。

应试啊，应试啊：
编程之美--至少今年很多题还出自这里面，必不可少。。。
程序员面试宝典
-- 三天就能看完，真要沦落到看这本书，那。。。除非技术正的大牛。。。
程序员求职成功路：技术、求职技巧与软实力培养 --
就算看应试的书，个人推荐还是看这本吧，讲的很多都比较有深度。尤其前几章C内存的部分。
程序员面试攻略 --
题目比较老，但是看看有助于思维发散。
《编程之美:
求二叉树中节点的最大距离》的另一个解法
昨天花了一个晚上为《编程之美》，在豆瓣写了一篇书评《迟来的书评和感想──给喜爱编程的朋友》。书评就不转载到这里了，取而代之，在这里介绍书里其中一条问题的另一个解法。这个解法比较简短易读及降低了空间复杂度，或者可以说觉得比较「美」吧。

问题定义

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

我也想不到更好的分析方法。

书上的解法

书中对这个问题的分析是很清楚的，我尝试用自己的方式简短覆述。

计算一个二叉树的最大距离有两个情况:


情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。

情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。

只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。



我也想不到更好的分析方法。

但接着，原文的实现就不如上面的清楚 (源码可从这里下载):



?




// 数据结构定义
struct NODE
{
    NODE* pLeft;        // 左子树
    NODE* pRight;       // 右子树
    int nMaxLeft;       // 左子树中的最长距离
    int nMaxRight;      // 右子树中的最长距离
    char chValue;       // 该节点的值
};
 
int nMaxLen = 0;
 
// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
    // 遍历到叶子节点，返回
    if(pRoot == NULL)
    {
        return;
    }
 
    // 如果左子树为空，那么该节点的左边最长距离为0
    if(pRoot -> pLeft == NULL)
    {
        pRoot -> nMaxLeft = 0;
    }
 
    // 如果右子树为空，那么该节点的右边最长距离为0
    if(pRoot -> pRight == NULL)
    {
        pRoot -> nMaxRight = 0;
    }
 
    // 如果左子树不为空，递归寻找左子树最长距离
    if(pRoot -> pLeft != NULL)
    {
        FindMaxLen(pRoot -> pLeft);
    }
 
    // 如果右子树不为空，递归寻找右子树最长距离
    if(pRoot -> pRight != NULL)
    {
        FindMaxLen(pRoot -> pRight);
    }
 
    // 计算左子树最长节点距离
    if(pRoot -> pLeft != NULL)
    {
        int nTempMax = 0;
        if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
        {
            nTempMax = pRoot -> pLeft -> nMaxLeft;
        }
        else
        {
            nTempMax = pRoot -> pLeft -> nMaxRight;
        }
        pRoot -> nMaxLeft = nTempMax + 1;
    }
 
    // 计算右子树最长节点距离
    if(pRoot -> pRight != NULL)
    {
        int nTempMax = 0;
        if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
        {
            nTempMax = pRoot -> pRight -> nMaxLeft;
        }
        else
        {
            nTempMax = pRoot -> pRight -> nMaxRight;
        }
        pRoot -> nMaxRight = nTempMax + 1;
    }
 
    // 更新最长距离
    if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
    {
        nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
    }
}

有一个数组，该数组的特点是：前一部分递增有序，后一部分递减有序，求数组的峰值位置
我们发现，给出的数组可能有如下三种形态：

其中后两种情况是属于特殊的，是有序数组，峰值的位置就是数组的开始或结束索引。我们单单考虑第一种情况。
思考1：线性扫描,思路最简单，也最容易实现，只需扫描 一遍数组，比较当前元素与前一个元素的大小关系，一旦碰到当前元素比前一元素小，前一元素就是峰值。或者比较当前元素与后一元素，一旦后一元素比当前元素小，当前元素就是峰值。此方法的缺点是需要线性时间O(n)
思考2：考虑二分搜索，如果不考虑情况2和情况3.对于情况一而言，mid中间元素的位置不外乎三个情况：

是不是跟二分搜索很类似？
我们可以根据中间元素与两边元素的大小关系，判断搜索左边还是右边。据此，不难写出如下代码（未经严格测试）：
[cpp] view plaincopyprint?
1. #include <stdio.h>  
2.  
3. //数组是先增后减数组。  
4. int findMax(int *a ,int n){ 
5.     int low = 0,high = n-1,mid; 
6.     while(low <= high){ 
7.         mid = low + ((high-low)>>1); 
8.         if((mid + 1)<=high && (mid-1)>=low){ 
9.             if(a[mid] >= a[mid-1] && a[mid] >= a[mid + 1]){ 
10.                 return mid; 
11.             }else if(a[mid] >= a[mid-1] && a[mid] <=a[mid + 1]){ 
12.                 low = mid + 1; 
13.             }else{ 
14.                 high = mid - 1; 
15.             } 
16.         }else if((mid+1) <= high){ 
17.             if(a[mid] <= a[mid+1]){ 
18.                 return mid+1; 
19.             }else{ 
20.                 return mid; 
21.             } 
22.         }else{ 
23.             if(a[mid] <= a[mid-1]){ 
24.                 return mid-1; 
25.             }else{ 
26.                 return mid; 
27.             } 
28.         } 
29.  
30.     } 
31. } 
32.  
33. int main(){ 
34.     int a[] = {1,2,7,6,5,4,3,1}; 
35.     printf("%d n",findMax(a,8)); 
36. }  

OSI七层划分
各层功能
应用层（Application Layer）
　　与其它计算机进行通讯的一个应用，它是对应应用程序的通信服务的。例如，一个没有通信功能的字处理程序就不能执行通信的代码，从事字处理工作的程序员也不关心OSI的第7层。但是，如果添加了一个传输文件的选项，那么字处理器的程序员就需要实现OSI的第7层。示例：telnet，HTTP,FTP,NFS,SMTP等。
表示层（Presentation Layer）
　　这一层的主要功能是定义数据格式及加密。例如，FTP允许你选择以二进制或ASCII格式传输。如果选择二进制，那么发送方和接收方不改变文件的内容。如果选择ASCII格式，发送方将把文本从发送方的字符集转换成标准的ASCII后发送数据。在接收方将标准的ASCII转换成接收方计算机的字符集。示例：加密，ASCII等。
会话层（Session Layer）
　　它定义了如何开始、控制和结束一个会话，包括对多个双向消息的控制和管理，以便在只完成连续消息的一部分时可以通知应用，从而使表示层看到的数据是连续的，在某些情况下，如果表示层收到了所有的数据，则用数据代表表示层。示例：RPC，SQL等。
传输层（Transport Layer）
　　这层的功能包括是否选择差错恢复协议还是无差错恢复协议，及在同一主机上对不同应用的数据流的输入进行复用，还包括对收到的顺序不对的数据包的重新排序功能。示例：TCP，UDP，SPX。
网络层（Network Layer）
　　这层对端到端的包传输进行定义，它定义了能够标识所有结点的逻辑地址，还定义了路由实现的方式和学习的方式。为了适应最大传输单元长度小于包长度的传输介质，网络层还定义了如何将一个包分解成更小的包的分段方法。示例：IP,IPX等。
数据链路层（Data Link Layer）
　　它定义了在单个链路上如何传输数据。这些协议与被讨论的各种介质有关。示例：ATM，FDDI等。
物理层（Physical Layer）
　　OSI的物理层规范是有关传输介质的特性标准，这些规范通常也参考了其他组织制定的标准。连接头、帧、帧的使用、电流、编码及光调制等都属于各种物理层规范中的内容。物理层常用多个规范完成对所有细节的定义。示例：Rj45，802.3等。
　在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
第一次握手：建立连接时，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认；
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个SYN包（syn=k），即SYN+ACK包，此时服务器进入SYN_RECV状态； 第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。 完成三次握手，客户端与服务器开始传送数据.

多线程同步方法
现在流行的进程线程同步互斥的控制机制，其实是由最原始最基本的4种方法实现的：
   1临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

　　2互斥量:为协调共同对一个共享资源的单独访问而设计的。

　　3信号量:为控制一个具有有限数量用户资源而设计。

　　4事件:用来通知线程有一些事件已发生，从而启动后继任务的开始。
临界区（Critical Section）

　　保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。
临界区包含两个操作原语： EnterCriticalSection（）进入临界区 LeaveCriticalSection（）离开临界区
 
互斥量（Mutex）
  
　　互斥量跟临界区很相似，只有拥有互斥对象的线程才具有访问资源的权限，由于互斥对象只有一个，因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出，以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。
 
  　　互斥量包含的几个操作原语：
  　　CreateMutex（）创建一个互斥量
  　　OpenMutex（）打开一个互斥量
  　　ReleaseMutex（）释放互斥量
  　　WaitForMultipleObjects（）等待互斥量对象
 
 
信号量（Semaphores）

　　信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore（）创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就会减1，只要当前可用资源计数是大于0的，就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目，不能在允许其他线程的进入，此时的信号量信号将无法发出。线程在处理完共享资源后，应在离开的同时通过ReleaseSemaphore（）函数将当前可用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。

　　PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用共享资源的进程数。

　　 P操作申请资源：
  　　（1）S减1；
  　　（2）若S减1后仍大于等于零，则进程继续执行；
  　　（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。
　　
　　V操作 释放资源：
  　　（1）S加1；
  　　（2）若相加结果大于零，则进程继续执行；
  　　（3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。
 
  　　信号量包含的几个操作原语：
  　　CreateSemaphore（）创建一个信号量
  　　OpenSemaphore（）打开一个信号量
  　　ReleaseSemaphore（）释放信号量
  　　WaitForSingleObject（）等待信号量
 
　事件（Event）
  
　　事件对象也可以通过通知操作的方式来保持线程的同步。并且可以实现不同进程中的线程同步操作。
总结：

　　1． 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。

　　2． 互斥量（Mutex），信号灯（Semaphore），事件（Event）都可以被跨越进程使用来进行同步数据操作，而其他的对象与数据同步操作无关，但对于进程和线程来讲，如果进程和线程在运行状态则为无信号状态，在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和线程退出。

　　3． 通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号灯对象可以说是一种资源计数器。
         这里有一个初学者经常混淆的概念。覆盖（override）和重载（overload）。上面说了，覆盖是指子类重新定义父类的虚函数的做法。而重载，是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同）。其实，重载的概念并不属于“面向对象编程”，重载的实现是：编译器根据函数不同的参数表，对同名函数的名称做修饰，然后这些同名函数就成了不同的函数（至少对于编译器来说是这样的）。如，有两个同名函数：function   func(p:integer):integer;和function   func(p:string):integer;。那么编译器做过修饰后的函数名称可能是这样的：int_func、str_func。对于这两个函数的调用，在编译器间就已经确定了，是静态的（记住：是静态）。也就是说，它们的地址在编译期就绑定了（早绑定），因此，重载和多态无关！真正和多态相关的是“覆盖”。当子类重新定义了父类的虚函数后，父类指针根据赋给它的不同的子类指针，动态（记住：是动态！）的调用属于子类的该函数，这样的函数调用在编译期间是无法确定的（调用的子类的虚函数的地址无法给出）。因此，这样的函数地址是在运行期绑定的（晚邦定）。结论就是：重载只是一种语言特性，与多态无关，与面向对象也无关！

字节对齐
其实字节对齐的细节和具体编译器实现相关，但一般而言，满足三个准则：1) 结构体变量的首地址能够被其最宽基本类型成员的大小所整除；2) 结构体每个成员相对于结构体首地址的偏移量都是成员大小的整数倍，如有需要编译器会在成员之间加上填充字节；例如上面第二个结构体变量的地址空间。3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要编译器会在最末一个成员之后加上填充字节。
五 小结与领悟
进行字节对齐的原因是因为处理器在存取内存的时候并不是一个字节一个字节操作的， 通常他会一次存取多个字节， 比如四个。所以将数据以四字节对齐方式存储能够提高数据存取效率(其实具体的存储和对齐方式没那么简单，不说了)。但是， 有时候这种默认的优化并不是我们想要的。比如在设计网络程序的时候，一般情况下我们会定义一个结构体来表示应用程协议的协议头，如果通信双方的程序是在不同体系结构的计算机编译出来的(这很有可能)，那么默认的对齐方式是有可能是不同的，这样解析出来的协议头必然就是错的。 另外即使很幸运的对齐方式一样，在协议头里面插入了几个无关的字节那也是很不优雅的何况还占用带宽。
C++笔试题 String类的实现 三大复制控制函数
分类： 著名IT笔试题 C++实现 2011-08-08 10:37 501人阅读 评论(1) 收藏 举报
 
#include<iostream>
using namespace std;
class String
{
  friend ostream& operator<<(ostream& out,const String& str)  //输出操作符重载
  {
   return str.Print(out);
  }
  public:
 String(const char *str = 0);// 普通构造函数
 String(const String &other); // 拷贝构造函数
 ~String(void) { delete [] data_; }// 析构函数
 String& operator=(const String &other);// 赋值函数
 char* data(void) const { return data_; }
  private:
 ostream& Print(ostream& out) const;
 char   *data_;    // 用于保存字符串
};
//赋值操作符首先要注意是不是自己赋给自己，如果是这样的话什么也不做，把自己返回即可。
//其次就是别人赋值给自己，这时首先要自己把原来的值扔到，根据别人的大小开辟一块空间
//准备盛放别人的内容，最后不要忘了返回对自己的引用。
String& String::operator =(const String& other)
{
 if(this!=&other)
 {
  delete [] data_;
  size_t length=strlen(other.data());
  data_=new char[length+1];
  strcpy_s(data_,length+1,other.data());
 }
 return *this;
}
//复制构造函数总是发生在构造阶段，所以此时成员data_还没有空间可以使用，应该先根据别
//人空间的大小开辟好空间，然后在把别人的内容拷贝进来。
String::String(const String &other)
{
 size_t length=strlen(other.data());
 data_=new char[length+1];
 strcpy_s(data_,length+1,other.data());
}
//由于输出操作符通常写成类的友元函数，这样就可以写类似cout<<s;如果不是这样使用起来就会
//很奇怪，比如可能是s.print()之类，无法像cout<<s<<s1<<endl;那样和标准库完美结合，甚至如果
//你写了一个ostream& operator<<(ostream& out,const String& str)忘了加上友元声明，编译器
//会认为你是重载了一元移位操作符<<，而且参数还加多了。
//输出操作符的经典写法就像本文这样，另加一个Print成员函数来完成干活的功能让<<来调用，之所
//以返回ostream& 也是和C++语言内建操作符机制保持一致，这样就可以写cout<<s<<s1<<endl;而不是
//cout<<s;cout<<s1;cout<<endl;
ostream& String::Print(ostream& out) const
{
 out<<data_;
 return out;
}
//此构造函数可以支持隐式类型转换比如你可以这样创建一个String对象 String s("Hello World !");此语句
//就是在调用这个构造函数，另外String s="Hello World !";会被解释成String s=Sting("Hello World !");先
//根据字符数组构造一个临时String对象(此对象在这条语句执行完之后就被析构)，并紧接着调用String的赋值
//操作符重载函数
String::String(const char *str) // 6分
{
 if(str==NULL)                         
 {
  data_=new char[1];// 若能加 NULL 判断则更好
  *data_='';                     
 }                                       
 else
 {
  size_t length = strlen(str);          
  data_ = new char[length+1]; // 若能加 NULL 判断则更好     
  strcpy_s(data_,length+1, str);               
 }
}
void main()
{
 char* p="Hello World !";
 String s(p);
 cout<<s<<endl;
 String s1("How are you ?");
 cout<<s1<<endl;
 s1=s;
 cout<<s<<endl<<s1<<endl;
 s=s=s1;
 cout<<s<<endl<<s1<<endl;
}
strcpy()、memcpy()、memmove()、memset()的实现
一直想知道内部实现, 现在想看了, 就找了一下.
不错.
strcpy()、memcpy()、memmove()、memset()的实现
 
strcpy(), 字符串拷贝.
char *strcpy(char *strDest, const char *strSrc)
{
    assert((strDest!=NULL) && (strSrc !=NULL));
    char *address = strDest;    
    while( (*strDest++ = * strSrc++) != '')
       NULL ;
    return address ;      
}
memcpy, 拷贝不重叠的内存块
void *memcpy(void* pvTo, void* pvFrom, size_t size) //byte是java里的变量类型
{
assert(pvTo != NULL && pvFrom != NULL);
void* pbTo = (byte*)pvTo;
void* pbFrom = (byte*)pvFrom;
/* 内存块重叠吗？如果重叠，就使用memmove */
assert(pbTo>=pbFrom+size || pbFrom>=pbTo+size);
while(size-->0)
    *pbTo++ == *pbFrom++;
return pvTo;
}
void *MemCopy(void *dest,const void *src,size_t count)
{
    char *pDest=static_cast<char *>(dest);
    const char *pSrc=static_cast<const char *>(src);
    if( pDest>pSrc && pDest<pSrc+count )
    {
        for(size_t i=count-1; i<=0; ++i)
        {
            pDest[i]=pSrc[i];
        }
    }
    else
    {
        for(size_t i=0; i<count; ++i)
        {
             pDest[i]=pSrc[i];
        }
    }
    return pDest;
}
void *Memmove(void *Dst, const void*Src,size_t count)
{
assert(Dst && Src);
void* pDst = Dst;
if (Dst<Src && (char*)Dst > (char*)Src + count)
{
while(count--)
{
   *(char*)Dst = *(char*)Src;
   Dst = (char*)Dst + 1;
   Src = (char*)Src + 1;
}
}
else
{
   Dst = (char*)Dst + count - 1;
   Src = (char*)Src + count - 1;
   while(count--)
   {
      *(char*)Dst = *(char*)Src;
      Dst = (char*)Dst -1 ;
      Src = (char*)Src -1 ;
   }
}
return pDst;
}

void* memmove(void *dest, const void *src,size_t n)
{
    if (n == 0) return 0;
    if (dest == NULL) return 0;
    if (src == NULL)    return 0;
    char *psrc = (char*)src;
    char *pdest = (char*)dest;
    if((dest <= psrc) || (pdest >= psrc + n)) /*检查是否有重叠问题 */
        {
         for(int i=0; i < n; i++) /*正向拷贝*/
          {
           *pdest = *psrc;
           psrc++;
           pdest++;
          }
        }
        else /*反向拷贝*/
        {
          psrc += n;
          pdest += n;
          for(int i=0;i<n;i++)
           {
            psrc--;
            pdest--;
            *pdest = *psrc;
           }
        }
   return dest;
}
memset:把buffer所指内存区域的前count个字节设置成字符c
void * Memset(void* buffer, int c, int count)
{
char* pvTo=(char*)buffer;
assert(buffer != NULL);
while(count-->0)
*pvTo++=(char)c;
return buffer;
}
内存池的实现(一)
引言
C/C++下内存管理是让几乎每一个程序员头疼的问题，分配足够的内存、追踪内存的分配、在不需要的时候释放内存——这个任务相当复杂。而直接使用系统调用malloc/free、new/delete进行内存分配和释放，有以下弊端：
1. 调用malloc/new,系统需要根据“最先匹配”、“最优匹配”或其他算法在内存空闲块表中查找一块空闲内存，调用free/delete,系统可能需要合并空闲内存块，这些会产生额外开销
2. 频繁使用时会产生大量内存碎片，从而降低程序运行效率
3. 容易造成内存泄漏

内存池（memory pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法，当我们申请内存空间时，首先到我们的内存池中查找合适的内存块，而不是直接向操作系统申请，优势在于：
1. 比malloc/free进行内存申请/释放的方式快
2. 不会产生或很少产生堆碎片
3. 可避免内存泄漏

内存池设计
看到内存池好处这么多，是不是恨不能马上抛弃malloc/free，投奔内存池的怀抱呢？且慢，在我们自己动手实现内存池之前还需要明确以下几个问题：
1. 内存池的空间如何获得？是程序启动时分配一大块空间还是程序运行中按需求分配？
2. 内存池对到来的内存申请，有没有大小的限制？如果有，最小可申请的内存块为多大，最大的呢？
3. 如何合理设计内存块结构，方便我们进行内存的申请、追踪和释放呢？
4. 内存池占用越多空间，相对应其他程序能使用的内存就越少，是否要设定内存池空间的上限？设定为多少合适呢？
带着以上问题，我们来看以下一种内存池设计方案。

内存池实现方案一
从这里下载该内存池实现的源码。
首先给出该方案的整体架构，如下：

图1.内存池架构图
结构中主要包含block、list 和pool这三个结构体，block结构包含指向实际内存空间的指针，前向和后向指针让block能够组成双向链表；list结构中free指针指向空闲内存块组成的链表，used指针指向程序使用中的内存块组成的链表，size值为内存块的大小，list之间组成单向链表；pool结构记录list链表的头和尾。

内存跟踪策略
该方案中，在进行内存分配时，将多申请12个字节，即实际申请的内存大小为所需内存大小+12。在多申请的12个字节中，分别存放对应的list指针（4字节）、used指针（4字节）和校验码（4字节）。通过这样设定，我们很容易得到该块内存所在的list和block，校验码起到粗略检查是否出错的作用。该结构图示如下：

图2.内存块申请示意图
图中箭头指示的位置为内存块真正开始的位置。

内存申请和释放策略
申请：根据所申请内存的大小，遍历list链表，查看是否存在相匹配的size；
　　　　存在匹配size：查看free时候为NULL
　　　　　　free为NULL：使用malloc/new申请内存，并将其置于used所指链表的尾部
　　　　　　free不为NULL：将free所指链表的头结点移除，放置于used所指链表的尾部
　　　　不存在匹配size：新建list，使用malloc/new申请内存，并将其置于该list的used所指链表尾部
　　　返回内存空间指针
释放：根据内存跟踪策略，获取list指针和used指针，将其从used指针所指的链表中删除，放置于free指针所指向的链表

对方案一的分析
对照“内存池设计”一节中提出的问题，我们的方案一有以下特点：
1. 程序启动后内存池并没有内存块，到程序真正进行内存申请和释放的时候才接管内存块管理；
2. 该内存池对到来的申请，对申请大小并不做限制，其为每个size值创建链表进行内存管理；
3. 该方案没有提供限定内存池大小的功能

结合分析，可以得出该方案应用场景如下：程序所申请的内存块大小比较固定（比如只申请/释放1024bytes或2048bytes的内存），申请和释放的频率基本保持一致（因申请多而释放少会占用过多内存，最终导致系统崩溃）。

这篇文章讲解了内存管理的基本知识，以一个简单的内存池实现例子作为敲门砖，引领大家认识内存池，下一篇为内存池进阶文章，讲解apache服务器中内存池的实现方法

风魂引擎学习之设计内存池
2010-12-14 10:23| 发布者: annmax| 查看: 1151| 评论: 0
摘要: 内存池是指一次性向系统申请较大的内存块（block），根据程序使用需要再划分为不同大小的内存块（smaller chunks），当向内存池申请空间的时候就取出分配好的chunk。当内存块使用完再次向系统申请block，再次划分为c ...
内存池是指一次性向系统申请较大的内存块（block），根据程序使用需要再划分为不同大小的内存块（smaller chunks），当向内存池申请空间的时候就取出分配好的chunk。当内存块使用完再次向系统申请block，再次划分为chunks。内存池实现了自定义的分配方式，它有两个作用：
1．提高内存分配的使用效率
2．可以用来记录内存的使用情况，特别包括内存泄露检查。
《风魂》里使用的是块固定大小的带内存泄露检查的内存池，下面具体说：
1  从总体上说，内存池对小内存块和大内存区分处理，而所谓大小则可以根据程序需求。像引擎里则以256字节为标准，小于256字节的为小内存块，大于256字节的为大内存块。大内存块直接向系统申请，小内存块再以8字节为单位分为不同的大小：8，16，24…到256，总共有256/8 = 32种大小的chunk。chunk是我们直接进行操作的对象。chunk除了需要保存自定义的数据之外，同时还需要保存chunk大小的信息，这样子删除chunk时候才可以将其归还给内存池；若在需要检查内存泄露的情况下，还要保存文件名，文件行数等等信息。
2  我们操作的对象都是针对chunk的进行的，因此在内存池中，chunk是以链表组织起来的，每个chunk都链接到下一个的chunk。“空闲列表”用来保存已经被分配的待使用的chunk，如果被使用了，chunk就从链表中移走。引擎里有32种不同大小的chunk，也就是32个链表保存在一个数组里。当chunk归还内存池时，则根据chunk本身的大小信息找到对应的列表插入。因为同个列表的chunk直接并无差异，不管申请还是归还直接对表头进行操作即可。
3  “总列表”是用来记录每次向系统申请的内存指针和大小，也就是每次当空闲列表为空时申请内存时，除了更新空闲列表本身，也同时要加入总列表中。这样子总列表就保存了所有内存池向系统申请的内存，只需对它进行删除就可以将去内存池所有内存归还系统。同时，由于总列表保存所有的chunk，而空闲列表保存着当前可以使用的chunk，那么程序最后结束时，内存泄露chunk = 总列表chunk - 空闲列表chunk。
4 大内存chunk则直接对系统内存进行操作，同样使用链表保存大内存chunk。申请时向系统申请并且加入链表，释放时归还系统并且从链表取出。最后链表剩下的chunk就是内存泄露了。
接下来看下《风魂》里的小内存chunk
代码
struct memory_cookie {
#ifdef _DEBUG
   const char *file;           //文件名
   unsigned line;              //文件行数
   unsigned id;                //全局id
#endif
   size_t size;                //chunk大小
   union {
      memory_cookie *next;     //下一链表节点
      unsigned char data[1];   //数据区
   };
};
上面说过，chunk必须除了保存自定义的数据，还需要记录chunk本身的大小，还有下一个chunk指针。在debug模式下，同时还记录了文件名，行数，一个id（全局累加），这些信息用于提供内存泄露检查的，所以只在debug模式下需要。注意next指针和data是采用union的方式组合在一起，下面再说它的作用。
struct cookie {
#ifdef _DEBUG
      cookie *prev;
      cookie *next;
      const char *file;
      unsigned line;
      unsigned id;
#endif
      size_t size;
};
 
这是引擎里的大内存chunk，跟小内存chunk有所不同。因为大内存chunk的申请和归还都是针对系统的，因此只有在需要检查内存泄露的情况下才将其放入链表，以双链表的形式可以提高链表操作的效率。
有了chunk的信息，看下我们申请的内存大小是如何转化成chunk的。在此内存池中，当我们创建一个对象，比如T *p = new T，那么需要申请的内存是sizeof(T)。而实际上chunk的大小 = sizeof(T) + sizeof(memory_cookie) - sizeof(memory_cookie *)。这里之所以还要减去sizeof(memory_cookie *)，是因为上面提过的里面的next*指针和data共享数据。当chunk在空闲列表中未被使用时，需要用next链接下一个chunk，data数据为空。而当chunk被取出使用时，next指针不需要被使用。当chunk归还内存池时，根据size大小找到相应的空闲链表插入，此次data数据已无用，next重新使用。
    接下来根据得到的chunk大小，进行8字节对齐计算（如何计算，可以看字节对齐计算），这样求的的才能在空闲列表中找到对应大小的块链表。接着判断对齐后的chunk的大小，有两种情况：
1.如果小于最大的小内存块，即256字节，则从对应的空闲列表去除头节点chunk，并返回chunk->data进行使用。
2.如果大于256字节，则以大内存块处理。此时重新根据sizeof(T) + sizeof(cookie)，并且以8字节对齐后，求的的就是大内存块的chunk。向系统申请内存，同时返回chunk->data使用。
以下用伪代码说明从内存池申请和删除chunk的过程:
代码
WMalloc(int size)   //申请的大小
{
   size = size + sizeof(memory_cookie) - sizeof(memory_cookie *) //计算小内存chunk
   size = Align(size)    //８字节对齐
   if (size >


求两个有序数组的中位数
2011-09-29 12:06 393人阅读 评论(1) 收藏 举报
设数组A的长度为m, 数组B的长度为n， 两个数组都都是递增有序的。
求这两个数组的中位数

首先我们看看中位数的特点，一个大小为n的数组，
如果n是奇数，则中位数只有一个，数组中恰好有  (n-1)/2 个元素比中位数小。
如果n是偶数，则中位数有两个（下中位数和上中位数），这里我们只求下中位数，对于下中位数，
数组中恰好有(n-1)/2个元素比下中位数小。

此题中，中位数只有一个，它前面有 c = (m+n-1)/2 个数比它小。中位数要么出现在数组A中，
要么出现在数组B中，我们先从数组A开始找。考察数组A中的一个元素A[p]， 在数组A中，
有 p 个数比A[p]小，如果数组B中恰好有 c-p 个数比 A[p] 小， 则俩数组合并后就恰好有 c 个数比A[p]小，
于是A[p]就是要找的中位数。 如下图所示：

如果A[p] 恰好位于 B[c-p-1] 和 B[c-p] 之间，则 A[p] 是中位数
如果A[p] 小于 B[c-p-1] ，说明A[p] 太小了，接下来从 A[p+1] ~A[m-1]开始找
如果A[p] 大于 B[c-p] ，说明A[p] 太大了，接下来从 A[0] ~A[p-1]开始找。
如果数组A没找到，就从数组B找。

注意到数组A和数组B都是有序的，所以可以用二分查找。代码如下：
[cpp] view plaincopyprint?
1. #include <stdio.h>  
2. #include <stdlib.h>  
3.  
4.  
5. /* 从数组A和B中找下中位数 */ 
6. int find_median(int *A, int *B, int m, int n, int s, int t) 
7. { 
8.     int  p, c; 
9.  
10.     c = (m+n-1)/2;  /* 有多少个数小于下中位数 */ 
11.     p = (s+t)/2; 
12.  
13.     /* 如果下中位数不在A中，就从数组B找 */ 
14.     if (s > t) { 
15.         return find_median(B, A, n, m, 0, n-1); 
16.     } 
17.  
18.     /* 数组A中有p个数小于A[p], 当且进当数组B中有c-p个数小于A[p], A[p]才是中位数 */ 
19.     if (A[p] >= B[c-p-1] && A[p] <= B[c-p]) { 
20.         return A[p]; 
21.     } 
22.  
23.     /* A[p]太小了，从数组A中找一个更大的数尝试 */ 
24.     if (A[p] < B[c-p-1]) { 
25.         return find_median(A, B, m, n, p+1, t); 
26.     } 
27.  
28.     /* A[p]太大了，从数组A中找一个更小的数尝试 */ 
29.     return find_median(A, B, m, n, s, p-1); 
30. } 
31.  
32. int main() 
33. { 
34.     int m, n; 
35.     int A[]={1,3,5,7,8,9,10,12,24,45,65}; 
36.     int B[]={2,4,6,10,11,12,13,14,17,19,20,34,44,45,66,99}; 
37.  
38.     m = sizeof(A)/sizeof(int); 
39.     n = sizeof(B)/sizeof(int); 
40.  
41.     printf("%dn", find_median(A, B, m, n, 0, m-1)); 
42.  
43.     return 0; 
44. }  

一些面试题，整理自网络，就不一一帖原址了
腾讯面试题：tcp三次握手的过程，accept发生在三次握手哪个阶段？
答accept发生在三次握手之后。
第一次握手：客户端发送syn包(syn=j)到服务器。
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个ASK包（ask=k）。
第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)。
三次握手完成后，客户端和服务器就建立了tcp连接。这时可以调用accept函数获得此连接。
 
const的含义及实现机制，比如：const int i,是怎么做到i只可读的？
const用来说明所定义的变量是只读的。
这些在编译期间完成，编译器可能使用常数直接替换掉对此变量的引用。
 
用UDP协议通讯时怎样得知目标机是否获得了数据包
可以在每个数据包中插入一个唯一的ID，比如timestamp或者递增的int。
发送方在发送数据时将此ID和发送时间记录在本地。
接收方在收到数据后将ID再发给发送方作为回应。
发送方如果收到回应，则知道接收方已经收到相应的数据包；如果在指定时间内没有收到回应，则数据包可能丢失，需要重复上面的过程重新发送一次，直到确定对方收到。
 
求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。
一天总共有 3600*24 = 86400秒。
定义一个长度为86400的整数数组int delta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。
然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。
这样处理一遍后数组中存储了每秒中的人数变化情况。
定义另外一个长度为86400的整数数组int online_num[86400]，每个整数对应这一秒的论坛在线人数。
假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0] = delta[0]。第n+1秒的人数online_num[n] = online_num[n-1] + delta[n]。
这样我们就获得了一天中任意时间的在线人数。
 
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。
不妨假设10G个整数是64bit的。
2G内存可以存放256M个64bit整数。
我们可以将64bit的整数空间平均分成256M个取值范围，用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后，我们便知道中数在那个范围内出现，以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少，我们就可以对这个范围内的整数进行排序，找到中数。如果这个范围内出现的整数比较多，我们还可以采用同样的方法将此范围再次分成多个更小的范围（256M=2^28，所以最多需要3次就可以将此范围缩小到1，也就找到了中数）。
 
两个整数集合A和B，求其交集。
1.      读取整数集合A中的整数，将读到的整数插入到map中，并将对应的值设为1。
2. 读取整数集合B中的整数，如果该整数在map中并且值为1，则将此数加入到交集当中，并将在map中的对应值改为2。
通过更改map中的值，避免了将同样的值输出两次。
2.      也可以将A和B分别排序，然后利用归并的思想搞定。
 
有1到10w这10w个数，去除2个并打乱次序，如何找出那两个数？
申请10w个bit的空间，每个bit代表一个数字是否出现过。
开始时将这10w个bit都初始化为0，表示所有数字都没有出现过。
然后依次读入已经打乱循序的数字，并将对应的bit设为1。
当处理完所有数字后，根据为0的bit得出没有出现的数字。
 
首先计算1到10w的和，平方和。
然后计算给定数字的和，平方和。
两次的到的数字相减，可以得到这两个数字的和，平方和。
所以我们有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。
 
有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时后就会死亡，至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒？
最容易想到的就是用1000只小白鼠，每只喝一瓶。但显然这不是最好答案。
 
既然每只小白鼠喝一瓶不是最好答案，那就应该每只小白鼠喝多瓶。那每只应该喝多少瓶呢？
 
首先让我们换种问法，如果有x只小白鼠，那么24小时内可以从多少瓶水中找出那瓶有毒的？
由于每只小白鼠都只有死或者活这两种结果，所以x只小白鼠最大可以表示2^x种结果。如果让每种结果都对应到某瓶水有毒，那么也就可以从2^x瓶水中找到有毒的那瓶水。那如何来实现这种对应关系呢？
第一只小白鼠喝第1到2^(x-1)瓶，第二只小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1) + 2^(x-2)瓶....以此类推。
 
回到此题，总过1000瓶水，所以需要最少10只小白鼠。
 
根据上排给出十个数，在其下排填出对应的十个数, 要求下排每个数都是上排对应位置的数在下排出现的次数。上排的数：0，1，2，3，4，5，6，7，8，9。
0，1，2，3，4，5，6，7，8，9
6，2，1，0，0，0，1，0，0，0
通过一个循环做，三次循环搞定.
任意0-N，都是N-3的位置是1，前面是N-4,2,1，其他是0
 
给40亿个不重复的unsigned int的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那40亿个数当中?
unsigned int 的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存，用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。当需要查询时，直接找到对应bit，看其值是0还是1即可。
 
IBM面试题：c++中引用和指针有什么不同？指针加上什么限制等于引用？
引用不是一个变量，它只表示该引用名是目标变量名的一个别名，它本身不是一种数据类型，因此引用本身不占存储单元，系统也不给引用分配存储单元。引用一经确定就不能修改。
指针是一个变量，需要在内存中分配空间，此空间中存储所指对象的地址。由于指针是一个普通变量，所以其值还可以通过重新赋值来改变。
把指针定义为const后，其值就不能改变了，功能和引用类似，但有本质的区别。
 
谷歌面试题：1024! 末尾有多少个0？
末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数，所以我们只需统计因子5的个数。
是5的倍数的数有： 1024 / 5 = 204个
是25的倍数的数有：1024 / 25 = 40个
是125的倍数的数有：1024 / 125 = 8个
是625的倍数的数有：1024 / 625 = 1个
所以1024! 中总共有204+40+8+1=253个因子5。
也就是说1024! 末尾有253个0。
 
谷歌面试题：给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数
只要我们可以从 n 个数中随机选出 1 到 n 个数，反复进行这种运算，直到剩下最后一个数即可。
我们可以调用 n 次给定函数，生成 n 个 1 到 5 之间的随机数，选取最大数所在位置即可满足以上要求。
例如
初始的 7 个数 [1,2,3,4,5,6,7].
7 个 1 到 5 的随机数 [5, 3,1,4,2,5,5]
那么我们保留下[1,6,7],
3 个1 到 5 的随机数[2,4,1]
那么我们保留下[6]
6 就是我们这次生成的随机数。
 
产生K个数(k>1) 假定产生的数分别为n1,n2,n3,n4...
那么定义产生的数为n1-1+（n2-2）*5+（n3-1）*5^2+（n4-1）*5^3........
于是产生的数位于区间（0，5^k-1)
然后把5^k分成k等分，产生的数位于哪个等分就是那个产生的随机数（0~6），然后+1即可
如果位于k等分的余数范围，则重新执行一次上述过程
不用担心余数问题，当k取3时落到余数范围的概率就已经降低为6/125
 
判断一个自然数是否是某个数的平方。当然不能使用开方运算。
假设待判断的数字是 N。
 
方法1：
遍历从1到N的数字，求取平方并和N进行比较。
如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。
复杂度为O(n^0.5)。
 
方法2：
使用二分查找法，对1到N之间的数字进行判断。
复杂度为O(log n)。
 
方法3：
由于
(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到这些项构成了等差数列（每项之间相差2）。
所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的关系。
如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。
复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。
 
给定一个未知长度的整数流，如何随机选取一个数？
方法1.
将整个整数流保存到一个数组中，然后再随机选取。
如果整数流很长，无法保存下来，则此方法不能使用。
 
方法2.
如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。
如果整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。
....
如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。
....
利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。
 
设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。
1.      使用数组存储。
插入数字时，在O(1)时间内将该数字插入到数组最后。
获取中数时，在O(n)时间内找到中数。（选数组的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分，直到找到中数。）
 
2. 使用排序数组存储。
插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。
获得中数时，在O(1)复杂度内找到中数。
 
3. 使用大根堆和小根堆存储。
使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。
插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。
获取中数时，在O(1)时间内找到中数。
 
谷歌面试题：在一个特殊数组中进行查找
给定一个固定长度的数组，将递增整数序列写入这个数组。当写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。请在这个特殊数组中找出给定的整数。
假设数组为a[0, 1, ..., N-1]。
我们可以采用类似二分查找的策略。
首先比较a[0]和a[N/2]，如果a[0] < a[N/2]，则说明a[0,1,...,N/2]为递增子序列，否则另一部分是递增子序列。
然后判断要找的整数是否在递增子序列范围内。如果在，则使用普通的二分查找方法继续查找；如果不在，则重复上面的查找过程，直到找到或者失败为止。
 
谷歌面试题：给定两个已排序序列，找出共同的元素
不妨假设序列是从小到大排序的。定义两个指针分别指向序列的开始。
如果指向的两个元素相等，则找到一个相同的元素；如果不等，则将指向较小元素的指针向前移动。
重复执行上面的步骤，直到有一个指针指向序列尾端。如果两个数组大小差不多，用你的方法就行了，如果数组大小差得很多，就遍历小的，然后在大的里二分查找~
 
编程实现两个正整数的除法，当然不能用除法操作符。
 
// return x/y.
int div(const int x, const int y) {
....
}
int div(const int x, const int y) {
int left_num = x;
int result = 0;
while (left_num >= y) {
    int multi = 1;
    while (y * multi <= (left_num >> 1)) {
       multi = multi << 1;
    }
    result += multi;
    left_num -= y * multi;
}
return result;
}
 
微软面试题：计算n bit的整数中有多少bit 为1
设此整数为x。
方法1：
让此整数除以2，如果余数为1，说明最后一位是1，统计值加1。
将除得的结果进行上面运算，直到结果为0。
 
方法2：
考虑除法复杂度有些高，可以使用移位操作代替除法。
将 x 和 1 进行按位与操作（x&1），如果结果为1，说明最后一位是1，统计值加1。
将x 向右一位（x >> 1），重复上面过程，直到移位后结果为0。
 
方法3：
如果需要统计很多数字，并且内存足够大，可以考虑将每个数对应的bit为1的数量记录下来，这样每次计算只是一次查找操作。
 
微软面试题：快速求取一个整数的7倍
乘法相对比较慢，所以快速的方法就是将这个乘法转换成加减法和移位操作。
可以将此整数先左移三位（×8）然后再减去原值：X << 3 - X。
 
微软面试题：判断一个数是不是2的n次幂
设要判断的数是无符号整数X。
首先判断X是否为0，如果为0则不是2的n次幂，返回。
X和X-1进行按位与操作，如果结果是0，则说明这个数是2的n次幂；如果结果非0，则说明这个数不是2 的n次幂。
 
证明：
如果是2的n次幂，则此数用二进制表示时只有一位是1，其它都是0。减1后，此位变成0，后面的位变成1，所以按位与后结果是0。
如果不是2的n次幂，则此数用二进制表示时有多位是1。减1后，只有最后一个1变成0，前面的 1还是1，所以按位与后结果不是0。
 
微软面试题：判断数组中是否包含重复数字
给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）
方法1.
对数组进行排序（快速，堆），然后比较相邻的元素是否相同。
时间复杂度为O(nlogn)，空间复杂度为O(1)。
 
方法2.
使用bitmap方法。
定义长度为N/8的char数组，每个bit表示对应数字是否出现过。遍历数组，使用 bitmap对数字是否出现进行统计。
时间复杂度为O(n)，空间复杂度为O(n)。
 
方法3.
遍历数组，假设第 i 个位置的数字为 j ，则通过交换将 j 换到下标为 j 的位置上。直到所有数字都出现在自己对应的下标处，或发生了冲突。
时间复杂度为O(n)，空间复杂度为O(1)。
 
微软面试题：删除链表中的重复项
一个没有排序的链表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，请去掉重复项，并保留原顺序，以上链表去掉重复项后为newlist={a,l,x,b,e,f,g,h,m}，请写出一个高效算法(时间比空间更重要)。
建立一个hash_map，key为链表中已经遍历的节点内容，开始时为空。
从头开始遍历链表中的节点：
- 如果节点内容已经在hash_map中存在，则删除此节点，继续向后遍历；
- 如果节点内容不在hash_map中，则保留此节点，将节点内容添加到hash_map中，继续向后遍历。
 
微软面试题：编一个程序求质数的和
编一个程序求质数的和，例如F(7) = 2+3+5+7+11+13+17=58。
 
方法1：
对于从2开始的递增整数n进行如下操作：
用 [2，n-1] 中的数依次去除n，如果余数为0，则说明n不是质数；如果所有余数都不是0，则说明n是质数，对其进行加和。
 
空间复杂度为O(1)，时间复杂度为O(n^2)，其中n为需要找到的最大质数值（例子对应的值为17）
方法2：
可以维护一个质数序列，这样当需要判断一个数是否是质数时，只需判断是否能被比自己小的质数整除即可。
 
对于从2开始的递增整数n进行如下操作：
用 [2，n-1] 中的质数（2，3，5，7，开始时此序列为空）依次去除n，如果余数为0，则说明n不是质数；如果所有余数都不是0，则说明n是质数，将此质数加入质数序列，并对其进行加和。
 
空间复杂度为O(m)，时间复杂度为O(mn)，其中m为质数的个数（例子对应的值为7），n为需要找到的最大质数值（例子对应的值为17）。
方法3：
也可以不用除法，而用加法。
申请一个足够大的空间，每个bit对应一个整数，开始将所有的bit都初始化为0。
对于已知的质数（开始时只有2），将此质数所有的倍数对应的bit都改为1，那么最小的值为0的bit对应的数就是一个质数。对新获得的质数的倍数也进行标注。
对这样获得的质数序列累加就可以获得质数和。
 
空间复杂度为O(n)，时间负责度为O(n)，其中n为需要找到的最大质数值（例子对应的值为17）
 
微软面试题：给出一种洗牌算法
给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
假设数组Card[0 - 53]中的54个数对应54张牌，从第一张牌（i = 0）开始直到倒数第二张牌（i = 52），每次生成一个[ i, 53]之间的数r，将Card[i]和Card[r]中的数互换。
 
微软面试题：找到两个单向链表的第一个公共节点
如果两个单向链表有公共节点，则两个链表会构成Y型结构，最后一个节点相同。
 
我们可以从头开始遍历两个链表，找到最后一个节点的指针，设为p_a，p_b。同时记录下两个链表的长度len_a，len_b（假设len_a >= len_b)。
如果p_a == p_b，则说明两个链表有公共节点，否则没有。
如果有公共节点，则第一个公共节点距起始节点的距离满足 len_a - start_a == len_b - start_b。
所以第一个可能的公共节点距起始节点的距离是 len_a - len_b, 0。我们从这两个节点开始比较，直到找到第一个公共节点。
 
微软面试题：如何在链表里如何发现循环链接?
解答：
从链表的开始处，由两个指针A和B同时开始遍历链表。指针A每向前移动一步，指针B都向前移动两步。如果在移动了N步以后，指针A和B指向了同一个节点，则此链表中存在循环链表。
分析：
当然还可以在遍历的过程中存储节点的地址，通过不断的比较地址来判断有没有循环链表。但这种算法会使用更多的内存。
如果考官比较变态，还可以直接考复制链表。如果复制前没有测试循环链表，那不好意思，只能扣分了
 
谷歌面试题：找到链表的倒数第m个节点
方法1：
首先遍历链表，统计链表的长度N。
然后再次遍历链表，找到第N-m个节点，即为倒数第m个节点。
 
方法2：
使用两个指针，并使它们指向的节点相距m-1个。
然后同时向前移动两个指针，当一个指针指最后一个节点时，第二个指针指向倒数第m个节点。
 
两个方法的复杂度都是O(n)。
但是当N较大而m较小时，方法2可能会更快一些。因为方法2能更好利用CPU的缓存。
 
谷歌面试题：给定一个排序数组，如何构造一个二叉排序树？
采用递归算法。
选取数组中间的一个元素作为根节点，左边的元素构造左子树，右边的节点构造有子树。
 
谷歌面试题：数组中是否有两个数的和为10
1.
比较任意两个数的和是否为10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
复杂度为O(n*n)。
 
2.
将数组排序后，对每个数m，使用二分查找在数组中寻找10-m。
复杂度为O(nlogn)。
 
3.
将数组存储到hash_set中去，对每个数m，在hash_set中寻找10-m。
复杂度为O(n)。
 
4.
如果数组很大，超过内存的容量，可以按照hash(max(m, 10-m))%g，将数据分到g个小的group中。然后对每个小的group进行单独处理。
复杂度为O(n)。
 
谷歌面试题：找到两个字符串的公共字符，并按照其中一个的排序
写一函数f(a,b)，它带有两个字符串参数并返回一串字符，该字符串只包含在两个串中都有的并按照在a中的顺序。写一个版本算法复杂度O(N^2)和一个O(N) 。
O(N^2)：
对于a中的每个字符，遍历b中的每个字符，如果相同，则拷贝到新字符串中。
 
O(N)：
首先使用b中的字符建立一个hash_map，对于a中的每个字符，检测hash_map中是否存在，如果存在则拷贝到新字符串中。
 
在给定整数序列中，找出最大和的子序列
给定一个整数序列，其中有些是负数，有些是正数，从该序列中找出最大和的子序列。比如：-5，20，-4，10，-18，子序列[20，-4，10]具有最大和26。
 int GetMaxSubArraySum(int* array, int array_len) {
`    int current_sum = 0;
`    int max_sum = 0;
`    for (int i = 0; i < array_len; ++i) {
`      current_sum += array[i];
`      if (current_sum > max_sum) {
`        max_sum = current_sum;
`      } else if (current_sum < 0) {
`        current_sum = 0;
`      }
`    }
`    return max_sum;
` }
 
谷歌面试题：将无向无环连通图转换成深度最小的树
已知一个无向无环连通图T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度。
 
最简单直接的方法就是把每个节点都试一遍：
假设某个节点为根节点，计算树的深度。当遍历完所有节点后，也就找到了使树的深度最小的根节点。
但这个方法的复杂度很高。如果有n个节点，则时间复杂度为O(n^2)。
 
树的深度取决于根节点到最深叶节点的距离，所以我们可以从叶节点入手。
叶节点会且只会和某一个节点连通（反之不成立，因为根节点也可能只和一个节点连通），所以我们很容易找到所有可能的叶节点。
题目可以等价于找到了两个叶节点，使得两个叶节点之间的距离最远。根节点就是这两个叶节点路径的中间点（或者中间两个点的任意一个）。
我们可以每次都将连接度为1的节点删掉，直到最后只剩下1个或2个节点，则这一个节点，或者两个节点中的任意一个，就是我们要找的根节点。
 
谷歌面试题：将字符串中的小写字母排在大写字母的前面
有一个由大小写组成的字符串，现在需要对它进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序）。
初始化两个int变量A和B，代表字符串中的两个位置。开始时A指向字符串的第一个字符，B指向字符串的最后一个字符。
逐渐增加A的值使其指向一个大写字母，逐渐减小B使其指向一个小写字母，交换A，B所指向的字符，然后继续增加A，减小B....。
当A>=B时，就完成了重新排序。
 
谷歌面试题：如何拷贝特殊链表
有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？
拷贝pNext指针非常容易，所以题目的难点是如何拷贝pRand指针。
假设原来链表为A1 -> A2 ->... -> An，新拷贝链表是B1 -> B2 ->...-> Bn。
为了能够快速的找到pRand指向的节点，并把对应的关系拷贝到B中。我们可以将两个链表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
从A1节点出发，很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx，将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。依次类推。
当所有节点的pRand都拷贝完成后，再将合并链表分成两个链表就可以了。
 
谷歌面试题：10分钟内看到一辆车的概率是多少？
如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设为常概率条件下)
假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)^3，也就是0.05。所以得到方程
(1-x)^3 = 0.05
解方程得到x大约是0.63。
 
百度面试题：从输入url到显示网页，后台发生了什么？
简单来说有以下步骤：
1. 查找域名对应的IP地址。这一步会依次查找浏览器缓存，系统缓存，路由器缓存，ISP DNS缓存，根域名服务器。
2. 向IP对应的服务器发送请求。
3. 服务器响应请求，发回网页内容。
4. 浏览器解析网页内容。
当然，由于网页可能有重定向，或者嵌入了图片，AJAX，其它子网页等等，这4个步骤可能反复进行多次才能将最终页面展示给用户。
百度面试题：设计DNS服务器中cache的数据结构
要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
DNS服务器实现域名到IP地址的转换。
 
每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。
总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）
可以考虑的数据结构包括hash_map，字典树，红黑树等等。
 
百度面试题：将多个集合合并成没有交集的集合
给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度
（3）请描述可能的改进。
集合使用hash_set来表示，这样合并时间复杂度比较低。
 
1. 给每个集合编号为0，1，2，3...
2. 创建一个hash_map，key为字符串，value为一个链表，链表节点为字符串所在集合的编号。
遍历所有的集合，将字符串和对应的集合编号插入到hash_map中去。
3. 创建一个长度等于集合个数的int数组，表示集合间的合并关系。例如，下标为5的元素值为3，表示将下标为5的集合合并到下标为3的集合中去。
开始时将所有值都初始化为-1，表示集合间没有互相合并。
在集合合并的过程中，我们将所有的字符串都合并到编号较小的集合中去。
遍历第二步中生成的hash_map，对于每个value中的链表，首先找到最小的集合编号（有些集合已经被合并过，需要顺着合并关系数组找到合并后的集合编号），然后将链表中所有编号的集合都合并到编号最小的集合中（通过更改合并关系数组）。
4.现在合并关系数组中值为-1的集合即为最终的集合，它的元素来源于所有直接或间接指向它的集合。
 
算法的复杂度为O(n)，其中n为所有集合中的元素个数。
题目中的例子：
0: {aaa bbb ccc}
1: {bbb ddd}
2: {eee fff}
3: {ggg}
4: {ddd hhh}
生成的hash_map，和处理完每个值后的合并关系数组分别为
aaa: 0。[-1, -1, -1, -1, -1]
bbb: 0, 1。[-1, 0, -1, -1, -1]
ccc: 0。[-1, 0, -1, -1, -1]
ddd: 1, 4。[-1, 0, -1, -1, 0]
eee: 2。[-1, 0, -1, -1, 0]
fff: 2。[-1, 0, -1, -1, 0]
ggg: 3。[-1, 0, -1, -1, 0]
hhh: 4。[-1, 0, -1, -1, 0]
所以合并完后有三个集合，第0，1，4个集合合并到了一起，
第2，3个集合没有进行合并。
 
百度面试题：用C语言将输入的字符串在原串上倒序
 void revert(char* str) {
`    char c;
`    for (int front = 0, int back = strlen(str) - 1;
`         front < back;
`         ++front, --back) {
`      c = str[back];
`      str[back] = str[front];
`      str[front] = c;
`    }
` }
 
 
百度面试题：找出给定字符串对应的序号
序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…] 类似与excel的排列，任意给出一个字符串s=[a-z]+(由a-z字符组成的任意长度字符串），请问s是序列Seq的第几个。
注意到每满26个就会向前进一位，类似一个26进制的问题。
比如ab，则位置为26*1 + 2；
比如za，则位置为26*26 + 1；
比如abc，则位置为26*26*1 + 26*2 + 3
 
百度面试题：找出第k大的数字所在的位置
写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
先找到第k大的数字，然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效的找到第k大的数。
 
我们可以通过快速排序，堆排序等高效的排序算法对数组进行排序，然后找到第k大的数字。这样总体复杂度为O(N logN)。
 
我们还可以通过二分的思想，找到第k大的数字，而不必对整个数组排序。
从数组中随机选一个数t，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，{x, xx, ..., t} < {y, yy, ...}。
在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第k大的数字在哪个子数组中。
然后我们继续对包含第k大数字的子数组进行同样的划分，直到找到第k大的数字为止。
平均来说，由于每次划分都会使子数组缩小到原来1/2，所以整个过程的复杂度为O(N)。
 
百度面试题：找到满足条件的数组
给定函数d(n) = n + n的各位之和，n为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如93可以看成由78生成。
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出1至10000里的所有符合数A定义的数。
申请一个长度为10000的bool数组，每个元素代表对应的值是否可以有其它数生成。开始时将数组中的值都初始化为false。
由于大于10000的数的生成数必定大于10000，所以我们只需遍历1到10000中的数，计算生成数，并将bool数组中对应的值设置为true，表示这个数可以有其它数生成。
最后bool数组中值为false的位置对应的整数就是不能由其它数生成的。
 
百度面试题：对正整数，算得到1需要操作的次数
实现一个函数，对一个正整数n，算得到1需要的最少操作次数。
操作规则为：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。
例子：
func(7) = 4，可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：实现函数(实现尽可能高效) int func(unsign int n)；n为输入，返回最小的运算次数。
给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。
 
int func(unsign int n) {
if (n == 1) {
return 0;
}
if (n%2 == 0) {
return 1 + func(n/2);
}
int x = func(n+1);
int y = func(n-1);
if (x > y) {
return y + 1;
} else {
return x + 1;
}
}
假设n表示成二进制有x bit，可以看出计算复杂度为O(2^x)，也就是O(n)。
 int func(unsign int n) {
`    if (n == 1) {
`      return 0;
`    }
`    if (n % 2 == 0) {
`      return 1 + func(n/2);
`    }
`    if (n == 3) {
`      return 2;
`    }
`    if ( n & 2) {
`      return 1 + func(n + 1);
`    } else {
`      return 1 + func(n - 1);
`    }
` }
百度面试题：找出N！后面的0的个数
容易理解，题目等价于求因子2和因子5出现的次数。
对于因子2来说，数字2，4，6，8，10....2n...中存在因子2，这样就获得了 N/2 （其中N/2只取结果的整数部分）个因子2。这些数字去除因子2后，变成1，2，3....N/2，又可以提取N/4个因子2....这样一直到只剩下1个数（1）。所以N！中总共可以获得N/2 + N/4 + N/8 +....个因子2。
同理，N！中可以获得N/5 + N/25 + ... 个因子5。
尾部连续0的个数就是因子2和因子5较少的那个。
 
对于题目中的例子，18！中包含9+4+2+1个因子2，包含3个因子5。所以尾部有3个连续0。
 
计算的复杂度为O(logN)。
 
百度面试题：找出被修改过的数字
n个空间（其中n<1M），存放a到a+n-1的数，位置随机且数字不重复，a为正且未知。现在第一个空间的数被误设置为-1。已经知道被修改的数不是最小的。请找出被修改的数字是多少。
例如：n=6，a=2，原始的串为5, 3, 7, 6, 2, 4。现在被别人修改为-1, 3, 7, 6, 2, 4。现在希望找到5。
 
由于修改的数不是最小的，所以遍历第二个空间到最后一个空间可以得到a的值。
a 到 a+n-1这 n个数的和是 total = na + (n - 1)n/2。
将第二个至最后一个空间的数累加获得 sub_total。
那么被修改的数就是 total - sub_total。
 
百度面试题：在100w个数中找最大的前100个数
应该使用某种数据结构保存迄今最大的100个数。每读到一个新数时，将新数和保存的100个数中的最小一个相比较，如果新数更大些，则替换。这样扫描一遍100w个数也就获得了最大的100个数。
对于保存的100个数的数据结构，应该在最小复杂度的条件下满足
1）可以获得最小的数；
2）将最小数替换为另一个数后可以重新调整，使其可以满足条件1。
可见小根堆可以满足这些条件。
所以应该采用小根堆+扫描的方法。
 
方法1：类似《算法导论》中用二分法求第K大数，理想TC是O(n)。
 
百度面试题：正向最大匹配分词，怎么做最快？
用所有词生成一个字典树，匹配的过程就是查字典的过程。
假设我们有两个词”百度“，”百家姓“，那么生成的字典树就是：
 
百---度*
|
|-----家----姓*
 
其中“度”和“姓”旁边的星号表示这是一个有效词。
对于句子“百度面试题“，首先在字典中找”百“，找到了；继续向下查找”度“，又找到了；继续向下查找”面“，没有找到。那么”百度“就是我们分出来的第一个词。
还可以用hash_map来做。
首先用所有的词生成一个hash_map，假设我们有两个词“百度，“百家姓”，那么生成hash_map如下：
{
百：0
百度：1
百家：0
百家姓：1
}
其中值为0表示对应的key不是一个词，但有更长的词包括这个key；值为1表示这是一个词。
对于句子“百度面试题”，首先在hash_map中查找“百”，找到对应值为0，继续；查找“百度”，找到对应值为1，说明这是一个词，记下来并继续；查找“百度面”，没有找到，说明没有更长的词包含“百度面”。所以“百度”就是我们分出来的第一个词。
 
和字典法相比，hash_map法可能会用到更多的存储空间（因为有些字，比如“百”字，都存储了多次。但这还取决于字典树的具体实现），但程序设计会更加简单，不容易出错。
 
session和cache的区别是什么？
session是针对单个连接（会话）来使用的，主要存储和连接相关的上下文信息，比如登录信息等等。
cache是应用程序级的，主要用来缓存计算结果，减轻服务器负担，并加快响应速度。
 
百度面试题：找出数组中出现次数超过一半的数
答案：
创建一个hash_map，key为数组中的数，value为此数出现的次数。遍历一遍数组，用hash_map统计每个数出现的次数，并用两个值存储目前出现次数最多的数和对应出现的次数。
这样可以做到O(n)的时间复杂度和O(n)的空间复杂度，满足题目的要求。
但是没有利用“一个数出现的次数超过了一半”这个特点。也许算法还有提高的空间。
答案2：
使用两个变量A和B，其中A存储某个数组中的数，B用来计数。开始时将B初始化为0。
遍历数组，如果B=0，则令A等于当前数，令B等于1；如果当前数与A相同，则B=B+1；如果当前数与A不同，则令B=B-1。遍历结束时，A中的数就是要找的数。
这个算法的时间复杂度是O(n)，空间复杂度为O(1)。
 
百度面试题：如何找出字典中的兄弟单词
给定一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有多少个兄弟单词？
答案：
使用hash_map和链表。
首先定义一个key，使得兄弟单词有相同的key，不是兄弟的单词有不同的key。例如，将单词按字母从小到大重新排序后作为其key，比如bad的key为abd，good的key为dgoo。
使用链表将所有兄弟单词串在一起，hash_map的key为单词的key，value为链表的起始地址。
开始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时，只需求取这个单词的key，然后到hash_map中找到对应的链表即可。
这样创建hash_map时时间复杂度为O(n)，查找兄弟单词时时间复杂度是O(1)。
 
网易面试题：new/delete和malloc/free的区别
new/delete：给定数据类型，new/delete会自动计算内存大小，并进行分配或释放。如果是对类进行操作，new/delete还会自动调用相应的构造函数和析构函数。
malloc/free：没有进行任何数据类型检查，只负责分配和释放给定大小的内存空间。
有些情况下，new/delete和malloc/free都不能满足性能的要求，我们需要自建内存分配来提高效率。比如，如果程序需要动态分配大量很小的对象，我们可以一次分配可以容纳很多小对象的内存，将这些小对象维护在链表中，当程序需要时直接从链表中返回一个。还有一点，new返回指定类型的指针；而malloc返回void*，必须强制类型转化。
有个比较有意思的地方是:int *p=(void*)malloc(1);可以编译并运行。
 
网易面试题：没有拷贝构造函数和重载＝运算符的string类
c++中，一个没有拷贝构造函数和重载＝运算符的string类，会出现什么问题，如何解决？
如果没有定义拷贝构造函数和重载=运算符，则系统会自动生成逐位拷贝的函数。
当我们用string初始化string时，（比如 string a("abc"); string b = a;），两个对象会指向同样的内存地址。在两个对象的析构函数中，我们会对同一个内存块调用两次删除，导致不确定的结果。
当我们将一个string赋值给另外一个string时，（比如 string a("abc"); string b(“cde"); b = a;）除了上面的多次调用析构函数的问题外，由于原来对象b指向的数据没有被正确删除，会导致内存泄漏。
 
解决办法：
1. 添加这两个函数。
2. 不使用这两个函数。
- 不用string初始化string：可以使用string a（”abc"); string b(a.c_str()); 代替。
- 不用string给string赋值，包括不能通过传值方法传递string参数：尽量使用指针。
 
网易面试题：写一段程序，实现atoi(const char* s)方法
atoi用于将字符串转换成为整数。
比如 “123” =》 123， “-246” =》 -246。
 
`   int atoi(const char*s) {
`     int result = 0;
`     bool is_plus = true;
`     if (*s == '+') {
`       ++s;
`     } else if (*s == '-') {
`       ++s;
`       is_plus = false;
`     }
`     while (*s >= '0' && *s <= '9') {
`       result = result * 10 + *s - '0';
`       ++s;
`     }
`     if (is_plus) {
`       return result;
`     } else {
`       return -result;
`     }
`   }
 
网易面试题：给出若干个单词，组成字典，要求查找速度最快。
为使查找速度最快，可以要使用hash_map。
如果每个单词还有对应的解释和例句，可以将解释和例句对应的指针存放在hash_map的值中。或许可以尝试使用 TRIE 结构。
 
迅雷面试题：门面模式的解释、适用场合？
门面模式又被称为外观模式，为子系统中的一组接口提供一个一致的界面，该模式定义了一个高层接口，使得这个子系统更加容易使用。
举个例子：在做项目或产品的过程中进行跨部门合作的时候，每个部门都有个相应的接口人，那么我们只需和对应部门的接口人交互即可。
 
适用场合：
为一个复杂子系统提供一个简单接口：子系统往往因为不断演化而变得越来越复杂，使用门面模式可以使得子系统更具有可复用性。
子系统的独立性：引入门面模式将一个子系统与它的客户端以及其他子系统分离，可以提高子系统的独立性和可移植性。
层次化结构：在构建一个层次化的系统时，可以使用 门面模式定义系统中每一层的入口。如果层与层之间是相互依赖的，则可以限定它们仅通过门面进行通信，简化层与层之间的依赖关系。
 
迅雷面试题：AJAX的原理、如何实现刷新及其优点
AJAX即“Asynchronous JavaScript and XML”（异步JavaScript和XML)，是指一种创建交互式网页应用的网页开发技术。
 
使用了AJAX技术的网页，利用Javascript和服务器通信，获取数据，然后再通过修改网页的DOM中的某些元素来实现刷新网页的特定部分。
 
使用了AJAX技术后，由于只需要更新网页的一部分，而不是全部，所以和服务器交互的数据比较少。这就降低了服务器的负载，并提高了用户端的响应速度。另外，AJAX并不需要在浏览器中安装插件。
 
迅雷面试题：数组与链表的区别？
在数组中，元素在内存中连续存放。对于访问操作，由于元素类型相同，占用内存相同，所以可以通过数组的下标计算出元素所在的内存地址，便于快速访问。但对于插入或删除操作，需要移动大量元素，所以速度比较慢。
在链表中，元素在内存中没有连续存放，而是通过元素中的指针将各个元素连接在一起。对于访问操作，需要从链表头部开始顺序遍历链表，直到找到需要的元素，所以速度比较慢。对于插入或删除操作，只需修改元素中的指针即可完成，速度比较快。
所以，如果需要频繁访问数据，很少插入删除操作，则使用数组；反之，如果频繁插入删除，则应使用链表。
 
迅雷面试题：最快的排序法的性能，并列举至少三个
最快的排序算法是O(N*lgN)。，快排序，堆排序，归并排序
 
迅雷面试题：合并用户基本信息和看电影的记录
如何有效合并两个文件：一个是1亿条的用户基本信息，另一个是用户每天看电影连续剧等的记录，5000万条。其中内存只有1G。
显然内存不能同时存下所有的数据，所以考虑分而治之的思想。
假设1K Byte可以保存一个用户的基本信息和看电影记录。我们可以将基本信息和看电影记录都按照hash(user_name)%100的余数各分成100个小文件。利用1G内存，我们可以每次只处理一对小文件，然后将结果输出到一个文件中即可。
在处理一对小文件时，可以利用key为用户名的hash_map将基本信息和看电影记录合并在一起。
 
迅雷面试题：c语言中不同include方法的差别
#include "filename.h" 首先在程序原文件所在目录下查找，如果找不到，再到系统目录中查找。
#include <filename.h> 直接去系统目录中查找。
 
在1亿条用户记录里，如何快速查询统计出看了5个电影以上的用户？
构建一个hash map，key为用户名，value为已经看过的电影数量。
遍历所有用户记录，然后根据用户名和已经看过电影数量的情况进行处理：
- 如果用户名不在hash map中，则添加对应用户名，并将值设为1。
- 如果用户名对应的值小于5，则将值加1。如果加1后值为5，则输出此用户名。
- 如果用户名对应的值等于5，则不进行任何操作。
 
oracle面试题：数据库冷备份和热备份的不同点以及各自的优点
热备份针对归档模式的数据库，在数据库仍旧处于工作状态时进行备份。而冷备份指在数据库关闭后，进行备份，适用于所有模式的数据库。热备份的优点在于当备 份时，数据库仍旧可以被使用并且可以将数据库恢复到任意一个时间点。冷备份的优点在于它的备份和恢复操作相当简单，并且由于冷备份的数据库可以工作在非归 档模式下，数据库性能会比归档模式稍好。（因为不必将archive log写入硬盘）
 
华为面试题：IP，TCP和UDP协议的定义和主要作用
IP协议是网络层的协议。IP协议规定每个互联网网上的电脑都有一个唯一的IP地址，这样数据包就可以通过路由器的转发到达指定的电脑。但IP协议并不保证数据传输的可靠性。
TCP协议是传输层的协议。它向下屏蔽了IP协议不能可靠传输的缺点，向上提供面向连接的可靠的数据传输。
UDP协议也是传输层的协议。它提供无连接的不可靠传输。
 
华为面试题：全局变量和局部变量有什么区别
全局变量是整个程序都可访问的变量，生存期从程序开始到程序结束；局部变量存在于模块中(比如某个函数)，只有在模块中才可以访问，生存期从模块开始到模块结束。
全局变量分配在全局数据段，在程序开始运行的时候被加载。局部变量则分配在程序的堆栈中。因此，操作系统和编译器可以通过内存分配的位置来知道来区分全局变量和局部变量。全局变量和局部变量的区别是在存储器中位置不同，具体说，全局变量存储在数据段中，局部变量一般来说在堆栈段
 
华为面试题：析构函数和虚函数的用法和作用？
析构函数是在类对象消亡时由系统自动调用。主要用来做对象的清理工作，比如来释放对象申请的动态空间。
基类中用virtual修饰的函数称为虚函数。在派生类中可以对虚函数进行重新定义，这样同样的函数接口可以在不同的派生类中对应不同的实现。当通过基类的指针来调用虚函数时，程序会根据指针实际指向的对象来决定调用哪个实现。
 
华为面试题：如何引用一个已经定义过的全局变量？
可以用引用头文件的方式，也可以使用extern关键字。
用引用头文件方式，如果将那个变量写错了，那么在编译期间会报错。
用extern方式，如果将变量名写错了，那么在编译期间不会报错，而在连接期间报错。
 
华为面试题：c语言中局部变量能否和全局变量重名？
局部变量可以与全局变量同名。在函数内引用这个变量时，会用到同名的局部变量，而不会用到全局变量。要用全局变量，需要使用"::"。
对于有些编译器而言，在同一个函数内可以定义多个同名的局部变量，比如在两个循环体内都定义一个同名的局部变量，而那个局部变量的作用域就在那个循环体内。
 
完美时空面试题：memcpy 和 memmove 有什么区别？
memcpy和memmove都是将源地址的若干个字符拷贝到目标地址。
如果源地址和目标地址有重叠，则memcpy不能保证拷贝正确，但memmove可以保证拷贝正确。
 
例如：
char src[20];
// set src
char* dst = src + 5;
此时如果要从src拷贝10个字符到dst，则么memcpy不能保证拷贝正确，但是memmove可以保证。
 
雅虎面试题：HTTP中Get和Post的区别
Get和Post都是浏览器向网页服务器提交数据的方法。
Get把要提交的数据编码在url中，比如 http://hi.baidu.com/mianshiti?key1=value1&key2=value2 中就编码了键值对 key1，value1 和key2，value2。受限于url的长度限制，Get方法能传输的数据有限（不同浏览器对url长度限制不同，比如微软IE设为2048）。
Post把要提交的数据放在请求的body中，而不会显示在url中，因此，也没有数据大小的限制。
 
由于Get把数据编码在URL中，所以这些变量显示在浏览器的地址栏，也会被记录在服务器端的日志中。所以Post方法更加安全。
 

最后

以上就是温暖小伙为你收集整理的网络上搜集的面试题 Linux下2种定时执行任务方法malloc,free和new,delete有区别吗？如果有，是什么？c++面试题：#define MIN(A,B) ( (A) <= (B) ? (A) : (B) )的全部内容，希望文章能够帮你解决网络上搜集的面试题 Linux下2种定时执行任务方法malloc,free和new,delete有区别吗？如果有，是什么？c++面试题：#define MIN(A,B) ( (A) <= (B) ? (A) : (B) )所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。