前言
众所周知，Google的面试是出了名的，为此MIT还专门针对它开了一门课程！
链接：http://courses.csail.mit.edu/iap/interview/index.php
看了一下该课程提供的材料，相当的基础，估计上完这课离真正地Hacking a Google interview还是有一定的距离的。这里摘选Handout里的一些内容，希望起到抛砖引玉的作用。
Handout 1
经典问题1：
8枚硬币，其中一枚比较重。你只有一台老式天平能比较两物轻重。请问至少需要称几次才 能找到那枚比较重的硬币？
解答：
很简单的思维题目，不过容易陷入这样的陷阱：每次对半称，第一次两边各四枚，找到较重 的一堆；第二次两边各两枚，找到较重的一堆；第三次两边各一枚，找到较重的那一枚。 这样做并不是最优的。最优的解法，最少只要两次就可以找到较重的那枚硬币： 拿出6枚，天平一边各放3枚。如果天平平衡，则较重的那枚在另外2枚中，再称一次即可。 否则，在较重的3枚中拿出2枚，天平一边各一枚，如果较重的那一枚在这2枚中， 则可以直接从天平结果中得出；如果天平平衡，则没称的那一枚是较重的。
面试中的tips
当面试官问你问题时，要保持与他的交流。告诉他你对这个问题的见解与思路， 你打算怎么来解答这个题目。通常情况下，当你被问题卡住时，面试官会给出相应的提示。
面试中如果要你写代码，一般是写在白板或是纸上的。因此要提前练习在纸上写代码的能力。
面试中的Do’s和Don’t’s:
Do’s:
- 如果对于题目不理解或是题目中有不明晰的地方，要询问面试官
- 让面试官知道你在想什么，你的思路是什么
- 对于一个问题，尝试给出多种解决方案
- 试探性地从面试官那得到信息(比如用这道题是不是用这个数据结构或是算法)
- 如果被问题卡住了，不必慌张，礼貌地向面试官询问提示
Don’t’s:
- 不要放弃
- 思考问题的时候不要一言不发。要向面试官传达你的思维方式，解题思路是什么
- 如果你已经知道答案了，不要脱口而出。至少要有一个思考的过程
大O标记
没什么可讲的。不过里面出现了一小段程序，检测一个int数组中是否存在相同的数。 代码如下：
boolean hasDuplicate(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (array[i] == array[j] && i != j) {
return true;
}
}
}
return false;
}
这段代码的时间复杂度是O(n^2 )。不过，显然还有更好的解决方案。 用另一个数组A来表示array中数字的出现。如果array中有数字x，则令A[x]=true。 遍历一遍array数组，当其中某个数y对应的A[y]为true，说明这个数在前面已经出现过了。 即可判断该数组中存在相同的数，返回true。遍历完如果没有返回true,则返回false。
在有序的数组中查找一个数。二分查找，没什么讲的。
并行
线程与进行：
一台计算机常常同时做许多事情，比如查看新邮件，保存Word文档，加载网页。 每个程序是一个独立的进程，每个进程有一个或多个线程。如果一个进程有多个线程， 那么这些线程看起来就是在同步运行。比如，一个Email客户端可能有一个线程用于检查新 邮件，同时有一个线程用于GUI使之能显示一个按钮是否被点击了。事实上， 在任何一个时刻，都只有一个线程在运行。我们之所以看到好几个线程同时在运行是因为处 理器在线程之间的切换非常快速。
同一进程中的多个线程共享内存空间。与此相反，不同进程拥有不同的内存空间， 且不同进程之间只能靠特殊的机制进行通信。处理器为每个线程加载并保存一组独立的寄存 器。
记住：每个进程拥有一个或多个线程，并且处理器在这些线程之间切换。
互斥锁(Mutexes)与信号量(Semaphores):
互斥锁就像一把锁。互斥锁用于并行编程中来保证在同一时间只有一个线程能访问共享资源。 比如，有一个线程正在修改一个数组。当它进行到一半时，处理器切换到其他线程， 如果我们没有使用互斥锁，新的线程也可能尝试去修改数组，而这可能并不是我们所希望看 到的。
为了防止这种事情发生，我们可以使用互斥锁。从概念上来讲，互斥锁是一个从1开始计数 的整数。一个线程在任何时候需要修改一个数组，它就“锁”住这个互斥锁。 这将导致s
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2012/11/26/hacking-a-google-interview/
