温斯顿吴 ☀️摩诃般若波罗蜜

编程问题总结-Good Interview Questions

2017-04-05
编程

一个数组A[N]，包含取值为[1,N]的元素，请判断是否有重复元素

解法： 1.Sum(1…N)!=sum(A[0],A[N-1])则重复 2.hash记数法 3.排序后再判重

为手机的T9输入法设计一个索引

提供一个包含所有英文单词的字典，为手机的T9输入法设计一个索引，例如输入4能够提示出g、h、i开头的英文单词（greate、hello、…），输入43能够提示出ge、he、id、if (hello…) 等词开通的英文单词。 思路： 使用trie树存储索引，但是如果使用普通的以字母形式组织的trie树检索非常麻烦。因此需要先将所有的英文单词改写成数字，例如： Greate:473283 Hello:43556 然后组织成数字的trie树，所有的单词都挂在这棵trie树上。

内存受限情况下的海量字符串查找问题

方案1：可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。 遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set（STL）中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。 Bloom filter：Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。Bloom filter 采用的是哈希函数的方法，将一个元素映射到一个 m 长度的阵列上的一个点，当这个点是 1 时，那么这个元素在集合内，反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突，解决方法就是使用 k 个哈希 函数对应 k 个点，如果所有点都是 1 的话，那么元素在集合内，如果有 0 的话，元素则不再集合内。随着元素的插入，Bloom filter 中修改的值变多，出现误判的几率也随之变大，当新来一个元素时，满足其在集合内的条件，即所有对应位都是 1 ，这样就可能有两种情况，一是这个元素就在集合内，没有发生误判；还有一种情况就是发生误判，出现了哈希碰撞，这个元素本不在集合内。

内存有限情况下进行排序

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。 方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。 如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。 对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

写出斐波那契数列的递归与迭代代码

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……
用数学公式表示出来就是： F(1) = 1，F(2)=1 (n=1,2) F(n)=F(n-1)+ F(n-2) (n>2) 递归法： Fib(1) = 1 [基本情况]
Fib(2) = 1 [基本情况] 对所有n > 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 关键代码：

if(n == 1|| n== 2){
  return 1;
}
else{
  return fib(n - 1) + fib(n - 2);
}

迭代法:

int f(int n){
  int i, f1 = 1, f2 = 1, f3;
  if(n<=0){
    printf("输入错误.\n");
  }
  else if( n==1 || n==2 ){
    printf("1");
  }
  else{
    for( i=0; i < n-2; i++ ){
      f3 = f1+f2;           // f1 表示当前的值
      f2=f1;
      f1=f3;
    }   
    printf("%d\n",f1);
  }
}

分药问题

有5瓶药，药片形状大小一样，每瓶数量一样。其中一瓶是坏的，每片9mg，好的药片每片10mg。需要一次区分哪瓶是坏药，怎么做？ 1.你有一个高灵敏度的天平，有任意规格砝码 给5个瓶依次编号，分别取出1、2、3、4、5片药，根据砝码不同的质量区分坏药瓶的序号

2.你有一个高灵敏度的天平，但没有砝码 给5个瓶依次编号，第5瓶放开不取，从1~4瓶中分别取出100、1、100、1片药，放置1、2和3、4分别于天平左右侧: （1）看是否平衡，若平衡，5是坏的；如不平衡； （2）左侧低右侧高，看灵敏天平的偏转角度，大3，小4； （3）左侧高右侧低，看灵敏天平的偏转角度，大1，小2。

合并有序链表

递归算法所体现的“重复”一般有三个要求： 一是每次调用在规模上都有所缩小(通常是减半)； 二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)； 三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

如何设计递归算法 1.确定递归公式 2.确定边界(终了)条件递归实现：

算法思想： 递归终止条件：若head1为空，返回head2指针（head）；若head2为空，返回head1指针（head） 递归过程： 1.若head1->data > head2->data; head 指针应该指向head2所指向的节点，而且head->next应该指向head1和head2->next两个链表的合成序列的头指针； 2.否则head 指针应该指向head1所指向的节点，而且head->next应该指向head->next和head2两个链表的合成序列的头指针；

实现代码：

#include <iostream>
using namespace std;
    
// 节点的类定义
class Node{
  public:
  int data;
  Node * next;
  Node(int data){
    this->data=data;
  }
};

// 链表的类定义
class LinkedList{
  public:
    Node * head;
    
    // 用一个整形数组作为参数的构造函数
    LinkedList(int array[]){
      head=new Node(array[0]);
      Node * temp = head;
      int i;
      for(i=1;i<3;i++){
        temp->next=new Node(array[i]);
        temp=temp->next;
      }
      temp->next=NULL;
    }
};

// 递归的合并两个有序链表
Node * mergeLinkedList(Node * head1, Node * head2){   
  Node *p=NULL;   
  if(head1==NULL && head2==NULL){   
    return p;   
  }
  else if( head1==NULL ){   
    return head2;
  }   
  else if( head2==NULL ){   
    return head1;
  }   
  else{   
    if( head1->data < head2->data ){   
      p = head1;   
      p->next = mergeLinkedList( head1->next,head2 );   // !
    }   
    else{
      p = head2;   
      p->next = mergeLinkedList( head1,head2->next );   
    }   
    return p;   
  }   
} 

// 打印链表的所有元素
void printList(Node * head){
  Node * temp=head;
  while(temp!=NULL){
    cout<<temp->data<<"  ";
    temp=temp->next;
  }
}

int main(){
  int array1[3]={2,5,8};
  int array2[3]={1,6,7};

  // 构造两个有序链表--list1和list2
  LinkedList list1(array1);
  LinkedList list2(array2);

  // 递归的将这两个有序链表合并成一个有序链表
  Node * new_head = mergeLinkedList(list1.head, list2.head);
    
  // 打印有序链表
  printList(new_head);
  return 0;
}

向单链表中满足条件的位置插入一个元素

通常是向有序单链表中插入一个新元素结点，使得插入后仍然有序。其插入过程为： (1)为新元素动态分配结点并赋值； (2)若单链表为空或者新元素小于表头结点的值，则应把新元素结点插入到表头并返 (3)从表头开始顺序查找新元素的插入位置，在查找过程中必须保留当前结点的前驱g指针，以便插入新结点时使用； (4)在插入位置上完成插入操作，即把新结点插入到当前结点和其前驱结点之间。

在一个有序数组中，有些元素重复出现。输入一个数值，求此值在数组中重复的次数

思路有两种: 1.upperbound() – lowerbound() 2.使用类似线段树的思想直接统计 iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。 iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。 例如：map中已经插入了1，2，3，4的话，如果lower_bound(2)的话，返回的2，而upper_bound（2）的话，返回的就是3

在2.5亿个整数中找出不重复的整数

在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。 方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

方案2：也可采用划分小文件的方法，然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

