一次谷歌面试趣事

google logo

很多年前我进入硅谷人才市场,当时是想找一份高级工程师的职位。如果你有一段时间没有面试过,根据经验,有个非常有用的提醒你应该接受,就是:你往往会在前几次面试中的什么地方犯一些错误。简单而言就是,不要首先去你梦想的公司里面试。面试中有多如牛毛的应该注意的问题,你可能全部忘记了,所以,先去几个不太重要的公司里面试,它们会在这些方面对你起教育(再教育)作用。

我第一家面试的公司叫做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)是你能得到的最好的结果了 —— 我是说,你至少要对每个字母至少访问一次才能完成这项操作 —— 而这个方案是刚好是对每个字母只访问一次“。我越想越确信我是对的。

他走到白板前,”如果这样呢 —— 假设我们有一个一定个数的字母组成字串 —— 我给每个字母分配一个素数,从2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历第一个字串,把每个字母代表的素数相乘。你最终会得到一个很大的整数,对吧?然后 —— 轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。这样不行吗?“

每当这个时候 —— 当某个人的奇思异想超出了你的思维模式时,你真的需要一段时间来跟上他的思路。现在他站在那里,他的皮裤子并没有帮助我理解他。

现在我想告诉你 —— Guy的方案(不消说,我并不认为Guy是第一个想出这招的人)在算法上并不能说就比我的好。而且在实际操作中,你很可能仍会使用我的方案,因为它更通用,无需跟麻烦的大型数字打交道。但从”巧妙水平“上讲,Guy提供的是一种更、更、更有趣的方案。

我没有得到这份职位。也许是因为我拒绝了他们提供给我的一些讨厌的工作内容和其它一些东西,但这都无所谓了。我还有更大更好的目标呢。

接着,我应聘了become.com。在跟CTO的电话面试中,他给我布置了一道”编程作业“。这个作业有点荒唐 —— 现在回想起来,大概用了我3天的时间去完成。我得到了面试,得到了那份工作 —— 但对于我来说,最大的收获是这道编程作业强迫我去钻研并有所获。我需要去开发一个网页爬虫,一个拼写检查/纠正器,还有一些其它的功能。不错的东西。然而,最终,我拒绝了这份工作。

终于,我来到了Google面试。我曾说过Google的面试过程跟外面宣传的很一致。冗长 —— 严格,但诚实的说,相当的公平。他们在各种面试过程中尽最大的努力去了解你、你的能力。并不是说他们在对你做科学研究,但我确信他们是努力这样做。

我在Google的第四场面试是一个女工程师,老实话,是一场很无聊的面试。在前面几场面试中我表现的很好,感觉到我的机会非常的大。我相信如果不做出什么荒唐事情来,十拿九稳我能得到这份工作。

她问了我一些关于排序或设计方面的非常简单的问题,我记不清了。但就在45分钟的面试快要结束时,她对我说”我还有一个问题。假设你有一个一定长度的由字母组成的字符串。你还有另外一个,短些。你如何才能知道所有的在较短的字符串里的字母在长字符串里也有?“

哇塞。Guy附身了。

现在,我完全可以马上结束这场面试。我可以对她说“哈哈,几个星期前我就知道答案啦!”,这是事实。但就是在几个星期前被问到这个问题时 —— 我给出的也是正确的答案。这是我本来就知道答案的问题。看起来就好像是Guy为我的这次面试温习过功课一样。而且,可恶,人们通常是通过上网来搜集面试问题 —— 而我,我可以毫不客气的说,对于这些问题,我不需要任何“作弊”。我自己知道这些答案!

现在你们可能认为——就在她问出了问题之后,在我准备开始说出在脑海里构思完成的最后的演讲之前——你们可能会想,我应该是,当然该,从情理上讲,镇定的回答出这个问题,并且获得赞赏。可糟糕的是,事实并不是这样。打个比喻,就像是她问出来问题后,我在闹子里立即举起了手,并大叫着“我!嗨!嗨!我知道!让我来回答吧!”我的大脑试图夺走我对嘴巴的控制权(这事经常发生),幸亏我坚强的毅力让我镇定下来。

