如何看待中国学生为了进 Google、微软等外企疯狂地刷题？北美学生想进这些名企也要刷题吗？

我之前没怎么刷题，于是第一个电面就懵逼了：

面试官：写个开根号的程序吧。

我：好的，可以用牛顿法（Newton–Raphson method），我开始写啦？

面试官：

我：。。。

面试官：那是神马东东？没听过！

我：嗯？？！！就是一种数学上的逼近方法blablabla，我写出来你就明白了！

我：（飞速写完，一边写一边解释），搞定啦！我来分析复杂度吧！

面试官：

我：。。。

面试官：嗯。。。这个方法不对吧。。。

我：牛爵爷还能错？我给你证明一下blablabla。。。

面试官：嗯。。。我还是不相信是对的。。。怎么看都不对啊。。。

我：好吧，我给你跑几个例子吧，（测了几个例子都是对的）。

面试官：嗯。。。好吧。。。算你是对的。。。但是感觉很慢的样子。。。

我：怎么会？超快的！O(log n)，blablabla

面试官：嗯。。。好吧。。。算你对了

。。。

。。。

。。。

（面试官沉默了很久）

。。。

。。。

。。。

面试官：（还有五分钟结束时）你听过二分查找吗（binary search）？之前所有面试者都用的二分查找啊？

。。。

。。。

。。。

我的内心OS： 原来。。。二分查找。。。才是标准答案吗？？！！

虽然非常匪夷所思，但这确实是我参加某大公司第一轮电面的情况！！！！我就不黑是哪家了。

可能是这个面试官没做任何准备；可能他还没睡醒状态不好；可能他很长时间没用过牛顿法，听到Newton–Raphson method就懵逼了。不管怎样，没刷过题很多时候真的猜不出“那个面试官心里想的标准答案”是神马！！！！

这时他问你问题，你以为他在考你，实际上他可能只是在引导你用他心目中的标准方法。

所以。。。在所有面试者都刷题的情况下。。。你也必须刷题。。。不然。。。即使你能做对题目。。。也可能会因为和其他人的解法不同而实力懵逼。。。

而且要是碰上老印完全听不懂的话，如果刷过题，知道大概的题意，应该会帮助很大吧！

毕竟。。。你不能把找工作这种大事，寄希望于遇到“有耐心，英文标准，还善于引导”的面试官上！

以上，就是我开始刷题的经过。。。

=========华丽丽的分割线==========

1. 我写这个段子想表达的，不是“我知道牛顿法我好牛逼呀”（这个真的超级基础），而是“现在Google，Facebook，微软的面试者都刷题，你不刷题可能会实力懵逼”。毕竟面试官都有自己日常的工作，面试算是额外的任务，并不是每个人都很上心。

有很多评论说需要impress面试官，我觉得没必要。常规方法把题都做完，一遍bug-free就OK了！而且常规方法也比较容易解释，毕竟我们口语也是有一定障碍的。

2. 既然很多评论区大神对求根号的算法很感兴趣，我就在这儿简单讨论一下：

1) 牛顿法每次迭代的误差都会至少小一半，所以复杂度最多是O(log(n))。在数学上，牛顿法是quadratic convergence的，求高精度开根号是灰常常用的方法。

2) 有没有O(1)的算法？当然有，最著名的就是用Magic Number（0x5f3759df）算出 (1/根号 n)，然后再乘以n，但是这种算法做个游戏还行，科学计算还是歇歇吧。而且，实在是太难理解了！

3) 这个链接比较了15种快速开根号的方法

，除了使用了特殊汇编指令、以及Magic Number的方法外，基本都是牛顿法的变种。而且几乎所有O(1)的算法，都会通过一步或两步牛顿法来提高精度。

4) 经评论提醒，Magic Number也是牛顿法的变种。不过我记得这个Magic Number和数学估算出的数还是有偏差，但是magic的地方就在于。。。在32位机器上。。。它的效果很多情况下都比数学估算的数更好！！！！（也可能是我记错了，反正这个数很神奇！！！！）

5) 二分查找对于较小的N可能会比牛顿法快，但整体而言肯定是没牛顿法好，所以我面试的时候压根就木有提起。

3. 对于那个不知道牛顿法的面试官，你说Magic Number或是上面链接里任意一个神奇方法，你都肯定会跪得很惨！！！！还是刷刷题，看看大家的常用解法是什么比较靠谱！！！！

4.另外请祖国人民放心，面试肯定是过了的。

以上，