BitMap算法：来自于《编程珠玑》。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。 假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0 然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01«(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为1。 然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1。 然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。

多信号量生产者-消费者问题

桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。 分析 在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。 解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：

	int S＝1;
	int Sa＝0;
	int So＝0;
      main()
      {
        cobegin
            father();      /*父亲进程*/
            son();        /*儿子进程*/
            daughter();    /*女儿进程*/
        coend
    ｝
    father()
    {
        while(1)
          {
            P(S);
            将水果放入盘中;
            if（放入的是桔子）V(So);
            else  V(Sa);
           }
     }
    son()
    {
        while(1)
          {
             P(So);
             从盘中取出桔子;
             V(S);
             吃桔子;
            ｝
    }
    daughter()
    {
         while(1)
            {
              P(Sa);
              从盘中取出苹果;
              V(S);
              吃苹果;
            ｝
｝

大数相加问题

实现A+B=C,其中A、B位数超过100位 算法思想：大数使用字符串存储，每一个单元存储操作数的每一位，之后执行位相加。 基本思路：字符串反转、字符变数字、位运算、反序输出 C语言代码：

#include <stdio.h>   
#include<string.h>   
#define Max 101   

void print(char sum[], int result_len);  
int bigNumAdd(char a[],char b[],char sum[]);  
  
int main()  {  
  char a[Max]={0};  
  char b[Max]={0};  
  char sum[Max]={0};  
  puts("input a:");  
  gets(a);             /*  char* gets(char*buffer); 头文件stdio.h .gets(s)函数与scanf("%s",s)相似，但不完全相同，使用scanf("%s",s) 函数输入字符串时存在一个问题，就是如果输入了空格会认为字符串结束，空格后的字符将作为下一个输入项处理，但gets()函数将接收输入的整个字符串直到遇到换行为止 */
  puts("input b:");  
  gets(b);  
  print(sum, bigNumAdd(a,b,sum));  
  return 0;  
}  
  
int bigNumAdd(char a[], char b[], char sum[]){  
  int i=0;  
  int c=0;  // 表示进位   
  
  char m[Max]={0};  
  char n[Max]={0};  
  memset(sum,0,Max*sizeof(char));  // 重要
  
  // 字符串反转且字符串变数字   
  int lenA=strlen(a);  
  int lenB=strlen(b);  
      
  int result_len = (lenA > lenB)?lenA:lenB;  
  for (i=0;i<lenA;i++){  
      m[i]=a[lenA-i-1]-'0';  
  }  

  for (i=0;i<lenB;i++){  
      n[i]=b[lenB-i-1]-'0';  
  }  
  
  // 按位运算   
  for (i=0; i<lenA||i<lenB; i++){  
      sum[i]=(m[i]+n[i]+c)%10+'0';  // 得到末位   
      c=(m[i]+n[i]+c)/10;  // 得到进位   
  }  
  
  if (c){  
      result_len++;// 最后一次有进位，长度+1   
  }  
  return result_len;  
}  
  
void print(char sum[], int result_len){  
  int j=0;  
  int i=0;  
  
  for(j=result_len-1; j>=0; j--){  
    i++;  
    printf("%c",sum[j]);  
  }  
  puts("\n");  
}

如何使用P、V操作来结局各种生产者-消费者问题？

PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

    P（S）：①将信号量S的值减1，即S=S-1；
           ②如果S0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
    V（S）：①将信号量S的值加1，即S=S+1；
           ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。 信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。

一般来说，信号量S>0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。 利用信号量和PV操作实现进程互斥：

	进程P1              进程P2           ……          进程Pn
	……                  ……                           ……
	P（S）；              P（S）；                         P（S）；
	临界区；             临界区；                        临界区；
	V（S）；              V（S）；                        V（S）；
	……                  ……            ……           ……

其中信号量S用于互斥，初值为1。 使用PV操作实现进程互斥时应该注意的是： （1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。 （3）互斥信号量的初值一般为1。

利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。 使用PV操作实现进程同步时应该注意的是： （1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。 （2）信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。 （3）同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。

如何判断一个链表是否存在回路?

  • 方法1：给指针加一个标志域，如访问过则置1.当遍历到标志为1的项说明有了回路。
  • 方法2：定义2个指针，一快(fast)一慢(slow)，即：从头向后遍历过程中，每循环一次，快指针一次向后移动2个元素，慢指针移动一个元素，每次判断( fast==slow   slow==fast->nest ),如果成立，说明慢指针赶上了快指针，则为循环链表，否则，如果有一个指针到达NULL，则为单链表。

如何对递归程序进行时间复杂度分析？

例子：求N!。 这是一个简单的”累乘”问题，用递归算法也能解决。

  n! = n * (n - 1)!   n > 1 
  0! = 1, 1! = 1      n = 0,1

因此，递归算法如下：

  fact(int n) {  
    if(n == 0 || n == 1)          
      return 1;  
    else   
      return n * fact(n - 1);  
  }

以n=3为例，看运行过程如下：

    fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3) 
    ------------------------------>  ------------------------------> 
                递归                            回溯

递归算法在运行中不断调用自身降低规模的过程，当规模降为1，即递归到fact(1)时，满足停止条件停止递归，开始回溯(返回调用算法)并计算，从fact(1)=1计算返回到fact(2);计算2fact(1)=2返回到fact(3)；计算3fact(2)=6，结束递归。 递归算法的分析方法比较多，最常用的便是迭代法。 迭代法的基本步骤是先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，最后求级数的和，再估计和的渐进阶。

    <1> 例：n! 
       算法的递归方程为： T(n) = T(n - 1) + O(1); 
       迭代展开： T(n) = T(n - 1) + O(1) 
                       = T(n - 2) + O(1) + O(1) 
                       = T(n - 3) + O(1) + O(1) + O(1) 
                       = ...... 
                       = O(1) + ... + O(1) + O(1) + O(1) 
                       = n * O(1) 
                       = O(n) 
      这个例子的时间复杂性是线性的。 

  <2> 例：如下递归方程： 
      T(n) = 2T(n/2) + 2, 且假设n=2的k次方。 
      T(n) = 2T(n/2) + 2 
           = 2(2T(n/2*2) + 2) + 2 
           = 4T(n/2*2) + 4 + 2 
           = 4(2T(n/2*2*2) + 2) + 4 + 2 
           = 2*2*2T(n/2*2*2) + 8 + 4 + 2 
           = ... 
           = 2的(k-1)次方 * T(n/2的(i-1)次方) + $(i:1~(k-1))2的i次方 
           = 2的(k-1)次方 + (2的k次方)  - 2 
           = (3/2) * (2的k次方) - 2 
           = (3/2) * n - 2 
           = O(n) 
      这个例子的时间复杂性也是线性的。 

  <3> 例：如下递归方程： 
      T(n) = 2T(n/2) + O(n), 且假设n=2的k次方。 
      T(n) = 2T(n/2) + O(n) 
           = 2T(n/4) + 2O(n/2) + O(n) 
           = ... 
           = O(n) + O(n) + ... + O(n) + O(n) + O(n) 
           = k * O(n) 
           = O(k*n) 
           = O(nlog2n) //以2为底 
     
      一般地，当递归方程为`T(n) = aT(n/c) + O(n)`, T(n)的解为： 
      O(n)          (a<c && c>1) 
      O(nlog2n)     (a=c && c>1) //以2为底 
      O(nlogca)     (a>c && c>1) //n的(logca)次方，以c为底 
   上面介绍的3种递归调用形式，比较常用的是第一种情况，第二种形式也有时出现，而第三种形式(间接递归调用)使用的较少，且算法分析比较复杂。下面举个第二种形式的递归调用例子。 

    <4> 递归方程为：T(n) = T(n/3) + T(2n/3) + n 
     为了更好的理解，先画出递归过程相应的递归树： 
                            n                        --------> n 
                    n/3            2n/3              --------> n 
              n/9       2n/9   2n/9     4n/9         --------> n 
           ......     ......  ......  .......        ...... 
                                                     -------- 
                                                     总共O(nlogn) 
     累计递归树各层的非递归项的值，每一层和都等于n，从根到叶的最长路径是： 
      n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1 
     设最长路径为k，则应该有：(2/3)的k次方 * n = 1 
     得到 k = log(2/3)n  // 以(2/3)为底 
     于是 T(n) <= (K + 1) * n = n (log(2/3)n + 1) 
     即 T(n) = O(nlogn) 
   由此例子表明，对于第二种递归形式调用，借助于递归树，用迭代法进行算法分析是简单易行的。

如果收到一个字符串型的浮点数，比如“1234.56”，如何变成浮点数

double atof(char s[]){
  double val,power;
  int i,sign;

  for( i=0; isspace(s[i]); i++) //跳过空白
    ;
  
  sign=(s[i]=='-') ? -1 : 1;    //判断符号
  
  if( s[i]=='+' || s[i]=='-' ){
    i++;
  }
  
  for( val=0.0; isdigit(s[i]); i++){
    val = 10.0*val + (s[i]-'0');  // 此步骤也可用于求解“将一个字符串的整数变成整数”
  }  
  
  if(s[i]=="."){
    i++;
  }

  for(power=1.0;isdigit(s[i]);i++){
    val=10.0*val+(s[i]-'0');
    power*=10.0;
  }
  return sign*val/power;
}

完成一个trim函数，将一个字符串两端的空格、回车、tab符号去掉

void trim( char *str){
  int i, j;
  assert( str != NULL); // <assert.h>
  
  /*find the first non-space char's position */
  for (i = 0; (str[i] == ' ' || str[i] == '\t') && str[i] != '\0'; i++)
    ;
      
  /*find the last non-space char's position */
  for (j = strlen(str) - 1; (str[j] == ' ' || str[j] == '\t') && j; j--)
    ;
  
  memmove(str, str + i, j - i); // < String.h >
  str[j + 1] = '\0';
}

memmove用于从src拷贝count个字节到dest，如果目标区域和源区域有重叠的话，memmove能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中。但复制后src内容会被更改。当目标区域与源区域没有重叠则和memcpy函数功能相同。

定一棵二叉树的前序和中序遍历序列，重建这个二叉树

如先序为 124356， 中序为 421536 1．首先要面试者正确写出一个二叉树的先序和中序序列 2．然后询问根据先序和中序结果，是否可以重建出这棵二叉树？看面试者是否能够意识到二叉树节点内容相同的情况。 3．简化问题，假设二叉树节点只使用标号表示，没有重复，写程序根据先序和中序序列重构出二叉树。 4．分析： 先序中的第一个节点1是二叉树的根，找到该节点在中序中的位置，则1之前的为二叉树的左子树（42），1之后的为二叉树的右子树（536），然后根据先序中的对应子树24和356，递归重建即可。 重建二叉树：先序+中序（可以），后序+中序（可以），先序+后序（不可以）

尽可能的优化一段代码的性能

如下代码成为了系统的瓶颈，请尽可能的优化；要求找到优化的点和优化方案，分析说明原因。 代码如下：

#define  M   10000
#define  N   10000
#define  L    3
int arr[L][M][N];
int xxx[M * N];
int main()
{
  // init arr and xxx first, omit
  // start
  for (int r=0; r<10000; ++r){
    f(arr);
  }
  return 0;
}

void f( int arr[L][M][N] )
{
  int k = 0;
  for ( int m=0; m<M; m++ ){
    for( int n=0; n<N; n++ ){
        for ( int l=0; l<L; l++){
            int ss = arr[l][m][0] + 1111;
            int tmp = sss + power( log( arr[l][m][n] ), 3 );
            arr[l][m][n] = a[l][m][n] + tmp;
            xxx[k] += arr[l][m][n];
        }
      k = k + 1;
    }
  }
}

修改点： 1.power函数，可以直接写成aaa，这个优化效果与机器型号有关 2.改变数据结构，arr[L][M][N]修改成arr[M][N][L]，修改后的好处： a) 内层循环的一些共有计算可以提前 b) 内层数据访问被连续存储，cache命中率极度提升（最重要也是最根本的优化点） 3.改变循环方式，for l, for m, for n；配合2，修改循环方式后，可以对l循环进行循环展开，减少分支预测失败 4.….

快排

这是一套题目的3个子问题，难度依次递进： 问题1:描述快排的基本思想并进行编码，以及一个典型的应用。 问题2:快排可以应用在链表上么？ 问题3:除了快排，还有其他的排序可以在链表上达到O(lnN)的复杂度么？ 解答1:典型应用：求第N大或者第N小的数。 解答2:快排可以应用在链表上。每次迭代需要两个指针，一个指向比pivot大的结点的链表，一个指向比pivot小的结点的链表，然后合并。 解答3: 还可以使用归并排序，逻辑比较复杂，需要考虑临时指针的使用，每个临时指针在过程中多次复用，否则会消耗大量的空间。具体参考stl中list的排序算法。

使用快排的衍生算法求乱序数组中第N大的数

每轮快排都得找个支点，然后从数组的两边交替开始和支点比较，右边比支点小的数移到左边，左边比支点大的数移到右边，最后只剩一个位置了，再把支点填进来。这时在支点右边的数都比支点大。假设支点的index等于i，那么支点就是第(endIndex-i+1)大的数了。如果endIndex -i + 1 = n,就说明找到了，但是2个数比较有3种结果，分情况讨论如下:

记函数原型为find(a, startIndex, endIndex, n)，当th = endIndex - i + 1时有：

  • th = n，返回支点；

  • th > n，说明第n大的数在支点右边,所以在右边继续找:find(a, i + 1, endIndex, n)；
  • th < n，说明第n大的数在支点左边,右边的数都比要找的数大,也比支点大,所以只需要在左边找第(n - th)大的数即可,find(a, startIndex, i - 1, n - th)；
int choose_nth(int a[], int startIndex, int endIndex, int n)
{
    int midOne = a[startIndex];
    int i = startIndex, j = endIndex;
    if(i == j) //递归出口之一
        return a[i];

    if(i < j)
    {
        while(i < j)
        {
            for(; i < j; j--)
            if(a[j] < midOne)
            {
                a[i++] = a[j];
                break;
            }
            for(; i < j; i++)
            if(a[i] > midOne)
            {
                a[j--] = a[i];
                break;
            }
        }
        a[i] = midOne;//支点归位

        int th = endIndex - i + 1;//计算下标为i的数第几大

        if(th == n)//正好找到
        {
            return a[i];
        }
        else
        {
            if(th > n )//在支点右边找
                return choose_nth(a, i + 1, endIndex, n);
            else//在支点左边找第(n-th)大,因为右边th个数都比支点大
                return choose_nth(a, startIndex, i - 1, n - th);
        }
    }
    
}

撞球问题

在水平光滑无限长的管道两端，有若干相向而行的小球，球的直径和管的直径相同，所有球的质量和速率均相同，球与球之间有一定间距。当两个相向而行的小球相遇时，发生完全弹性碰撞，即为一次碰撞。求下列情况下的碰撞总次数 （1）两端各3个球； （2）一端6个球，一端3个球； （3）一端M个球，一端N个球 答案： （1）9； （2）18； （3）MN 思路: 对于（1）或（2），可以用穷举法计算，目的是引导推导出MN的规律 （2）可以从（1）中推导，即将（2）分成两组（1）来考虑 （3）有两种思路，简单的，可以考虑将（2）的分组考虑成18个11组合，类推出MN；另一种思路，当发生一次碰撞时，可以看成两个小球碰撞后交换位置。

染色问题

现在平面上n条直线，n条直线将平面划分为若干个区域，现在用若干种颜色对这些区域染色，那么至少需要多少种颜色，才能使相邻区域（两个区域的公共部分只有一个点不能视为相邻）的颜色不同？ 答案是两种（无论n条直线将平面划分后是怎样的）。首先是考虑一条直线的情况，显然可以用黑白这两种颜色就能满足要求。当已经将n-1条直线划分的区域染成黑白两种颜色时，那么增加一条新的直线时候，将直线左边的区域的颜色全部从黑变白，白变黑。而右边的区域的颜色保持不变，那么最终相邻区域的颜色还是保持不同。

海量字符串查找问题

有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？ 有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止… 所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串”压缩” 成一个整数。当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小。 是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod) 对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置有没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)。 冲突解决：分离链接法，用链表解决冲突。 一个好的hash函数：

