电话面试.txt

google的面试题

自我介绍
项目经历介绍
struct和class的区别
linux下的一些基本命令
引用和指针的区别，用法
单向链表的删除操作，已知head,p(指向被删除元素)，
要求复杂度为O(1)
Google Destop Search的一些技术

有100阶楼梯，一个人从底往上爬，每次爬1阶或2阶，请编个算法说明一共多少
种走法？


1、对现在的Stack（栈）数据结构进行改进，加一个min()功能，使之能在常数，即O(1)，时间内给出栈中的最小值。可对push()和pop()函数进行修改，但要求其时间复杂度都只能是O(1)。
2、用C/C++编程如何确定所在的计算机上栈的增长方式（是从上往下，还是从下往上）。
3、你要如何实现类似Google的拼写检查（即纠正用户输入关键字中的错误单词）？
还有如果进入Google，让你自由地选择一个课题，你会做什么方面的？




单链表 O(1) 复杂度内节点删除 
ZZ

Google电面有道题目，单链表知道head，知道节点p，要求在常数时间即O(1)内

把p删除。
O(1) means no search

算法：
if (p->next != null)
{
    p->value = p->next->value;
    p->next = p->next->next;
    free(p->next);
    //no search, ok!
}
else
{
    //the regular way
}