42. 写一个函数找出一个整数数组中，第二大的数 （microsoft）
答案：
const int MINNUMBER = -32767 ;
int find_sec_max( int data[] , int count)
{
int maxnumber = data[0] ;
int sec_max = MINNUMBER ;
for ( int i = 1 ; i < count ; i++)
{
if ( data > maxnumber )
{
sec_max = maxnumber ;
maxnumber = data ;
}
else
{
if ( data > sec_max )
sec_max = data ;
}
}
return sec_max ;
}
复制代码
43. 写一个在一个字符串（n）中寻找一个子串（m）第一个位置的函数。
KMP算法效率最好，时间复杂度是Ｏ（n+m）。
44. 多重继承的内存分配问题：比如有class A ： public class B， public class C {}那么A的内存结构大致是怎么样的？
这个是compiler-dependent的， 不同的实现其细节可能不同。
如果不考虑有虚函数、虚继承的话就相当简单；否则的话，相当复杂。
45. 如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）
struct node { char val； node* next;}
bool check(const node* head） {} //return false ： 无环；true： 有环
一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：
bool check(const node* head)
{
if(head==NULL) return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}