/*key为一个字符串，nTableLength为哈希表的长度
*该函数得到的hash值分布比较均匀*/
unsigned long getHashIndex( const char *key, int nTableLength )
{
    unsigned long nHash = 0;
    while (*key)
    {
        nHash = (nHash<<5) + *key++;  // nHash = nHash*32 + *key;  key++
    }
    return ( nHash % nTableLength );
}

海量文件统计问题

有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。 还是典型的TOP K算法，解决方案如下： 方案1： 顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。 找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_count输出到文件中。这样得到了10个排好序的文件。 对这10个文件进行归并排序（内排序与外排序相结合）。

方案2： 一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

方案3： 与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。

海量日志数据，提取出某日访问百度次数最多的那个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）一个生产者，一个消费者，公用一个缓冲区。 定义两个同步信号量： empty——表示缓冲区是否为空，初值为1。 full——表示缓冲区中是否为满，初值为0。 生产者进程

	while(TRUE){
		生产一个产品;
     	P(empty);
     	产品送往Buffer;
     	V(full);
	}

消费者进程

	while(True){
		P(full);
   		从Buffer取出一个产品;
   		V(empty);
   		消费该产品;
   	}

（2）一个生产者，一个消费者，公用n个环形缓冲区。 定义两个同步信号量： empty——表示缓冲区是否为空，初值为n。 full——表示缓冲区中是否为满，初值为0。 设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。 生产者进程

	while(TRUE){
     	生产一个产品;
     	P(empty);
     	产品送往buffer（in）；
     	in=(in+1)mod n；
     	V(full);
	}

消费者进程

	while(TRUE){
 		P(full);
   		从buffer（out）中取出产品；
   		out=(out+1)mod n；
   		V(empty);
   		消费该产品;
   	}

（3）一组生产者，一组消费者，公用n个环形缓冲区 在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。 定义四个信号量： empty——表示缓冲区是否为空，初值为n。 full——表示缓冲区中是否为满，初值为0。 mutex1——生产者之间的互斥信号量，初值为1。 mutex2——消费者之间的互斥信号量，初值为1。 设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。 生产者进程

while(TRUE){
     生产一个产品;
     P(empty);
     P(mutex1)；
     产品送往buffer（in）；
     in=(in+1)mod n；
     V(mutex1);
     V(full);
}

消费者进程

while(TRUE){
 P(full)
   P(mutex2)；
   从buffer（out）中取出产品；
   out=(out+1)mod n；
   V（mutex2）；
   V(empty);
   消费该产品;
   }

需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。

直线分割平面问题

一条线把平面分成两块，两条线把平面分成四块，如果任意两条线不平行，且没有3条线交在同一点，问100条线将平面分成多少块。 答案：5051 1条直线最多将平面分成2个部分；2条直线最多将平面分成4个部分；3条直线最多将平面分成7个部分；现在添上第4条直线．它与前面的3条直线最多有3个交点，这3个交点将第4条直线分成4段，其中每一段将原来所在平面部分一分为二，所以4条直线最多将平面分成7+4=11个部分． 完全类似地，5条直线最多将平面分成11+5=16个部分；6条直线最多将平面分成16+6=22个部分；7条直线最多将平面分成22+7=29个部分；8条直线最多将平面分成29+8=37个部分． 一般地，n条直线最多将平面分成2+2+3….+N=（N*N+N+2）/2

称重问题

有N个球，其中只有一个是重量较轻的，用天平只称三次就能找到较轻的球，以下的N值哪个是可能的？ A 12 B 16 C 20 D 24 E 28 3 个一次可以测出来，33 = 9 个以内 2 次，33*3 = 27 个以内，3次！

称重问题2

有一架天平，左右两侧均可以放砝码。现在希望能用它称量出从1克开始，尽可能多的连续的整数质量。如果现在允许你任意选择砝码组合，那么对于N个砝码来说最多可以称量出多少个从1克开始的连续质量？ (3N-1)/2，即1+3+32+…+3N-1。砝码的组合方式是使用1克，3克，9克，…，3N-1克的砝码各一个。例如N=2时，称量出1~4克的方法是： 1 = 1; 2 = 3-1; 3 = 3; 4 = 3+1; 而N=3时，依此不难得到5~13克的构造方法。形式化的证明可以使用数学归纳法。 最可能的得到上述答案的思路是从N较小的情况入手，使用递推方法，发现每增加一个砝码时应选择3N-1克的质量。随后使用数学归纳法证明。

称重问题3

现在共有13个球，这批球重有一个球的质量和其它球的质量不同（轻重未知）。给你一个天平，至多只有三次的称量机会，怎样将那个质量不一样的球找出来？ 将13个球分为4球，4球，5球三组。 (1) 第一次称两个4球组，若不想等，则5球组全是标准球。然后就可以用12球类似的方法解决。 1.1 abcd轻。在efgh中取出fgh，替换掉abcd中的bcd。在ijkl中取出jkl，补充到原来fgh的位置。 如果afgh轻，说明答案为a或e。称量ab，如果相等，答案为e；如果不等，答案为a。 如果afgh重，说明答案在fgh中。称量fg，如果相等，答案为h；如果不等，重者为答案。如果一样重，答案在bcd中。称量bc，如果相等，答案为d；如果不等，轻者为答案。 1.2 abcd重。在efgh中取出fgh，替换掉abcd中的bcd。在ijkl中取出jkl，补充到原来fgh的位置。 如果afgh重，答案为a或e。称量ab，如果相等，答案为e；如果不等，答案为a。 如果afgh轻，答案在fgh中。称量fg，如果相等，答案为h；如果不等，轻者为所求。如果一样重，答案在bcd中。称量bc，如果相等，答案为d；如果不等，重者为答案。 (2) 若两个4球组相等，则异常球存在于5球组中。则从两个4球组中任取一个作为标准球。

统计海量数据中的前10个热门数据

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。 外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。尔后在归并段阶将这些临时文件组合为一个大的有序文件，也即排序结果。

