谷歌试题

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

struct 和 class 的区别

见 http://blog.csdn.net/wplxb/archive/2007/06/16/1654129.aspx

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

引用和指针的区别，用法

见 http://blog.csdn.net/wplxb/archive/2006/10/14/1334781.aspx

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

单向链表的删除操作，已知 head, p(指向被删除元素)，要求复杂度为 O(1) (题目似有误)

常数时间删除结点肯定不行，不过可以用假删除，就是把要删除节点的值用要删除节点的下一个节点值覆盖，然后删除下一个节点 (要求该节点的下一个节点不能是空，也就是说，这种方法对删除最后一个节点是行不通的)。

见 http://blog.csdn.net/wplxb/archive/2007/07/02/1675718.aspx

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

有 100 阶楼梯，一个人从底往上爬，每次爬 1 阶或 2 阶，请编个算法说明一共多少种走法？后面的问题更有一些深度：这个算法(他会给出一个正确的算法思路)有什么效率上的问题，如何解决；如果这个算法经常要被调用，如何设法使效率提高？

F(n) = F(n-1) + F(n-2), n = 阶数
F(0) = F(1) = 1，这个是 Fibonacci 数列，最直观的是递归，复杂度是指数；然后是线性的算法；接下来有一个对数的算法。如果是经常被调用，可以修改线性的算法，设一个 cache F[0...n]，在算之前，先查一下这个 cache，如果没有，就重新算一下。

参考：Fibonacci 数列的三种算法 (http://enihcam.iblog.com/post/5251/124345)

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

对栈数据结构进行改进，加一个 min() 功能，使之能在常数 (即 O(1)) 时间内给出栈中的最小值。可对 push() 和 pop() 函数进行修改，但要求其时间复杂度都只能是 O(1)。

思路：
1. 设置一个主栈，一个辅栈，辅栈用于存储当前栈中最小值元素。
push:
如果主栈为空，push 进主栈和辅栈; 如果主栈非空，push 进主栈，然后把这个数跟辅栈的栈顶元素比较，把较小值 push 进辅栈；
pop:
辅栈 pop 一次，主栈 pop 一次并返回；
min:
返回辅栈栈顶元素即可。
2. 在栈元素中扩展出最小值域，栈顶元素的最小值域中保持当前栈中的最小值。
与 1 基本一样，不用辅助栈，但要修改栈内元素结构。
3. 设置一个主栈，一个辅栈，辅栈用于存储主栈中当前最小值元素及其到主栈底的距离。
push:
push 进主栈。当主栈新栈顶元素比辅栈的栈顶元素更小时，把主栈的新栈顶数据和主栈当前栈大小压入辅栈。
pop:
如果主栈 pop 后，其栈大小比辅栈栈顶元素的距离小，则辅栈的栈顶也弹出。
min:
返回辅栈的栈顶元素即可。
基本思想跟 1 一样，但在主栈中重复元素较多，或者排好序的数据按升序入栈的情况下，可以节省空间。但如果栈中没有重复元素，且排好序的数据按降序入栈，则需要更多空间。

注：如果要求最大值，同理可得。


参考：
1. http://topic.csdn.net/t/20051121/13/4407616.html
2. http://blog.csdn.net/minus8cool/archive/2006/03/14/624375.aspx

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

用 C/C++ 编程如何确定所在的计算机上栈的增长方式（是从高到低，还是从低到高）。

int x;
int y;
if (&x < &y)
{
cout << "from low to high";
}
else
{
cout << "from high to low";
}

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

你要如何实现类似 Google 的拼写检查 （即纠正用户输入关键字中的错误单词)？

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

Google Destop Search 的一些技术

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

项目经历；你觉得哪个项目最富有挑战性？你怎么解决那些问题的？

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

如果进入 Google，让你自由地选择一个课题，你会做什么方面的？

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