第三十九期：找茬--心里圈的故事（活动答案和获奖名单已公布）

lsekfe

获奖名单
奖项	获奖名单	奖励	答案链接
一等奖	maqi5630	500测试积点	#4
二等奖	libingyu135	500测试积点	#9
三等奖	风华绝代	500测试积点	#10

一次谷歌面试趣事
很多年前我进入硅谷人才市场，当时是想找一份高级工程师的职位。如果你有一段时间没有面试过，根据经验，有个非常有用的提醒你应该接受，就是：你往往会在前几次面试中的什么地方犯一些错误。简单而言就是，不要
首先去你梦想的公司里面试。面试中有多如牛毛的应该注意的问题，你可能全部忘记了，所以，先去几个不太重要的公司里面试，它们会在这些方面对你起教育(再教育)作用。
　　我第一家面试的公司叫做gofish.com，据我所知，gofish这家公司如今的情况跟我当时面试时完全的不同。我几乎能打保票的说，当时我在那遇到的那些人都已不再那工作了，这家公司的实际情况跟我们这个故事并不是
很相关。但在其中的面试却是十分相关的。对我进行技术性面试的人是一个叫做Guy的家伙。
　　Guy穿了一条皮裤子。众所周知，穿皮裤子的面试官通常是让人“格外”恐怖的。而Guy也没有任何让人失望的意思。他同样也是一个技术难题终结者。而且是一个穿皮裤子的技术难题终结者——真的，我做不到他那样。
　　我永远不会忘记他问我的一个问题。事实上，这个问题是非常的普通——在当时也是硅谷里标准的面试题。
　　问题是这样的：
　　假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法上讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？
　　比如，如果是下面两个字符串：
　　String 1: ABCDEFGHLMNOPQRS
　　String 2: DCGSRQPOM
　　答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：
　　String 1: ABCDEFGHLMNOPQRS
　　String 2: DCGSRQPOZ
　　答案是false，因为第二个字符串里的Z字母不在第一个字符串里。
　　当他问题这个问题时，不夸张的说，我几乎要脱扣而出。事实上，对这个问题我很有信心。(提示：我提供的答案对他来说显然是最糟糕的一种，从面试中他大量的各种细微表现中可以看出来)。
　　对于这种操作一种幼稚的做法是轮询第二个字符串里的每个字母，看它是否同在第一个字符串里。从算法上讲，这需要O(n*m)次操作，其中n是string1的长度，m是string2的长度。就拿上面的例子来说，最坏的情况下将
会有16*8 = 128次操作。
　　一个稍微好一点的方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m)+ O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。同样拿上面的字串做例
子，将会需要16*4 + 8*3 = 88加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长，你会发现这个算法的效果会越来越好)
　　最终，我告诉了他一个最佳的算法，只需要O(n+m)次操作。方法就是，对第一个字串进行轮询，把其中的每个字母都放入一个Hashtable里(成本是O(n)或16次操作)。然后轮询第二个字串，在Hashtable里查询每个字母，
看能否找到。如果找不到，说明没有匹配成功。这将消耗掉8次操作——这样两项操作加起来一共只有24次。不错吧，比前面两种方案都要好。
　　Guy没有被打动。他把他的皮裤子弄的沙沙响作为回应。”还有没有更好的？“他问道。
　　我的天？这个家伙究竟想要什么？我看看白板，然后转向他。”没有了，O(n+m)是你能得到的最好的结果了——我是说，你至少要对每个字母至少访问一次才能完成这项操作——而这个方案是刚好是对每个字母只访问一
次“。我越想越确信我是对的。

活动内容：

         每个周一、周五上午11点整，小编会在灌水版块中发布一篇关于心里圈故事的帖子提供给大家阅读。阅读后，需要大家找出文章中的错别字，并且写上一句读后感（不少于10个文字）。

活动时间：

         每周二次

活动规则：

         阅读心里圈的故事，找出文章中的错别字和写上自己的读后感（必须原创），通过论坛跟帖的形式进行回复。Ps:如发现抄袭原文评论将视为无效。

获奖标准：

        找出文章中的所有错别字，并且读后感写的最好的三位会员能获得500测试积点。

正确答案：脱口而出=脱扣而出

清晨一缕阳光

错别字：
1."脱扣而出"  脱口而出。
2.“轮询”  轮循。

清晨一缕阳光

错别字：
1."脱扣而出"  脱口而出。
2.“轮询”  轮循。

maqi5630

打保票 应该为 打包票   脱扣  应为  脱口，
读后感：首先文章应该是翻译过来的，读起来比较拗口。本人技术菜鸟所以，上面面试题我也看不懂，我也看过苹果公司的面试题，我感觉到一点就是,通常国外的这些大IT公司技术面试的面试一般都不是什么具体技术题目，更多是一些智力题，创意提，和类似文章中的算法题等等，可见一般国外IT公司更注重个人的思维灵活，敏捷，创新。相比国内更多的注重你的实际技术能力！好了不能再吹了，我也本身就是菜鸟一个不能再高谈阔论了！

清晨一缕阳光

面试中自信非常重要，三思而后行。

清晨一缕阳光

面试中自信非常重要，三思而后行。

jingzizx

脱扣而出---脱口而出

确实是这样,工作太久,需要面试去发现自己的不足,这样才能不断地进步.

51Testing_叮当

不再 -> 不在
脱扣而出 -> 脱口而出

这个故事之所以吸引人，在有意思的面试题分析与解答之外，还有一个戛然而止没有结尾的结尾

libingyu135

打保票----打包票
已不再那工作-------已不在那工作
脱扣而出------脱口而出

说实话，读完第一遍以为没写完。又多读了一次才明白作者的意图。
细细一扣，小小的一个故事却说出了很多道理：
1.最普通的问题，最常用的方法并不一定是最佳的方法；
2.要善于思考，对于突如其来的问题不能急于给出答案，多思考，静下心来，想周全些；
3.对于我们认为重要的事情，需要更多的准备和积累，因为机会只有一次。
4.要对自己有自信，打消别人的不断质疑的最好方法就是端着自信的姿态用自己的理论去一步一步说服他；
5.对气势强大的对手，我们更需要镇定自若。
面试不难也不易，面试官问的问题大同小异，过与不过就在于你的答案是否能抓住面试官看中的重点；这既是一场智商的战争，也是一场情商的较量；从毕业以来，我面试的次数屈指可数，不海投不乱投，每次去之前坐在公交车上我就会猜想面试官会问我什么问题，然后我会怎样回答，每一次的准备都会让我更有信心和底气，所以也鲜有失手。我想，一切都源自于充分的准备吧，那句话不是说“机会都是留给有准备的人的”！

风华绝代

最明显的错误：“脱扣而出”->“脱口而出”。
其他：
“当他问题这个问题时”->“当他问到这个问题时”；
“把他的皮裤子弄的沙沙响”->“把他的皮裤子弄得沙沙响”。

读后感：
通过这个故事告诉求职者不要先去心仪的公司面试，而应该先去不太重要的公司接受＂再教育＂。

zhuruize

当时我在那遇到的那些人都已不再那工作了
中的“再”应该是“在”

我几乎要脱扣而出
中的“扣”应该是“口”

想知道，为啥作者不问一下Guy会怎么做这个题呢，很想看看guy的答案