外归并排序：外排序的一个例子是外归并排序（External merge sort），它读入一些能放在内存内的数据量，在内存中排序后输出为一个顺串（即是内部数据有序的临时文件），处理完所有的数据后再进行归并。比如，要对 900 MB 的数据进行排序，但机器上只有 100 MB 的可用内存时，外归并排序按如下方法操作：

  • 1.读入 100 MB 的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。
  • 2.将排序完成的数据写入磁盘。
  • 3.重复步骤 1 和 2 直到所有的数据都存入了不同的 100 MB 的块（临时文件）中。在这个例子中，有 900 MB 数据，单个临时文件大小为 100 MB，所以会产生 9 个临时文件。
  • 4.读入每个临时文件（顺串）的前 10 MB （ = 100 MB / (9 块 + 1)）的数据放入内存中的输入缓冲区，最后的 10 MB 作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果。）
  • 5.执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。直至所有数据归并完成。

统计热门查询

要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。所以我们可以基于这个思路分两步来设计该算法。 即，此问题的解决分为以下俩个步骤：

第一步：Query统计 Query统计有以下俩个方法，可供选择： 1.直接排序法 首先我们最先想到的的算法就是排序了，首先对这个日志里面的所有Query都进行排序，然后再遍历排好序的Query，统计每个Query出现的次数了。但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。 让我们回忆一下数据结构课程上的内容，当数据量比较大而且内存无法装下的时候，我们可以采用外排序的方法来进行排序，这里我们可以采用归并排序，因为归并排序有一个比较好的时间复杂度O(NlgN)。排完序之后我们再对已经有序的Query文件进行遍历，统计每个Query出现的次数，再次写入文件中。综合分析一下，排序的时间复杂度是O(NlgN)，而遍历的时间复杂度是O(N)，因此该算法的总体时间复杂度就是O(N+NlgN)=O（NlgN）。 2.Hash Table法 在第1个方法中，我们采用了排序的办法来统计每个Query出现的次数，时间复杂度是NlgN，那么能不能有更好的方法来存储，而时间复杂度更低呢？ 题目中说明了，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。 那么，我们的算法就有了：维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。 本方法相比算法1：在时间复杂度上提高了一个数量级，为O（N），但不仅仅是时间复杂度上的优化，该方法只需要IO数据文件一次，而算法1的IO次数较多的，因此该算法2比算法1在工程上有更好的可操作性。

第二步：找出Top 10 算法一：普通排序 我想对于排序算法大家都已经不陌生了，这里不在赘述，我们要注意的是排序算法的时间复杂度是NlgN，在本题目中，三百万条记录，用1G内存是可以存下的。

算法二：部分排序 题目要求是求出Top 10，因此我们没有必要对所有的Query都进行排序，我们只需要维护一个10个大小的数组，初始化放入10个Query，按照每个Query的统计次数由大到小排序，然后遍历这300万条记录，每读一条记录就和数组最后一个Query对比，如果小于这个Query，那么继续遍历，否则，将数组中最后一条数据淘汰，加入当前的Query。最后当所有的数据都遍历完毕之后，那么这个数组中的10个Query便是我们要找的Top10了。 不难分析出，这样，算法的最坏时间复杂度是N*K， 其中K是指top多少。

算法三：堆 在算法二中，我们已经将时间复杂度由NlogN优化到NK，不得不说这是一个比较大的改进了，可是有没有更好的办法呢？ 分析一下，在算法二中，每次比较完成之后，需要的操作复杂度都是K，因为要把元素插入到一个线性表之中，而且采用的是顺序比较。这里我们注意一下，该数组是有序的，一次我们每次查找的时候可以采用二分的方法查找，这样操作的复杂度就降到了logK，可是，随之而来的问题就是数据移动，因为移动数据次数增多了。不过，这个算法还是比算法二有了改进。 基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？回答是肯定的，那就是堆。 借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此到这里，我们的算法可以改进为这样，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。 思想与上述算法二一致，只是算法在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O（K）降到了O（logK）。 那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了N*logK，和算法二相比，又有了比较大的改进。

