闲着无聊在微信上看到一个皮裤子面试算法的问题,面试者Paul后来用皮裤子的算法赢得了Google的职位。题目如下:
假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?
比如,如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true,所有在string2里的字母string1也都有。如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false,因为第二个字符串里的Z字母不在第一个字符串里。
皮裤子给出的算法是把小字符串的字符用质数编码相乘。然后遍历大字符串,如果积能被任何字符整除,没有特殊字符。
看到这里,貌似很精妙,但是仔细推敲有漏洞:
1. 乘除法cpu周期多
2. 如果有26个英文字母,那么需要26个质数,2-101, 用excel整数以后是38位整数。。。这怎么表示和计算?
看完之后真的怀疑人生,难道google这么好混?26个字符,用int当bitmap就好了
忍不住骑墙去看
原文,果然有50个人在评论中质疑,也有人提到bitsmap算法。
但是其中一个中国人的回复让人很钦佩:Xiaonan Ji说这是讲面试经验的最好文章,抛开算法,怎样为心仪的公司面试先去面试别的公司,面试中的心里技巧。。。
解决问题容易,包容别人难
http://blog.sina.com.cn/s/blog_620ccfbf0100r69s.html
btw, 知乎上看了一下算法相关讨论,居然跟奥数一样变成刷题,有专门的线上刷题,高效啊。这样进大公司又能说明什么呢?记得以前scjp考高分的一个网友。。。不过看看一些题目的做法的确很巧妙,欲罢不能,有些题目真的用到奥数知识,比如回文数必须是11的倍数等。。。
出题的人也辛苦,要不断出网上没有的题目。看样以后面试还是出些现实问题看怎样一步一步分析吧。记得以前问无人机遥控的方案就很有意思。
分享到:
相关推荐
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
C#版的字符串差异对比类。 可以比较两个字符串的不同之处。返回结果为两个字符串的差异变化项,具有一定的参考和实用价值,根据返回的差异数组可以自由实现不同的表现形式,比如差异文字高亮。
Levenshtein算法python也是用的这个对比字符串相似度的,还不错
设计Strcmp(s,t)算法,实现两个字符串s和t的比较。
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符...试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。
计算两个字符串的编辑距离 -- 快速算法
使用最短编辑距离算法判断两个字符串的相似度
p79_2ti 设计strcmp(s,t)算法,实现两个字符串的比较
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
数据结构上机作业 第二章17题 张宪超 数据结构算法及应用
找出两个字符串之间相同字符算法题可以进行拆分字符串进行比较
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
求两个字符串的最长公共字符串 输出全部位置信息,并输出字符串,相同字符串先输出所有位置信息在输出字符串 测试平台:XP/VS 2008 CN
Java 实现推荐系统 两个字符串 余弦相似度 算法。
输入任意两个字符串,计算它们的编辑距离。 编辑距离是指两个字符串之间,由一个转换为另一个所需的最少编辑操作次数。许可的编辑操作包括字符的替换、插入和删除。
算法与数据结构(C语言描述) 顺序表两个字符串连接起来,自己手打的,总的来说我感觉算法与数据结构
算法训练 比较字符串 时间限制:1.0s 内存限制:512.0MB 编程实现两个字符串s1和s2的字典序比较。若它们不相等,则指出其第一个不同字
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
一个完整可直接用的LD算法计算两个字符串之间的相似度。