谷歌中国面试题.docx

文档介绍：谷歌中国面试题
1、给出一行C语言表达式，判断给定的整数是否是一个2的哥。
2、一个大小为N的数组，所有数都是不超过 N-1的正整数。
用O（N）的时间找出重复的那个数（假设只有一个）。一个大小为N的 数组，所有数都是不超过 N+1的正整数。用O（N）的时间找出没有 出现过的那个数（假设只有一个）。
3、如何快速找出一个32位整数的二进制表达里有多少个 1 ? 用关于1的个数的线性时间？
4、你在一幢100层大楼下，有21根电线线头标有数字1..21。
这些电线一直延伸到大楼楼顶，楼顶的线头处标有字母 A..U。你不
知道下面的数字和上面的字母的对应关系。 你有一个电池，一个灯泡， 和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关 系？
5、用线性时间和常数附加空间将一个长度为 n的字符串向左循
环移动m位（例如，abcdefg 移动3位就变成了 defgabc ）。
6、两个机器人，初始时位于数轴上的不同位置。给这两个机器
人输入一段相同的程序，使得这两个机器人保证可以相遇。 程序只能 包含左移n个单位、右移n个单位，条件判断语句If,循环语句 while ,以及两个返回Boolean值的函数在自己的起点处和在对 方的起点处。你不能使用其它的变量和计数器。
7、你在一个飞船上，飞船上的计算机有 n个处理器。突然，飞 船受到外星激光武器的攻击，一些处理器被损坏了。你知道有超过一 半的处理器仍然是好的。你可以向一个处理器询问另一个处理器是好 的还是坏的。一个好的处理器总是说真话，一个坏的处理器总是说假 话。用n-2次询问找出一个好的处理器。
8、用线性时间和常数附加空间将一篇文章的单词 （不是字符）倒
序。