谷歌中国面试题

谷歌中国的面试题目与洞察：

题目一：判断一个整数是否为2的幂。

C语言表达式可以这样写：`(n&(n-1))==0`。这个表达式通过位运算判断给定的整数是否满足一个数如果是二的幂，那么它的二进制表示中只有一位是1的特性。如果满足条件，返回真，否则返回假。

题目二：找出重复和缺失的数。对于这两个问题，我们可以使用异或运算来解决。对于不超过N-1和N+1的正整数数组，分别对所有数进行异或操作，重复的数字会抵消掉，留下的结果就是缺失或重复的数。这种方法的时间复杂度为O(N)。

题目三：统计一个32位整数二进制表示中的“1”的个数。可以使用一个简单的算法：保留每步中的进位信息，将数字与自身减一相比，得到的差值就是该数字二进制表示中“1”的个数。这种方法也是线性时间。

题目四：确定电线线头的对应关系。这个问题可以通过巧妙的思维解决。将电池与灯泡通过特定的电线连接起来，然后分别从不同的楼层的线头开始尝试连接，直到灯泡亮起。对应的电线关系就确定了。只需上下楼一次，就能找到对应关系。

题目五：字符串向左循环移动m位。这个问题可以通过两次反转解决。反转整个字符串，然后将前m个字符反转，其余字符反转。这样就可以得到移动m位后的结果。这种方法的时间复杂度为O(n)，附加空间为常数。

题目六：机器人相遇问题。两个机器人可以通过交替执行左移和右移操作来相遇。无论初始位置如何，只要两个机器人遵循相同的程序逻辑，总会相遇。程序应包含判断语句和循环语句，确保机器人能够持续移动直到相遇。

题目七：找出好的处理器。这个问题可以通过一个巧妙的策略解决。向任意两个处理器询问关于第三个处理器的状态，根据他们的回答来判断哪个是好的处理器。由于好的处理器总是说真话，而坏的处理器总是说谎，因此可以通过比较两个回答来判断哪个处理器是好的。只需n-2次询问就能找出好的处理器。

题目八：文章单词倒序。这个问题可以通过维护一个栈来解决。遍历文章的每个单词，将其压入栈中。当所有单词处理完后，栈顶就是最后一个单词，依次弹出栈内单词即可得到倒序的单词序列。这种方法的时间复杂度为线性，附加空间为常数。