于是我开始回答。平静的。带着不可思议的沉着和优雅。带着一种故意表现出来的 —— 带着一种,我认为,只有那种完全的渊博到对古今中外、不分巨细的知识都精通的人才能表现出来的自信。

我轻描淡写的说出来那种很幼稚的方案,就好象是这种方案毫无价值。我提到了给它们排序,就好像是在给早期的《星际迷航》中的一个场景中的人物穿上红T恤似的。最后,平淡的,就好像是我决定了所有事情的好坏、算法上的效率,我说出了O(n+m)一次性方案。

我要告诉你——尽管我表明上的平静——这整个过程我却在做激烈的挣扎,内心里我在对自己尖着——“你个笨蛋,赶紧告诉她素数方案!”

当我完成了对一次性算法的解释后,她完全不出意外的认可的点了下头,并开始在笔记本上记录。这个问题她以前也许问过了一百次,我想大部分的人都能回答上来。她也许写的是“回答正确。无聊的面试。正确的回答了无聊的字符串问题。没有惊喜。无聊的家伙,但可以留下。”

我等了一会。我让这种焦灼的状态持续的尽可能的长。我可以发誓的说,如果再耽搁一分钟,我一定会憋出脑血栓、脱口说出关于素数的未解之谜。

我打破了沉默。“你知道吗,还有另外一个,可能是更聪明的算法。”

她二目空空的抬头看了一眼,仅在瞬间闪现过一丝希望。

“假设我们有一定长度的字符串。我们可以给每个字母分配一个素数,从2开始。然后我们把大字串中的每个字母代表的素数相乘得出一个数,用小字串中的每个字母代表的素数去除它。如果除的过程中没有产生余数,则小字串是大字串的一个子集。”

在此时,我猜,她看起来就像是Guy当时把相同的话说给我听时我表现出来的样子。而我演讲时泰然自若的表情没了,眼睛瞪大,说话时稍微带出来一些唾沫星子。

一会儿后,她不得不说了,“可是…等一下,有可能…是的,可以这样!可是如何…如果…噢,噢,可行!简洁!”

我得意洋洋的吸了一口气。我在我的面试记录里写下了“她给了我一个‘简洁’的评语!”在她提出这个问题之前我就确信能得到这份工作,现在我更加确信了。还有一点我十分确信的是,我(更准确的说是Guy)给了她今天的好心情。

我在Google干了3年,生活的十分愉快。我在2008年辞职去到一个小公司里做CTO,之后又开办了一个自己的公司。大概是一年前,我偶然的在一个创业论坛会上遇到了Guy,他记不得我了,当我向他细述这段往事时,他对他那条皮裤子大笑不已。

话说回来,如果这个故事里有什么教育意义的话——永远不要冒失的首先去应聘你梦想的公司,应先去应聘那些你不看好的职位。你除了能从这些面试中获得经验外,你指不定能遇到某个能为你的更重要的面试铺路的人呢。事实上,这个经验在你生活中的很多其它事情上也适应。

说正经的,如果你有机会想找一个解决问题的高手——雇佣Guy比谁都强。那个家伙很厉害。

(在这些陈年旧账里发现的一点技术瑕疵:字母有可能重复而字符串可能会很长,所以必须要有统计。用那个最幼稚的解决方案时,当在大字符串里找到一个字符后就把它删掉,当这样仍然是 O(n*m)次。在Hashtable里我们会有一个key->value的计数。Guy的方案在这种情况下仍然好用。)

修改:11/30/10 —— 本文中提到的Guy看到了这篇文章,并在评论中做了澄清。值得一读。

[英文原文:A Google Interviewing Story ]
分享这篇文章:

111 Responses to 一次谷歌面试趣事

  1. zoujia says:

    呵呵,真有意思,可以借鉴一下\(^o^)/~

  2. Ella says:

    谨记,不要首先去梦想的公司里面试。

  3. Pea-brained Turtle says:

    永远不要冒失的首先去应聘你梦想的公司,应先去应聘那些你不看好的职位。你除了能从这些面试中获得经验外,你指不定能遇到某个能为你的更重要的面试铺路的人呢。事实上,这个经验在你生活中的很多其它事情上也适应。

    学习了……谢谢!

  4. evan says:

    如果只有字母的话用26位的二进制数表示,
    A:1000…00, B:0100…00, …, Z:0000…01
    对字符串中的字符进行与操作

    • evan says:

      错了,是“按位或”不是“与”

      • left says:

        这种位图算法具体怎么实现呢?是长字符串和短字符串分别各个字符相与之后,再拿短字符串得到的结果跟长字符串得到的结果逐位对比么?这样好像也没多大改进,只不过相当于用了一个快速排序的方法。
        一种可行的方法是,将长字符串得到的结果α和短字符串得到的结果β再相与,得到结果γ,γ和β异或,短为长的子集则异或结果为全0,不为子集还能从异或结果上直接找出短字符串里有但是却不属于长字符串里的字母。

      • evan says:

        恩,算法上没什么区别,只是一种可能的实现,不会发生溢出

      • ivan says:

        这个方法不错呀,得到A和B两个子串的值,然后 A|B == A也就意味着包含

    • test says:

      你的算法需要用到26位的二进制,要么你要用数组,要么就要用到2的26次方减1那么大的数;而Guy的算法只需要用到100多的数,所以他的算法要好很多。

      • littledoo says:

        很遗憾你错了。evan的算法明显优雅简洁节省得多。
        2的26次方听起来多么不可思议,其实只是一个UINT型的数字。
        A=1,B=2,C=4,D=8…Z=33554432(2的25次方)

        但GUY的算法需要用到100以内所有的素数(25个)和101相乘,我们看看是是多少:
        2.328623643584974e+38

        先不讨论数字的大小,CPU在进行机器码运算时,数值的乘/除法和位运算所消耗的时间也不一个等级的。

    • 王敏 says:

      这是我的做法,看到你和我做法差不多就在这留言了。通过上面的test的留言说明他不懂基本的计算机位运算。
      我的做法:
      1 使用一个uint32 的数flag初始值为0
      2 先扫描短的字符串, 每个字符, 使用flag |= (1<<(*p1 – 'a'));
      3 然后扫描长的字符串,每个字符, 使用flag ^= (1<<(*p2 – 'a')); 并判断flag是否为0,为0函数返回true
      函数最后面返回false

      当然还有更快的做法, 就是建一个256*256的表s,s['a]['a‘]存的是1,s['a]['b’]存的是3, 其他同理,速度可以快一点点

      • 王敏 says:

        C语言函数如下:

        int IsContain(const char * longStr, const char * shortStr)
        {
        unsigned int flag = 0;

        while (*shortStr != ”) // 同*shortStr
        {
        flag |= (1<<(*shortStr – 'A'));
        ++shortStr;
        }

        while (*longStr != '') // 同*longStr
        {
        flag ^= (1<<(*longStr – 'A'));
        if (0 == flag) return 1;
        ++longStr;
        }

        return 0;
        }

      • 王敏 says:

        上面错了, 应该是:
        int IsContain(const char * longStr, const char * shortStr)
        {
        const unsigned int allFlag = 3fff;
        unsigned int flag = 0;

        while (*shortStr != ”) // 同*shortStr
        {
        flag |= (1<<(*shortStr – 'A'));
        ++shortStr;
        }

        while (*longStr != '') // 同*longStr
        {
        flag &= allFlag ^(1<<(*longStr – 'A'));
        if (0 == flag) return 1;
        ++longStr;
        }

        return 0;
        }

      • 王敏 says:

        0x3fff …

      • Yonghang Jiang says:

        直接来个int count[256] = {0}不就行了,开二维数组是想怎样

  5. Lyd says:

    表示英文太菜,可否把Guy的评论也稍微翻译下。。。
    My version of the question starts out by restricting the input to seven letters (for Scrabble) and it was assumed you’d discard any word longer than the rack or shorter than the current best solution so a 32-bit word suffices with some finesses hinted below.
    Candidates who think a bitmask alone would suffice, don’t understand the distinction between a bag and a set. //set俺懂,bag是啥意思?关键字眼不理解真是害死人啊。。。

  6. evan says:

    List: Ordered collection of entities, duplicate allowed. Use a .net IList in code. The index column will need to be mapped in NHibernate.

    Set: Unordered collection of unique entities, duplicates not allowed. Use Iesi.Collection.ISet in code. It is important to override GetHashCode and Equals to indicate the business definition of duplicate. Can be sorted by defining a orderby or by defining a comparer resulting in a SortedSet result.

    Bag: Unordered list of entities, duplicates allowed. Use a .net IList in code. The index column of the list is not mapped and not honored by NHibernate.

    转自:http://stackoverflow.com/questions/1916350/set-bag-and-list-set-in-nhibernate

  7. 浮云流 says:

    非常有意思,哈哈。
    算法真是太奇妙了

  8. Lyd says:

    这么说我是理解错题意了,不过原作者描述的不够清晰。。。
    如果短的字母里面有重复字符,应该也要在长串里面出现多次才行吧?所以Hash是必须的。
    不过Guy的问题谁能给点提示?
    – How can you optimize the mapping of letters to primes?

    – Can you suggest a way to combine the prime representation with a bitmask to improve performance?

    还有出现多次的rack是啥意思?

    • reeze says:

      这个和找出一堆数字里丢失的某个数字的解法差不多,看这个题的时候有想过,不过数字多了就没辙了。数论的用处还真大,不了解的话根本就想不出来这中方法。。

  9. 深夜两点 says:

    一个字母一个位可以更简单。一共就26个英文字母,26位就够了,还没有超出int的范围。使用一个int变量,对于str1遍历,A对应0位,B对应1位,如果str1中有对应的字母,就把int变量对应的位设置为1。其实就跟hashtable差不多,只不过hash规则针对这种情况优化了。然后就是遍历str2,对于其中的字母,只要检查字母对应的位在第一步中的int变量是否为1就可以了,如果为1就是有,不为1就是没有。

    而且,其中一个优化点就是,在便利str1的过程中,每次增加一个字母就让这个int变量是不是后26位全为1了(int值的比较而已),如果是,则表示str1中所有的字母都存在了,则可以结束对str1的遍历,并且也不用对str2进行遍历了,直接返回true就可以。这对于长字符串是很有用的一个优化。

  10. Ida says:

    真有意思!
    不过纠正一个翻译:
    “he nearly peed his leather pants laughing.”
    应翻译成“他大笑不止,几乎尿在他的皮裤上”
    而不是“他对他那条皮裤子大笑不已”

  11. Rambo says:

    更觉得实力+幸运的成分。能被问到同一到题目。

  12. 笨乌不飞 says:

    呃,要是我,我倒是不欣赏那些“巧妙”的算法,让人一看就明白更重要。

  13. Kurt says:

    大家忽略了一个问题,那就是运气也很重要……

  14. glasslion says:

    说实话,我觉得那个素数算法实在渣的可怜
    最大问题是,即使用64位无符号整数保存乘法结果,在处理超过17种字符时就溢出了
    用位图保存最好

  15. 马斯 says:

    你所遇到的不管好坏都是经验~

  16. 4T-Shirt says:

    其实我还有一个算法,
    我觉得也很简单,是O(n+m)的复杂度,用一个空间flag[26],
    遍历一遍第一个字符串,把出现的字母假设为ch,标记为flag[ch-‘A’]=true;
    然后再遍历第二个字符串,看哪个flag[ch-‘A’]为false,就应该可以了

  17. says:

    那个~不知道相亲适用不?

  18. haitao says:

    中间第二家面试的CTO其实也挺牛.map-reduce的作者还有腾讯现在首席科学家都跟那cto混过.我曾经被这样面过,这应该10多年前的故事了,他的面试方法还是那样~

  19. haitao says:

    刚查了下,错了 become.com 还不算10多年那么久。。。05年成立的

  20. sender says:

    如果这两个字符串包含中文字符,哼哼,还素数法呢。

  21. 噶一个 says:

    翻译的太棒了,我想知道那段心理描写的英文原版…比如“带着不可思议的沉着和优雅。带着一种故意表现出来的 —— 带着一种,我认为,只有那种完全的渊博到对古今中外、不分巨细的知识都精通的人才能表现出来的自信”

  22. 学习了,下次去面试要注意。

  23. sponge says:

    太巧妙了!!看来我要学习的东西太多太多了

  24. Jayuh says:

    这是一个不错的面试经历,也让我学到了一些经验,very nice。

  25. Ryan says:

    他们比较希望看到有趣的算法吧。。虽然实际实现上有问题

  26. laruence says:

    有点可笑, 26的阶乘已经超过了64int的表示范围,

    采用一个int, 用26个bit来做开关, 使用位操作, 比这个强多了…..

  27. haha says:

    第一眼想到排序; 第二眼就位操作;

    看了文章后,才想起还有质数这种方法; 很久不看算法题了…

    评论中guy的回复真牛,还能想到是自己出的题?

  28. S_C_P says:

    为嘛我一下想到了chmod命令。。。

  29. Hugo says:

    搞算法的都是牛B的人…

  30. hewei says:

    想问一下,数论上面有没有已经证明,任意2个素数的乘积,只能被这2个素数整除,而不可能被其他素数或非素数整除?

    • abrandy says:

      LS不是問題吧
      “一個大於2的偶數是否能分解為兩個素數的和”,這才叫問題
      素數的定義很重要,複習一下吧
      任意兩個素數的乘積,分解質因數後,只有這兩個素數
      想整除,也必須是這兩個質數之一
      估計只是一時忘記了吧
      提問之前至少要想一下吧

  31. daniel says:

    学到了很多,感谢lz分享

  32. fear317 says:

    素数的方法行不通,建议大家仔细验证一下:大串:2,4,8,9小串2,3,8

  33. 海玉 says:

    很好的一个经历分享,面试路上多实力多技巧。

  34. tanglei says:

    不错。学习啦。

  35. tylerning says:

    想首先问问, 字母只有26个,能很快地分配素数,如果字符串还有其他的东西比如符号啊什么的,怎么分配素数呢,.net中提供了这样的算法了么?

  36. maconel says:

    素数的方法,先把n个素数乘一遍,再把m个素数除一遍,那不也是O(n+m)吗,有比hash法效率高吗,只是更“有趣”而已。

  37. univasity says:

    晕死,GUY说的方法也是O(n+m)的,而且求素数就有得你求了(26个)…杯具的是即使只把这26个素数相乘,其值早就超过int64了(在Java中long也无法表示)…

    其实有一种方法可以实现O(n),但需要一个int[26]的数组用来辅助。用哈希表估计实现起来会简单点,就是第一次遍历长字串,同时遍历短字串,然后分别将其当前index的字符put到哈希(分开不同值,好像如果是长字串的就为1,短字串的为2),下次取回来。每次先判断当前字符是否直接相等,不等的话进一步互相判断长串字符和短串字符在哈希表中是否有对应的值(即是否曾记录过),有对应的则说明之前曾经出现过。

    哎…这样也能进Google,无语中…或许我想错了?

    • ZX says:

      这本质上还是O(n+m)的,因为你还是要遍历两个字符串的全部字母才能确认结果

      • CRAZYCHEN says:

        我思维错乱了吗 ?? GUY的是(n+m)????

        • Crayan says:

          是的,如果把任意两个数字相乘的时间复杂度算作O(1),那最后就是O(n+m)。不用说,实际上数字相乘的时间复杂度不能简单算作O(1),数字越大尤其如此。我也不太明白Guy为什么要这么做,感觉只是换了一种更简洁的思路而已,但实际操作的时间复杂度未必就更小。

  38. alex says:

    不好意思。。。我只明白那种最幼稚的方案。。。
    OMG。。。

  39. image says:

    很有意思,很受启发,算法总是让人手足无措,有时又让人感觉豁然开朗

  40. cheery says:

    有意思! 算法有时候很是出乎意料

  41. bajie says:

    很有趣,大公司的面试就是不一样

  42. menfurmosal says:

    我不是专业程序员,也不是数学背景出生,我想先问一个问题:N个质数(可以有重复)的积得到的某个合数,最终完全分解的质因数是否也一定是这N个质数?
    如果答案是true,那为什么不把第二个字符串也遍历,用同样的方式得到各个字母的乘积,然后与第一个字符串的积相除取余,如果有余,则说明不包含;如果无余,则说明包含!
    如果答案是false,各位就当我没说。
    fish之见,还请大侠们莫要见笑!

    • c says:

      true;連除跟連乘再除是一樣的。但因為太慢了,若用任何一個不包含的質數去除第一字串的積即會造成餘數非零,剩下的質數不必再拿來除。

      • menfurmosal says:

        我懂你的意思,但是如果那个不包含的字母是第二个字符串的最后一个,那不是就需要完全轮询第二个字符串吗?如果是用第二个字符串的积去除,就只需除一次,只要有余数,就证明有不包含的字母,不管这个(些)字母在第二个字符串的什么位置;如果没余数,那就表示全部包含。guy的意思是不考虑其他因素,用最少的步骤得出结果,只除一次应该是最好的了。而其他轮询方式,最少也要一次,最多就需要N次了。(留下联系方式,欢迎讨论,哈哈)mr.color95@gmail.com

    • 霁云飞 says:

      1.得到第二个字符串的积的过程就一定要遍历完整的第二个字符串,但如果是一个一个除的话,就可能会在除的过程中获得余数,结束计算。所以先得第二个字符串的积再除的方法效率低。
      2.如果第二个字符串中出现重复字符,使用积的方法则只有在第一个字符串的同样字符也重复的情况下才会不出现余数。所以先得到第二个字符串积的方法不可取。注:原方法也需要用第一个字符串的积除以第二个字符串的每个字符,不能用中间结果除。

  43. Soleil says:

    你说的这个乘积是不是已经溢出位了?如果字付串长的话。
    ————
    menfurmosal 说:
    2012年04月7日11:06 上午
    我懂你的意思,但是如果那个不包含的字母是第二个字符串的最后一个,那不是就需要完全轮询第二个字符串吗?如果是用第二个字符串的积去除,就只需除一次,只要有余数,就证明有不包含的字母,不管这个(些)字母在第二个字符串的什么位置;如果没余数,那就表示全部包含。guy的意思是不考虑其他因素,用最少的步骤得出结果,只除一次应该是最好的了。而其他轮询方式,最少也要一次,最多就需要N次了。(留下联系方式,欢迎讨论,哈哈)mr.color95@gmail.com

  44. 西瓜肚圆圆 says:

    素数的方案有技巧,但是如果实际工作中应该选择hashtable这种更好些

  45. peach5460 says:

    我一直没明白一个问题

    对于hash是存在
    对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2)

    下面这个:
    最终,我告诉了他一个最佳的算法,只需要O(n+m)次操作。方法就是,对第一个字串进行轮询,把其中的每个字母都放入一个Hashtable里(成本是O(n)或16次操作)。然后轮询第二个字串,在Hashtable里查询每个字母,看能否找到。如果找不到,说明没有匹配成功。这将消耗掉8次操作 —— 这样两项操作加起来一共只有24次。不错吧,比前面两种方案都要好。

    那么,万一有两个字母的hash一致,这个算法不就完蛋了么?

  46. J-ram says:

    Guy的方案和hashtable的方案到底谁快了?除法指令周期不是比较长吗?

  47. martin says:

    public static boolean contains(String left, String right) {
    int magicLeft = toMagicInt(left);
    int magicRight = toMagicInt(right);
    return (magicLeft & magicRight) == magicRight;
    }

    public static int toMagicInt(String text) {
    int result = 0;
    int index = 0;
    for (char c : text.toLowerCase().toCharArray()) {
    index = c – ‘a’;
    result |= 2 << index;
    }
    return result;
    }

  48. nnkken says:

    我也是想到素數方法
    很高興我能想到一些受讚嘆的方法,讓我感到自豪

  49. 张强 says:

    int test(const char *str1, const char *str2)
    {
    printf(“test for [%s] and [%s]”, str1, str2);
    if(str1 == 0 || str2 == 0)
    {
    return 0;
    }
    int nBase[26] = {0};
    while(*str1 != 0)
    {
    int nIndex = (*str1 – ‘A’ > 25) ? (*str1 – ‘a’) : (*str1 – ‘A’);
    nBase[nIndex] = 1;
    str1++;
    }
    while(*str2 != 0)
    {
    int nIndex = (*str2 – ‘A’ > 25) ? (*str2 – ‘a’) : (*str2 – ‘A’);
    if(nBase[nIndex] == 0)
    {
    return 0;
    }
    str2++;
    }
    return 1;
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    printf(” result is %d\n”,
    test(“ABCDEFGHLMNOPQRS”, “DCGSRQPOM”));
    printf(” result is %d\n”,
    test(“ABCDEFGHLMNOPQRS”, “DCGSRQPOZ”));
    printf(” result is %d\n”,
    test(“abcdefghlmnopqrs”, “DCGSRQPOM”));
    printf(” result is %d\n”,
    test(“ABCDEFGHLMNOPQRS”, “dcgsrqpoz”));
    return 0;
    }

  50. Simple says:

    也可以使用indexOf:
    static void Main(string[] args)
    {
    string rt = “”;
    string str1 = “ABCDEFGHLMNOPQRS”;
    string str2 = “DCGSRQPOMZ”;
    char[] strChar = str2.ToCharArray();
    for (int i = 0; i < strChar.Length; i++) {
    if (str1.IndexOf(strChar[i]) < 0)
    {
    rt = strChar[i].ToString();
    break;
    }
    }
    Console.WriteLine(rt==""?true:false);
    Console.ReadLine();
    }

    • skylovers says:

      哥们,你的做法真心弱爆了,因为你没考虑indexOf里面的时间复杂度。事实上你的算法也是最差的O(m*n)

  51. xiejunme says:

    很不错呀,要学的东西还很多呀

  52. 林涛 says:

    数学学不好 编程做不了啊

  53. mos says:

    翻译的挺好的

  54. Scofined says:

    int num[127]={0}
    For(int I=0;I<a1len;I++)
    Num[a1[i]]=1;
    Int exist=1;
    For(int I=0;I<a2len;I++)
    {
    Exist=exist*num[a2[i]];
    If(exist==0)
    Break;
    }
    iPad 上输出。我觉得应该够快了

  55. Guy says:

    哥们,哥们,哈哈
    事实上,这个经验在你生活中的很多其它事情上也适应。

  56. David Xu 对这篇文章的反应是赞一个
  57. 无痕 says:

    使用素数固然精妙,但是给一个个字符赋值数字的时候不是更麻烦吗

  58. 呵呵 对这篇文章的反应是赞一个
  59. 秋水寒 对这篇文章的反应是敬佩赞一个
  60. 袁廉祎 对这篇文章的反应是赞一个
  61. 陈寒 对这篇文章的反应是赞一个
  62. moring jia  这篇文章, 并对这篇文章的反应是赞一个
  63. 李继光 对这篇文章的反应是赞一个
  64. shuaiagain 对这篇文章的反应是赞一个
  65. 蒲刚 对这篇文章的反应是赞一个
  66. 李银 对这篇文章的反应是赞一个
  67. 王家瑞  这篇文章, 并对这篇文章的反应是
  68. 很不错呀,要学的东西还很多呀

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据