总结：

  • 第一步，先用Hash表统计每个Query出现的次数，O(N）；
  • 第二步，采用堆数据结构找出Top 10，NO(logK) 所以，我们最终的时间复杂度是：O（N） + N’O（logK）。（N为1000万，N’为300万）。

编写函数strcpy

// 若参数没有const属性，则需要考虑重叠的情况
char *strcpy(char *strDest, const char *strSrc) {
  if ( strDest == NULL || strSrc == NULL)
    return NULL ;

  if ( strDest == strSrc)
    return strDest ;
    
  char *tempptr = strDest ;
  while( (*strDest++ = *strSrc++) != '/0')
    ;
  
  return tempptr ;
}

试毒问题

有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时后就会死亡至少要多少只小白鼠才能在24小时鉴别出哪瓶水有毒。 给1000个瓶分别标上如下标签（10位长度）： 0000000001 （第1瓶） 0000000010 （第2瓶） 0000000011 （第3瓶） …… 1111101000 （第1000瓶） 从编号最后1位是1的所有的瓶子里面取出1滴混在一起（比如从第一瓶，第三瓶，…里分别取出一滴混在一起）并标上记号为1。以此类推，从编号第一位是1的所有的瓶子里面取出1滴混在一起并标上记号为10。现在得到有10个编号的混合液，小白鼠排排站，分别标上10，9，…1号，并分别给它们灌上对应号码的混合液。24小时过去了，过来验尸： 从左到右，死了的小白鼠贴上标签1，没死的贴上0，最后得到一个序号，把这个序号换成10进制的数字，就是有毒的那瓶水的编号。

调整数组中数字的顺序，使得所有奇数位于数组的前半部分

输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分，要求时间复杂度为O(n) 维护两个指针，第一个指针指向数组的第一个数字，只向后移动，第二个指针指向最后一个数字，只向前移动。当第一个指针指向数字为偶数，且第二个指针指向数字为奇数时，交换数字，并移动两个指针。

输入一个单向链表，输出该链表中倒数第k个结点

输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

  • 从头节点开始遍历链表，直到链表尾节点，统计链表节点个数n。那么倒数第k个节点就是从头结点开始的第n-k-1个节点，则再从头结点开始遍历链表，直到第n-k-1个节点为止。这种思路需要遍历链表两次。
  • 在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。这种思路只需要遍历链表一次。

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变

句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。 例如输入”I am a student.”，则输出”student. a am I”。 思路： 先颠倒句子中的所有字符，再颠倒每个单词内的字符。 如例句中，”I am a student.”第一次整体翻转后得到”.tneduts a ma I”； 第二次在每个单词中内部翻转得到”students. a am I”，即为题解。

颜色变换问题

有一个8*8的矩形，分成64个1*1的小方块。每个方块要么染成黑色或者白色。现在存在两种颜色互换操作： 第一种是将一个任意33的矩形里面的所有小方块的颜色互换（即黑变白，白变黑）； 第二种是将一个任意44的矩形里面的所有小方块的颜色互换； 那么对于任意一种染色方案，是否都可以通过这两种颜色互换操作（可以多次操作）将所有的64个小方块的颜色都变成白色？ 思路： 显然，对于初始的矩形而言，一共有2^64种染色方案。第一种颜色互换操作一共有（8-3+1）(8-3+1)共36种小类型，第二种颜色互换操作一共有55=25种类型，一共有61种小类型。由于在颜色互换的过程时，每种小类型最多出现一次（两次相同小类型的操作相当于没有操作，颜色没有变化），且最终结果与操作的顺序无关。所以颜色互换操作的状态最多只有2^61种，是小于2^64种染色方案的。因此，最终的答案是不可能的。

100w个数中找出最大的100个数

  • 方案1：用一个含100个元素的小根堆（堆顶的元素为最小的元素，比堆顶元素小的元素就不用考虑了）完成。复杂度为O(100w*lg100)。
  • 方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，直到比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。
  • 方案3：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，直到扫描了所有的元素。复杂度为O(100w*100)。

3*4的格子有几个矩形

MN网格中有横竖各M+1、N+1条直线，其中，任意各取两条都可以组成一个长方形。 C(4,2)C(5,2)=610=60; A(N,N)=N! A(N,M)=N(N-1)…(N-M+1) C(N,M)=A(N,M)/A(M,M)

50个红球，50个篮球，2个袋子，一个袋子能装任意个球(0~100)

现由你将这100个球，以一定方法装入这两个袋子。另找一个不明真相的路人，闭眼，随机从两个袋子中任意摸一个球。 要使得他摸出红球的概率最高，你应该如何分配这100个球。 答案：一个袋子一个红球，另一个袋子49个红球+50个蓝球 首先可能会列方程解，说明思路比较清晰。但方程比较难解，如果可以解出来就加分。如果解不出来，建议他通过思考解答 能首先将问题分解为两个袋子红球概率和最大，加分 首先优化一个袋子红球的概率(50个红球全在袋子中)，其次不损失多余的红球，即可得出答案 还需要通过迭代法验证答案的正确性

54张扑克牌，一半红色一半黑色，随机取两张，一红一黑的概率

27/53

求二进制数中1的个数。

解法1：对于二进制操作，除以一个2，如果除的过程中有余，那么就表示当前位置有一个1。考虑利用整型数据除法的特点，通过相除和判断余数的值来分析。

int Count ( BYTE v )
{
  int num = 0;
  while(v)
  {
    if(v%2 == 1)
      num++;
    v = v/2;
  }
  return num;
}

解法2：对解法1进行改进，通过移位操作来实现除法。通过与00000001进行与操作来判断当前八位数字最后一位是否为1.

int Count ( BYTE v )
{
  int num = 0;
  while(v)
  {
    num += v & 0x01;
    v >>= 1;
  }
  return num;
}

解法3：在每次判断中仅与1来进行判断，将复杂度由二进制数的位数降低至二进制数中1的个数。v & (v-1)操作每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。

int Count ( BYTE v )
{
  int num = 0;
  while(v)
  {
    v &= (v-1);
    num++;
  }
  return num;
}

解法4：使用分支操作（switch语句），针对8位数据，直接把0~255的情况都罗列出来，并使用分支操作，可以得到答案。不是好的方法。

int Count ( BYTE v )
{
  int num = 0;
  switch( v )
  {
    case 0x0:
      num = 0;
      break;
    case 0x1:
    case 0x2:
    // …
    case 0x80:
      num = 1;
      break;
    case 0x3:
    case 0x6:
    // …
    case 0xc0;
      num = 2;
      break;
    // …
  }
  return num;
}

解法5：查表法，典型的空间换时间算法，把0~255中1的个数直接存储在数组中，v作为数组的下标，countTable[v]就是v中1的个数。算法的时间复杂度仅为1.

int countTable[256] = {0,1,1,2,1,2,2,3,…7,6,7,7,8};

int Count ( BYTE v )
{
  //check parameter
  return countTable[v];
}

寻找发帖“水王”：由水王ID所发的帖子数超过了总帖子数的一半。

最直接的方法，先对所有ID排序，再统计各个ID出现的次数。如果某个ID出现次数超过总数的一半，那么就输出这个ID。这个算法的时间复杂度为O( N*logN + N ) . 如果ID列表已经是有序的，也可以不用扫描统计各个ID的出现次数。如果一个ID出现的次数超过总数N的一半，那么无论水王的ID是什么，这个有序的ID列表的第N/2项（从0开始编号）一定是这个ID。除去排序的时间复杂度后，处理的时间复杂度为O(1)。 上面的方法都需要先对ID列表进行排序，时间复杂度方面没有根本的改进。如果每次删除两个不同的ID，那么在剩下的ID列表中，水王ID出现的次数仍然超过总数的一半（即，哪怕每次拿一个其他ID来同归一个水王的ID，最终剩下的仍然是水王的ID，且只有水王的ID能够满足这种挑战）。可以通过不断重复这个过程，把ID列表中的ID总数降低。从而避免了排序这个耗时的步骤，总的时间复杂度也只有O( N )，且只需要常数的额外内存:

Type Find( Type* ID ,int N )
{
  Type candidate;
  int nTimes, i;
  for( i = nTimes = 0; i<N; i++)
  {
    if( nTimes == 0 )
      candidate=ID[i], nTimes=1;
    else
    {
      if(candidate == ID[i])
        nTimes++;
      else
        nTimes--;
    }
  }
  return candidate;
}

大致思想就是：假设每个ID都有可能是水王，那么在遍历时这个水王就要遇到一种挑战，可能自己的帖子数是会增加的，也可能是遇到挑战的，帖子数要减少的。这样遍历下来，只有水王的帖子增加的减去遇到挑战的帖子数会是大于0的。其他任何帖子假设为水王时都是禁不起挑战的。 步骤：

  1. 可以假设帖子的第一个ID是次数最大的，用candidate记录，次数用nTimes记录。
  2. 遍历下一个ID，如果跟candidate一样，nTimes++，否则，遇到一个挑战，则nTimes–，如果nTimes == 0，下一步就要重复第一步了。
  3. 遍历结束，nTimes>0的那个candidate就是水王ID，他是获胜者。 问题解决的关键在于水王ID超过了总数的一半这一特殊条件。

寻找最大的K个数

解法1 部分排序：在元素数量不大的情况下，采用快排或者堆排序对所有元素排序，取前K个，时间复杂度为O( NlogN )+O( K )= O( NlogN ); 采用部分排序算法，如选择排序或交换排序，把N个数中的前K个数排序出来，复杂度为O( N*K ); 具体选择取决于K与logN的大小。 解法2 快速排序：按照快速排序的思路，假设N个数存储在数组S中，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中的元素小于X。这时有两种可能：

  1. Sa中的元素的个数小于K，Sa中所有的数和Sb中最大的K- Sa （ Sa 指Sa中元素的个数）个元素就是数组S中最大的K个数。
  2. Sa中元素的个数大于或等于K，则需要返回Sa中最大的K个元素。 如此递归。平均时间复杂度为O( N*logK )。伪代码如下： ```c Kbig( S, K ) if ( k <= 0 ): return [] if ( S. length <= K ): return S ( Sa,Sb ) = Partition( S ) return Kbig( Sa, K ).Append( Kbig( Sb, K - Sa.length ))

Partition(S): Sa=[]; Sb=[]; Swap( s[1], S[random() % S. length] ) p=S[1]

for i in [2: S.length]: S[i] > p ? Sa.Append( S[i] ):Sb.Append( S[i] )

Sa.length < Sb.length ? Sa.Append(p):Sb.Append(p) return (Sa,Sb)


**解法3 二分查找法**：寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数。可以使用二分搜索的策略来寻找N个数中的第K大的数。然后，对于一个给定的数p，可以在O（N）的时间复杂度内找出所有不小于p的数。
假如N个数中最大的数为Vmax，最小的数为Vmin，那么这N个数中的第K大数一定在区间[Vmin, Vmax]之间。那么，可以在这个区间内二分搜索N个数中的第K大数p。伪代码如下：

```c
while(Vmax – Vmin > delta)
{
  Vmid = Vmin + (Vmax - Vmin) * 0.5;
  if( f(arr, N, Vmid) >= K)
    Vmin = Vmid;
  else
    Vmax = Vmid;
}

伪代码中f（arr, N, Vmid）返回数组arr[0, …, N-1]中大于等于Vmid的数的个数。 上述伪代码中，delta的取值要比所有N个数中的任意两个不相等的元素差值之最小值小。如果所有元素都是整数，delta可以取值0.5。循环运行之后，得到一个区间（Vmin, Vmax），这个区间仅包含一个元素（或者多个相等的元素）。这个元素就是第K大的元素。整个算法的时间复杂度为O（N * log2（|Vmax - Vmin| /delta））。由于delta的取值要比所有N个数中的任意两个不相等的元素差值之最小值小，因此时间复杂度跟数据分布相关。在数据分布平均的情况下，时间复杂度为O（N * log2（N））。

解法4 堆排序：当N非常大的情况下，不能一次性装入内存操作。设N > K，前K个数中的最大K个数是一个退化的情况，所有K个数就是最大的K个数。考虑第K+1个数X。如果X比最大的K个数中的最小的数Y小，那么最大的K个数还是保持不变。如果X比Y大，那么最大的K个数应该去掉Y，而包含X。如果用一个数组来存储最大的K个数，每新加入一个数X，就扫描一遍数组，得到数组中最小的数Y。用X替代Y，或者保持原数组不变。这样的方法，所耗费的时间为O（N * K）。 进一步，可以用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中最小的一个。每次新考虑一个数X，如果X比堆顶的元素Y小，则不需要改变原来的堆，因为这个元素比最大的K个数小。如果X比堆顶元素大，那么用X替换堆顶的元素Y。在X替换堆顶元素Y之后，X可能破坏最小堆的结构（每个结点都比它的父亲结点大），需要更新堆来维持堆的性质。更新过程花费的时间复杂度为O（log2K）。

解法5 计数排序：可以通过改进计数排序、基数排序等来得到一个更高效的算法。但算法的适用范围会受到一定的限制。如果所有N个数都是正整数，且它们的取值范围不太大，可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。比如，所有整数都在（0, MAXN）区间中的话，利用一个数组count[MAXN]来记录每个整数出现的个数（count[i]表示整数i在所有整数中出现的个数）。我们只需要扫描一遍就可以得到count数组。然后，寻找第K大的元素：

for( sumCount = 0, v = MAXN – 1;  v >= 0;  v-- )
{
  sumCount += count[v];
  if( sumCount >= K )
    break;
}
return v;

极端情况下，如果N个整数各不相同，我们甚至只需要一个bit来存储这个整数是否存在。 实际情况下，并不一定能保证所有元素都是正整数，且取值范围不太大。上面的方法仍然可以推广适用。如果N个数中最大的数为Vmax，最小的数为Vmin，我们可以把这个区间[Vmin, Vmax]分成M块，每个小区间的跨度为d =（Vmax – Vmin）/M，即 [Vmin, Vmin+d], [Vmin + d, Vmin + 2d],……然后，扫描一遍所有元素，统计各个小区间中的元素个数，跟上面方法类似地，我们可以知道第K大的元素在哪一个小区间。然后，再对那个小区间，继续进行分块处理。这个方法介于解法三和类计数排序方法之间，不能保证线性。跟解法三类似地，时间复杂度为O（（N+M）* log2M（|Vmax - Vmin|/delta））。遍历文件的次数为2 * log2M（|Vmax - Vmin|/delta）。当然，我们需要找一个尽量大的M，但M取值要受内存限制。

补：寻找第K大的数。

求最大公约数。考虑两个正整数都很大的情况。

欧几里得辗转相除法求最大公约数：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。 如：f(42,30) = f(30,12) = f(12,18) = f(12,6) = f(6,6) = f(6,0) 即：f(x,y) = f(y, x%y) (x >= y > 0) 或f(x,y)=f(x-y, y). 解法1：直接用代码来实现辗转相除法：

int gcd(int x, int y)
{
  return (!y)?x:gcd(y, x%y);
}

解法2：解法1中用到%运算，其中包含除运算，这对于大整数而言将成为算法效率的瓶颈。采用公式f(x,y)=f(x-y, y)，就可以不再需要进行大整数的取模运算，而转换成简单得多的大整数的减法。

BigInt gcd(BigInt x, BigInt y)
{
  if( x < y)
    return gcd(y, x);
  if(y == 0)
    return x;
  else
    return gcd( x-y, y);
}

解法3：结合上两种算法，并采用移位操作。

补：大整数的实现。

寻找数组中的最大值和最小值

  • 解法1：遍历两次，分别求出最大值、最小值。需要比较2*N次。

  • 解法2：按顺序将数组中相邻的两个元素看成一组，遍历数组，调整每一组中两个元素的顺序，使大的数在偶数位上，小的数在奇数位上。然后分别从奇数位、偶数位上求出最大最小值，总的比较次数为1.5*N次。

  • 解法3：不破坏原数组，仍然将数组每相邻两位看成一组，定义两个变量min、max，遍历数组，相邻两位比较，然后得到的大者与max比较，小者与min比较。总的比较次数仍为1.5*N。

  • 解法4：采用分治算法，分别求出前后N/2个数的min和max，然后取较小的min及较大的max。但是总的比较次数仍为1.5*N。

    ​

快速找出一个数组中的两个数字，其和等于给定值。

  • 解法1：穷举法，时间复杂度O(N);
  • 解法2：变通思路，对数组中的每个数字arr[i]都判别sum-arr[i]在不在数组中。这样就变通为一个查找算法。将数组排序，需要时间O(NlogN)。对于每个arr[i]用二分法查找sum-arr[i]的时间复杂度都为O(logN)，总计NO(logN)+ O(NlogN)= O(NlogN)。

当然也可以用hash的方法简化查找，但是空间效率加大了。

  • 解法3：首先对数组进行排序，时间复杂度为O(N*logN)。

然后令i=0，j=n-1，看arr[i]+arr[j]是否等于sum，如果是则结束，如果小于sum，则i=i+1;如果大于sum，则j=j-1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，该步操作的时间复杂度为O(N)。两步加起来的时间复杂度为O(N*logN)。 查找伪码：

for( i=0,j=n-1; i<j; )
  if(arr[i] + arr[j] == sum)
    return (i , j);
  else if( arr[i] + arr[j] < sum)
    i++;
  else
    j--;
return (-1,-1);

求数组的子数组之和的最大值。

  • 解法1：分治法，将所给数组A[0],…A[n-1]分为长度相等的两段数组A[0],…,A[n/2-1]和A[n/2],…,A[n-1],分别求出这两段数组各自的最大子段和，则原数组的最大子段和为以下三种情况的最大值：
  1. A[0],…A[n-1]的最大子段和与A[0],…,A[n/2-1]的最大子段和相同；
  2. A[0],…A[n-1]的最大子段和与A[n/2],…,A[n-1]的最大子段和相同；
  3. A[0],…A[n-1]的最大子段跨过其中间两个元素A[n/2-1]和A[n/2]。 第1和第2两种情况是问题规模减半的相同子问题，可以通过递归求得。 第3种情况只要找到以A[n/2-1]结尾的和最大的一段数组之和S1，以及以A[n/2]开始和最大的一段数组之和S2，那么第3种情况的最大值为S1+S2,只要对原数组进行一次遍历即可。 分治法使得问题被分解为两个问题规模减半的子问题再加上一次遍历算法。总的时间复杂度为O(N*logN)。
  • 解法2：动态规划法，考虑数组的第一个元素A[0]，以及最大的一段数组A[i],…,A[j]跟A[0]之间的关系，有以下几种情况：
  1. 当0=i=j时，元素A[0]本身构成和最大的一段；
  2. 当0=i<j时，和最大的一段以A[0]开始；
  3. 当0<i时，元素A[0]跟和最大的一段没有关系。 这样可以将一个大问题(N)转化为一个较小的问题(N-1)。假设已经知道A[1],…,A[N-1]中和最大的一段数组之和为All[1]，并且已经知道A[1],…,A[N-1]中包含A[1]的和最大的一段数组为Start[1]。则由以上三种分析的情况可看出A[0],…,A[N-1]中问题的解All[0]是三种情况的最大值max{A[0],A[0]+Start[1],All[1]}。通过这样的分析可以看出这个问题无后效性，可以使用动态规划的方法解决。代码如下： 
    int MaxSum(int* A, int n)
{
  Start[n-1] = A[n-1];
  All[n-1] = A[n-1];
  for(i = n-2; i>=0; i--) //从数组末尾往前遍历，直到数组首
  {
 Start[i] = max( A[i], A[i]+Start[i+1]);
 All[i] = max(Start[i],All[i+1]);
  }
  return All[0]; //遍历完数组，All[0]中存放结果
}

    时间复杂度为O(N); 改进： Start[i] = max( A[i], A[i]+Start[i+1]);
    All[i] = max(Start[i],All[i+1]); 如果Start[i+1]<0，则Start[i]=A[i]。并且在这两个递推式中，其实都只需用两个变量就可以了。Start[k+1]只有在计算Start[k]时使用，而All[k+1]也只有在计算All[k]时使用。所以改进程序只需O(1)的空间就足够了：

    int MaxSum(int* A, int n)
{
  nStart = A[n-1];
  nAll= A[n-1];
  for(i = n-2; i>=0; i--) 
  {
 nStart = max( A[i], A[i]+nStart);
 nAll = max(nStart,nAll);
  }
  return nAll; 
}

数组循环移位

把一个含有N个元素的数组循环右移K位，要求时间复杂度为O(N)，且只允许使用两个附加变量。

*解法1：循环右移K位之后的情形跟右移k=K%N位之后的情形一样：

RightShift(int* arr, int N, int K)
{
  K %=N;
  while(K--)
  {
    int t=arr[N-1];
    for(int i = N-1; i>0; i--)
      arr[i] = arr[i-1];
    arr[0] = t;
  }
}

时间复杂度为O(N^2).

  • 解法2：假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。比较之后可以看到其中有两段的顺序是不变的，即1234和abcd，把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：
  1. 逆序排列abcd：abcd1234 -> dcba1234;
  2. 逆序排列1234：abcd1234 –> dcba4321;
  3. 全部逆序：abcd1234 -> 1234abcd。 代码： ```c Reverse(int* arr, int b, int e) { for(; b<e; b++,e–) { int temp = arr[e]; arr[e] = arr[b]; arr[b] = temp; } }

RightShift(int* arr, int N, int k) { K %= N; Reverse(arr, 0, N – K – 1); Reverse(arr, N – K, N – 1); Reverse(arr, 0, N – 1); }




## 判断字符串是否是另一个字符串循环位移字符串的子串

给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位得到的字符串包含。例如，给定s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD,返回false。

* 解法1：穷举法

```c
char src[] = ”AABBCD”;
char des[] = ”CDAA”;
int len = strlen(src);
for(int i=0;  i<len;  i++)
{
  char tempchar = src[0];
  for(int j=0;  j<len-1;  j++)
    src[j] = src[j+1];
  
  src[len-1] = tempchar;
  if( strstr(str,des)==0 )
    return true;
}
return false;
  • 解法2：空间换时间，对循环移位之后的结果进行分析。假设s1=ABCD，s1循环移位的结果如下：

ABCD -> BCDA -> CDAB -> DABC ->ABCD; 若保留前面移走的数据，则可发现如下规律： ABCD -> ABCDA -> ABCDAB -> ABCDABC ->ABCDABCD。 可见对s1做循环移位所得到的字符串都将是字符串s1s1的子字符串。如果s2可以由循环移位得到，那么s2一定在s1s1上。 由此，将问题转换成考察s2是否在s1s1上，可通过调用一次strstr函数得到结果。

计算字符串的相似度。

分析：两个字符串的距离肯定不超过它们的长度之和。 考虑如何才能把这个问题转化成规模较小的同样的问题： 如果两个串A和B的第一个字符是相同的，则只要计算A[2，…lenA]和B[2，…lenB]的距离就可以了。但是如果两个串的第一个字符不相同，那么进行如下操作：

  1. 删除A串的第一个字符，然后计算A[2，…lenA]和B[1，…lenB]的距离；
  2. 删除B串的第一个字符，然后计算A[1，…lenA]和B[2，…lenB]的距离；
  3. 修改A串的第一个字符为B串的第一个字符，然后计算A[2，…lenA]和B[2，…lenB]的距离；
  4. 修改B串的第一个字符为A串的第一个字符，然后计算A[2，…lenA]和B[2，…lenB]的距离；
  5. 增加B串的第一个字符到A串的第一个字符之前，然后计算A[1，…lenA]和B[2，…lenB]的距离；
  6. 增加A串的第一个字符到B串的第一个字符之前，然后计算A[2，…lenA]和B[1，…lenB]的距离；

由题意知，并不在乎两个字符串变得相等之后的字符串是怎样的，所以可以将上面的6个操作合并为：

  1. 一步操作之后，再将A[2，…lenA]和B[1，…lenB]变成相同的字符串；
  2. 一步操作之后，再将A[1，…lenA]和B[2，…lenB]变成相同的字符串；
  3. 一步操作之后，再将A[2，…lenA]和B[2，…lenB]变成相同的字符串； 实现代码： 
    int CalculateStringDistance( string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)
{
  if(pABegin > pAEnd)
  {
 if( pBBegin > pBEnd)
   return 0;
 else
   return pBEnd – pBBegin +1;
 }

 if(pBBegin > pBEnd)
 {
   if(pABegin > pAEnd)
     return 0;
   else
     return pAEnd – pABegin + 1;
 }
     
 if( strA[pABegin] == strB[pBBegin])
   return CalculateStringDistance( strA, pABegin +1, pAEnd, strB, pBBegin +1, pBEnd);
 else
 {
   int t1 = CalculateStringDistance( strA, pABegin, pAEnd, strB, pBBegin +1, pBEnd);
   int t2 = CalculateStringDistance( strA, pABegin +1, pAEnd, strB, pBBegin, pBEnd);
   int t3 = CalculateStringDistance( strA, pABegin +1, pAEnd, strB, pBBegin +1, pBEnd);
   return minValue( t1, t2, t3) + 1;
 }
}
}

