找工过程中碰到的笔试面试题整理（4）

继续我的找工笔试面试题整理。

1.加法实现n*n，要求时间复杂度O(logN)

要求不能用乘法，不考虑溢出问题，n为正整数。这个是面试的时候问到的，我没有想到较好的解决方案。只想到下面方法，思路就是每次加1倍，最后再判断不足一倍的部分。不知是否合乎要求。有人有好方法的不妨回复一下。:)

代码

int mult_by_add(int n)
{
int sum=n;
int totaladd =1;
while((totaladd+totaladd)<=n)
{
sum = sum+sum;
totaladd = totaladd+totaladd;
}
if(totaladd==n)
return sum;
int maxadd = totaladd>>1;
int maxsum = sum>>1;
while(totaladd<n)
{
while(n-totaladd<maxadd)
{
maxadd = maxadd>>1;
maxsum = maxsum>>1;
}
sum+=maxsum;
totaladd += maxadd;
maxadd = maxadd>>1;
maxsum = maxsum>>1;
}
assert(totaladd==n);
return sum;
}

2.实现strstr函数

常见的字符串处理函数实现，面试笔试经常考察的。类似的还有很多，大家多注意一下C库函数的字符串处理函数的实现。

代码

int mystrstr(constchar* source,constchar* dest)
{
int i,j;
i=j=0;
while(source[i]!='\0'&&dest[j]!='\0')
{
if(source[i]==dest[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(dest[j]=='\0')
return i-j;
return-1;
}

3.用C语言实现链栈

只要求实现基本功能，当时面华为遇到的程序题，没有当着面试官写出来，回来以后自己总结了下。链表，链栈都是常见题。注意考虑到，当栈为空的时候pop的处理

代码

typedef struct TNode
{
int data;
struct Node* next;
}StackNode;
typedef struct TStack
{
StackNode* top;
}LinkStack;
void init(LinkStack& lstack)
{
lstack.top = NULL;
}
int Pop(LinkStack& lstack)
{
if(lstack.top==NULL)
{
return-1;
}
StackNode* node = lstack.top;
lstack.top = lstack.top->next;
int data = node->data;
delete node;
return data;
}
void Push(LinkStack& lstack,int datavalue)
{
StackNode* pnode =new StackNode;
pnode->data = datavalue;
pnode->next = lstack.top;
lstack.top = pnode;
}
void DestroyStack(LinkStack& lstack)
{
while(lstack.top!=NULL)
{
Pop(lstack);
}
}

使用如下：

int main( )
{
LinkStack mystack;
init(mystack);
Push(mystack,12);
Push(mystack,10);
Pop(mystack);
Pop(mystack);
Push(mystack,9);
Pop(mystack);
DestroyStack(mystack);
return0;
}

4.同一继承层次多个基类的指针转换代码示例

这个考察对C++对象内存布局的了解，以下几个示例需要详细了解了内存对象布局才能得到答案。

代码

class A
{
public:
virtualvoid foo(double)=0;
};
class B
{
public:
virtualvoid foo(int)=0;
};
class C:public A,public B
{
public:
void foo(double)
{
printf("double,");
}
void foo(int)
{
printf("int,");
}
};
int main()
{
C* pc =new C;
void* pvoid = pc;
((B*)(A*)pc)->foo(0); //由于首先转成A类指针，此时再转B，将会破坏B的虚表，只保留A的虚表，因此调用A的虚函数
((C*)(B*)(A*)pc)->foo(0);//由于(B*)(A*)已经将B的虚表破坏，再转成C也还是只有A的虚表，因此调用A的虚函数
((A*)(B*)pc)->foo(0); //同上，A的虚表被破坏，只有B的
((B*)pvoid)->foo(0); //由于不知道pvoid的具体类型，因此会将处于内存布局前面的虚表指针（A的虚表指针）拷贝出来，再销毁内存布局前面的虚表指针，再将拷贝出来的虚表指针覆盖要转换的B类的虚表指针，此时B的虚表指针被A的虚表指针覆盖了。
((A*)pvoid)->foo(0); //同上，先拷贝内存布局前面的虚表指针（A）,再销毁内存布局前面的指针，再将拷贝出来的虚表指针覆盖要转换的目标类A的虚表指针。
((B*)(C*)pvoid)->foo(0);
delete pc;
return0;
}

上述示例如有错误请回复告知，3Q。:)

笔试面试题基本就整理到此了，还有很多基本的知识都是常见的，我这里就不整理了。希望能给面试笔试的同学带来帮助。