从无头单链表中删除节点

假设给定指针为pCurrent，Node* pNext = pCurrent->Next。 假设pCurrent指向当前节点为B，B的前一个节点为A，后一个节点为C。因为单链表没有头指针，因此无法追溯到A，假设直接删除B，则无法将A和C相连。 解法：由给定条件可以安全的删除节点C，然后用C中的数据项替换B中的数据项，代码如下：

pCurrent -> Next = pNext -> Next;
pCurrent -> Data = pNext -> Data;
delete pNext;

设计队列容器的数据结构，使得返回最大元素的操作时间复杂度尽可能的低。

  • 解法1：用传统方式来实现队列，采用一个数组或链表来存储队列的元素，利用两个指针分别指向队尾和队首。如果采用这种方法，那么取最大值的操作需要遍历队列的所有元素。时间复杂度为O(N)；
  • 解法2：考虑用最大堆来维护队列中的元素。堆中每个元素都有指向它的后续元素的指针。这样，取最大值操作的时间复杂度为O(1)，而入队和出队操作的时间复杂度为O( logN )。
  • 解法3：对于栈来讲，Push和Pop操作都是在栈顶完成的，所以很容易维护栈中的最大值，它的时间复杂度为O(1),实现代码如下：
class stack
{
  public:
    stack()
    {
      stackTop = -1;
      maxStackItemIndex = -1;
    }

    void Push( Type x)
    {
      stackTop++;
      if( stackTop >= MAXN ) // 溢出
        ;
      else
      {
        stackItem[stackTop] = x;
        if( x > Max() ) // 当前插入值为最大值
        {
          link2NextMaxItem[stackTop] = maxStackItemIndex; // 之前的最大值成为第二大的值，即当前值（最大值）的下一个最大值
          maxStackItemIndex = stackTop; // 最大值坐标指向当前值
        }
        else
          link2NextMaxItem[stackTop] = -1;
      } 
    }

    Type Pop()
    {
      Type ret;
      if( stackTop < 0 )
        ThrowException(); // 没有元素了
      else
      {
        ret = stackItem[ stackTop ];
        if( stackTop == maxStackItemIndex ) // 当前出栈的为最大值
          maxStackItemIndex = link2NextMaxItem[stackTop]; // 修改最大值坐标
        stackTop--;
      }
      return ret;
    }
    
    Type Max()
    {
      if( maxStackItemIndex >= 0 )
        return stackItem[ maxStackItemIndex];
      else 
        return –INF;
    }
    
  private:
    Type stackItem[MAXN];
    int stackTop;
    int link2NextMaxItem[MAXN]; // 维护一个最大值序列
    int maxStackItemIndex;
}

如果能够用栈有效地实现队列，而栈的Max操作又很容易实现，那么队列的Max操作也就能有效地完成了。考虑使用两个栈A跟B来实现队列。

class Queue
{
public:
  Type MaxValue( Type x, Type y)
  {
    if( x > y )
      return x;
    else
      return y;
  }

  Type Queue::Max()
  {
    return MaxValue( stackA.Max(), stackB.Max() );
  }

  EnQueue( v )
  {
    stackB.push( v );
  }
  
  Type DeQueue()
  {
    if( stackA.empty() )
    {
      while( !stackB.empty() )
        stackA.push( stackB.pop() )
    }
    return stackA.pop();
  }

  private:
  stack stackA;
  stack stackB;
}

从每个元素的角度来看，它被移动的次数最多可能有3次，这3次分别是：从B栈进入、当A栈为空时从B栈弹出并压入A栈、从A栈被弹出。相当于入队经过一次操作，出队经过两次操作。所以这种方法的平均时间复杂度是线性的。

完成一个字符串替换函数的设计和实现，如果需要在原串上替换呢？

Int strrep(char * content, int len, const char * src, const char * des); 要考虑src的长度超过des长度时的处理方法

写一个函数把链表奇数位和偶数位交换

A->B->C->D->E->F->G 结果为B->A->D->C->F->E->G 需要注意链表长度是奇数的处理

写一个把字符串的IP地址变成32位整数的函数

要求能够检查各种输入错误。例如将：“127.0.0.1”转成 127*2^26 + 1;

完成一个trim_string函数

将一个字符串两端的空格、回车、tab符号去掉。

实现linux下的tail命令，显示文件的最后n行

设定一块固定大小的 buffer，从文件尾部向前读取，并计算 buffer 中换行的数量，等于 n 时开始往后输出。 时间复杂度 O(n)，空间复杂度 O(1)

实现两棵树是否相等的比较

请实现两棵树是否相等的比较，相等返回0，否则返回其他值，并说明算法复杂度。 数据结构为：

typedef struct _TreeNode{
  char c;
  TreeNode *leftchild;
  TreeNode *rightchild;
} TreeNode;

函数接口为：

int CompTree(TreeNode* tree1,TreeNode* tree2);

注：A、B两棵树相等当且仅当Root->c==RootB–>c,而且A和B的左右子树相等或者左右互换相等。

使用递归算法：

int CompTree(TreeNode* tree1,TreeNode* tree2)
{
  if ( tree1==NULL && tree2 == NULL )
    Return 0;
  if ( tree1 == NULL || tree2 == NULL )
    Return 1;
  if (tree1->c != tree2->c)
    return 1;
  if ( compTree(tree1->leftchild, tree2->leftchild) == 0 && compTree(tree1->rightchild, tree2->rightchild) == 0 )
    return 0;
  if ( compTree(tree1->leftchild, tree2->rightchild) == 0 && compTree(tree1->rightchild, tree2->leftchild) == 0 )
  return 0;
}

由于需要比较的状态是两棵树的任意状态，而二叉树上的每一个节点的左右子节点都可以交换，因此一共需要对比2^n种状态。算法复杂度是O（2^n）

给定A, B两个整数，不使用除法和取模运算，求A/B的商和余数

1．最基本的算法是，从小到大遍历：

For (i = 2 to A -1)
if (i * B > A)

商 = i -1; 余数 = A – (i-1)*B; 2．较好的算法是采用2分法，查找[2, A]中满足尚的解。 更好的算法是采用位操作的思想来实现除法。

查找兄弟字符串

一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b 是a的兄弟单词。现在有一个字典，用户输入一个单词，从字典找出这个单词有多少个兄弟单词

1.建索引：将字典中的每个单词都按照ascii排序，并建hash表。Key是ascii排序之后的单词，value是key出现的次数。 2.查找：将单词按照ascii排序，然后从hash表中查找。

分解整数

从命令行读入一个整数，把它分解为多个整数之和，并打印所有不同的序列，每行一个，比如，3可以分解为： 1+1+1, 2+1, 3

递归解决

int print(int min, int max, char* buf, int buflen, int strlen)
{
    for (int i=min; i<=max; i++)
    {
        if (i==max)
        {
            printf("%s%d\n", buf,i);
        }
        else
        {
            int len = snprintf(buf+strlen, buflen-strlen, "%d+", i);
            print(i,max-i,buf,buflen,strlen+len);
            *(buf+strlen) = '\0';
        }
}
return 0;
}

int main(int argc, char* argv[])
{
    int num = 0;
    printf("Input the num:\n");
    scanf("%d",&num);
    const int buflen=1024;
    char buf[buflen] = {0};
    print(1,num,buf,buflen,0);
    return 0;
}

将数组随机化

给定数组A, 长度为n，以及随机函数rand(n); 将该数组随机化。要求每个元素等概率的被放到数组的任何位置，且每个元素均不在原来的位置。 Rand（n）函数：对于任何输入n（正整数），生成一个[0, n-1]区间的数。 用每个元素的位置调用rand函数，将得到的数字对应位置的元素与当前元素交换。

int shuffle(int *a, int n)
{
  if (n <= 1) return 0;
  for (int i = 1; i < n; i++)
  {
    int j = rand(i);
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
  return 0;
}

变形二分查找

一个有序的数组，不包含重复的元素。从某个位置切一下之后，把前面一段粘在后面一段，形如： 1,2,4,5,6 -> 4,5,6,1,2 要求在这样处理之后的数组中查找指定元素

两种做法。简单一点的是做两遍二分：

  1. 二分查找切割点。二分得到mid后，拿mid值依次与数组的两个端点进行比较，确定mid值在哪一段上
  2. 选择合适的段，再做一遍2分查找 复杂一点的是要求一遍处理就完成，做法还是二分，但判定条件会稍微复杂些，略

计算100!（100的阶乘）最后有多少个0？

每一个0都是由2和5相乘组成，而100！因子中5的数量小于2的数量，因此之需要计算100！的有多少个5的因子。 100/5 + 100/5/5 + 100/5/5/5 = 20 + 4 = 24.

设计线程安全的高效数据结构

现在有大量的数据，请设计一个数据结构来存储它们，这个数据结构能被多线程访问，既能实现快速的查找，同时能进行更新操作（插入、删除、修改等），更新的同时不能影响查找的速度。 使用哈希链表来存储数据，实现快速查找。 因为更新的同时不能影响查找的速度，因此同时使用两个哈希链表来存储数据，一个用来查找，即只做读操作，另一个用来进行更新操作。每隔一段时间，将这两个链表进行切换，使用更新过的链表作为查找的链表，同时进行一次数据同步操作。这样，进行数据查找时不需要加锁，只在更新时进行加锁，减少了加解锁的次数，同时提高了查找效率。

找出数组中两个只出现一次的数字

一个整型数组里除了 两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。 请写程序找出这个只出现一次的数字。 这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次， 其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。 有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。 我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结 果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0， 也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的 位的位置，记为第N位。现在我们以第N位是不是1为 标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1， 而第二个子数组的每个数字的第N位都为0。 现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都 出现了两次。因此到此为止，所有的问题我们都已经解决。

实现字符串替换函数

编写一个函数，将字符串A中的B字串全部替换为C字串，例如A串为1234abcd，B串为12，C串为34， 则替换后的串为 3434abcd。原地操作，不能额外分配空间，假设空间足够

为了简化问题，假设原串空间足够，且不考虑h)中的循环替换情况（如果面试者能主动提出就更好了），则： a) 如果B串长度大于等于C串，则使用两个指针，一个指向当前的可写位置，一个指向当前遍历到的位置，从前向后依次操作，一次遍历完成，时间复杂度O(n)。一般人会先给出每替换完一个串，就将后面的字符串全部向前移动的方法，看是否能够根据提示给出O(n)的方法。 b) 如果B串长度小于C串，则将A串先全部拷贝到空间尾部，再类似a)从前向后依次操作，时间复杂度O（2n）。看面试者是否能意识到从前向后替换和从后向前替换的结果有可能是不同的。

给n个unsigned short，可能有重复，求所有重复的数字和重复次数

对于unsigned short，数组做hash即可

如果是n个unsigned long，如何求解 对于unsigned long，需要考虑hash冲突

对称子字符串的最大长度

输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如 输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

要判断一个字符串是不是对称 的，不是一件很难的事情。我们可以先得到字符串首尾两个字符，判断是不是相等。如果不相等，那该字符串肯定不是对称的。否则我们接着判断里面的两个字符是 不是相等，以此类推。

现在我们试着来得到对称子字 符串的最大长度。最直观的做法就是得到输入字符串的所有子字符串，并逐个判断是不是对称的。如果一个子字符串是对称的，我们就得到它的长度。这样经过比较，就能得到最长的对称子字符串的长度了。

如果我们换一种思路，我们从里向外来判断。也就是我们先判断子字符串A是不是对称的。如果A不是对称的，那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果A对称，那么我们只需要判断A两端延长的一个字符是不是相等的，如果相等，则延长后的字符串是对称的。因此在知道A是否对称之 后，只需要O（1）的时间就能知道aAa是不是 对称的。

在一个正整数序列中求和最大的非相邻子序列（序列任两元素在原序列里都不相邻）

遍历该序列a(n)，每步的最大序列 S(n) = max{ s(n), s(n-1)+a(n)}

找出重复了奇数次的数

编写一函数，要求如下： 有奇数位长的数组，其中只有一个元素是重复了奇数次，其他都重复了偶数次，找出那个唯一的元素。比如一整形数组A：{1, 2, 3, 1, 3}，在这个数组里1，3两元素都重复了偶数次，而2重复了奇数次，我们需要的是将2给找出来。

注：该题可要求面试者只使用C语言进行实现

  • 方法一：利用字典对数组中各个元素分别进行次数统计存放，然后依次判断各个元素的奇偶情况
  • 方法二：利用“异或”进行处理，代码如下：（较优） 
    A = [1, 2, 3, 1, 3 ]
B = A[0]
for i in A[1: len(A)]:
 B = B ^ i
print B
  • 方法三：先排序，再进行统计（可省去内存存放）

一个数组A[N]，包含取值为[1,N]的元素，请判断是否有重复元素

解法： 1、Sum(1…N)!=sum(A[0],A[N-1])则重复 2、hash记数法 3、排序后再判重

数轴上从左到右有n个点a[0],a[1]…,a[n-1]，给定一根长度为L的绳子，求绳子最多能覆盖其中的几个点。要求算法复杂度为o(n)。

void maxCover(int* a, int n, int l) {
   int maxCover = 1;
   int beginPos = 0, endPos = 1;
   while (endPos <= n – 1 ) {
       if (a[endPos] – a[beginPos] >= l) {        
          If (a[endPos] – a[beginPos] == l ) {
             maxCover = endPos–beginPos + 1;
          } elseif (a[endPos] – a[beginPos] > l ) {
             maxCover = endPos–beginPos;
          }
          beginPos++;
       }
       endPos++;
   }
   return maxCover;
}

二路归并排序变种

数组A和数组B分别包含m和n个数，且在数组内部有序非重复，但数组A和数组B之间可能存在相同数。编写一个函数，实现数组A和数组B中所有元素的去重排序，数据最后按序依次存放在数组C中。

可以开辟m+n的数组C，使用二路归并排序将数组A和数组B去重排序C，整体时间复杂度为O(m+n)。具体方法为使用三个指针，分别指向数组A和数组B的比较位置，以及数组C的存储位置，每次对指针指向的两个数据进行比较，排序胜出的元素拷贝到数组C中，并且对应的选取的数组和数组C的指针向后移动。其中若两个元素相同，则同时移动。直到任意一个数组完成，并将未完成的数组元素全部拷贝到数组C的尾部。

系统数据结构设计

1）假设有一台机器A，有约1G内存可用，另外若干台机器（B、C、D……）通过网络TCP向机器A传输数据，A机器把接收到的数据写入硬盘。B、C、D等机器的数据按记录传输，每条记录大小16M。 2）为了保证每条记录的原子性，B、C、D等机器每次先向A请求传输，然后再进行数据传输。请求时，A机器会给记录分配一个序号，写入文件时每个记录按序号顺序、原子写入。 3）B、C、D等机器处理速度和网络速度都不尽相同，因此记录数据传递到A的顺序可能不一定按分配好的序号顺序到达。

现在要求给A上程序设计一个数据结构，利用该数据结构能高效的接收数据并顺序高效的写入磁盘（也即是不能序号大的记录先写，然后再回写序号小的记录；也不能接收到几十个字节就写一次磁盘）。

主要考察系统设计思路： 要点：A机器使用循环数组管理序号和数据。

  • 设计每个记录的数据结构为：
struct MSG
{
  char* data;
  bool finished;
};

其中data为接收数据内容，finished为是否接收完成的标记。

  • 申请一个65（1G/16M+1）的MSG循环数组DataArray,记录起始结束位置headindex，tailindex，开始时headindex=tailindex=0。

  • 收到数据传输请求，若headindex！= tailindex+1，则可以接收，在DataArray的tailindex处记录信息，并返回tailindex，且tailindex++。

  • 每次接受完数据，更新相应的finished标志位，并检查headindex处数据是否finished，如果finished则写入磁盘，headindex++，继续检查下一个，直到条件不成立或headindex==tailindex。

  • 循环数组需对index做好管理，即index>64，则index置0。

    ​

输入字符串（只包含大小写字母和数字），将小写字母转换成大写字母

  • 最简单的方法，遍历字符串，如果是小写，则减32变成大写。
  • 因为要转换速度最快，更好的方法，空间换时间，建立一个查询表，初始化arr[数字]=数字，arr[小写]=大写，arr[大写]=大写。直接查表转换，不需进行大小写判断和减法操作。

给定url入口，要求找出网站上尽可能多的公司名和电话

图的遍历和规则模版的提取, 根据url的关联关系生成关联图，每个节点页面的规则设定

分布式cache系统映射算法

在分布式cache系统中,我们往往需要把内容分散到不同的机器上去,在访问的时候需要尽量地提高cache命中率。 假定MySQL 有一张超大表(检索词id 检索词)，为加快查询速度，前端N台机器可以作为cache，设计一种映射算法，将不同的记录缓存到不同的机器上。 要求:

  • 内容能够均衡地分布到多个机器中；
  • 访问的时候尽量提高cache命中率；
  • 在机器故障和上下线机器的时候尽量减少cache失效的比例；

无固定标准答案，一些参考答案：

  • 基本取模算法 + 取模算法的不足

    通俗的硬hash映射算法，扩展性不足，机器故障存在大面积迁移、失效

  • 一致性hash算法 + 详细描述

    Consistent hash 算法，高扩展性等

  • 其他映射算法

    比如直接分区段、视情况进行分裂等策略

对于一个有序（升序排列）的数组a，查找所有比i（i不在a中）大的数，请写出关键代码

public class FindGreater
{
  public static void main(String[] args) {
    int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int i = 18;
    
    int start = 0;
    int end = a.length - 1;
    
    int result = 0;
    
    while(start < end) {
      int base = (start + end) / 2;
      if(a[base]>i && a[base-1] <=i) {
        result = base;
        break;
      }else if(a[base] > i) {
        end = base;
      } else {
        start = base;
      }
      System.out.println("find time increace");
    
    }
    
    System.out.println("the value from " + a[result]);
  }
}

给定一个文件，包含1亿个ip，每个ip一行，要求统计出现次数最多的ip地址，100M内存

  • 将文本的ip转化成整数ip可存入100M内存
  • ip和整数互转的算法，移位操作细节

选择合适的排序算法，一般用堆排序，可以问一下堆排序的细节

概率问题

20个篮球，20个红球，放在袋子里，每次拿出两个球，如果同色，放回一个篮球，如果异色，放回一个红球，问：最后剩一个红球的概率是多少？

红球总是偶数个，所以不可能剩一个红球，所以概率是0

将一个链表的奇数项和偶数项调换

struct *linkList trans(linkList *l)
{
    linkList i = l->next;
    linkList j = i->next;
    while (i && j) {
        linkList k = j->next;
        j->next = i;
        i->next = k;
        i = k;
        j = k->next;
    }
    return l;
}

一台电脑配置无限好，可以同时打开多少个网页

65535-1000 = 64535（端口数）

ip地址能被伪造吗？

http头部中的IP地址可以被篡改，但是只能修改X_FORWARDED_FOR，真实ip地址（REMOTE_ADDR）很难修改（除非是路由器去修改），因为真实ip是底层会话ip地址，而且因为TCP 3次握手的存在，连接无法建立，伪造的意义不大，至于UDP的话，一般是内网才使用UDP通信。

上一篇 编程问题总结-C

下一篇 编程问题总结-MySQL

微信公众号：时空波隐者
文章目录