一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1782|回复: 27
收起左侧

Google 12/11 Onsite

[复制链接] |试试Instant~ |关注本帖
crisc3 发表于 2015-12-11 16:12:43 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
比较难想的题目:
给一个dictionary,里面包含很多字符串。 ex: dict{"aabc", "bcd", "aew","wxyz"} 找出里面customsize最大的一对字符串,string s, string t, . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果满足没有任何char同时出现在s 和t里面, customsize = s.size() * t.size()。 反之customsize = 0;. visit 1point3acres.com for more.

举例:上述字典中 customsize("aabc", "bcd") = 0, customsize("aew","wxyz") = 3*4 = 12,customsize("aabc","wxyz") = 4*4 = 16. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
所以最后return "aabc", "wxyz"。如果有多个 return 一对即可

请说明你的算法的time complexity。字典长度为M, 字符串平均长度为 N

评分

1

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-12-11 19:23:36 | 显示全部楼层
crisc3 发表于 2015-12-11 16:15
@stellari 求问有除了brute force以外的什么好方法吗?

如果单词只包含小写字母的话,你可以用一个32位int表示出这个单词中有那些字母;这样两个单词是否有相同字母就可以在O(1)时间内用“与”操作解出。两两比较单词,最后只用O(M^2)时间。

另外,这版上大神这么多为啥只召唤我……
回复 支持 1 反对 0

使用道具 举报

 楼主| crisc3 发表于 2015-12-11 16:13:17 | 显示全部楼层
大家贡献下最佳思路吧
回复 支持 反对

使用道具 举报

 楼主| crisc3 发表于 2015-12-11 16:15:39 | 显示全部楼层
@stellari 求问有除了brute force以外的什么好方法吗?
回复 支持 反对

使用道具 举报

include110 发表于 2015-12-11 21:34:55 | 显示全部楼层
我觉得这一道题可以分为两部分来解决,第一部分就是如何快速从两个字符串中判断是否有重叠的字符,方法跟楼上的一样,应该是最快的方法了,用一个32位int整数来以此表示a-z的有或者没有,然后用与操作来比较两个字符串是否重叠,第一部可以先转换,到第二部分再进行比对,复杂度O(n);第二部分是如何快速根据第一部分的结果从一个数组中找到customsize最大的值,这一部分好像也只能O(n^2)了,求大神良策。。。
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-12-11 22:25:11 | 显示全部楼层
可以考虑一下divide and conquer的解法吧,第一步根据包含的字母divide,比如第一步分为有a组, 和没a组。 有a组的话,内部不可能成为解。有a组的可以单个拿出来与没a组的结合,只不过a,这样就从n的问题变成 k 个n-1个问题了(k指k个有a的string). 等最后分组分完了26次,剩下的在一起的就是互不相欠的了,只要组内取长度前2就作为可能的结果,update最大值了。
回复 支持 反对

使用道具 举报

yl2762 发表于 2015-12-12 02:42:28 | 显示全部楼层
弱弱的没看懂题目T-T,customize最大是什么意思呀?
回复 支持 反对

使用道具 举报

yl2762 发表于 2015-12-12 02:43:20 | 显示全部楼层
哦哦我好像看懂了
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-12 07:33:41 | 显示全部楼层
stellari 发表于 2015-12-11 19:23
如果单词只包含小写字母的话,你可以用一个32位int表示出这个单词中有那些字母;这样两个单词是否有相同 ...

弱弱的问一下,怎么用32位int表示这个单词有哪些字母哈?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-12 09:18:32 | 显示全部楼层
潇洒走一回 发表于 2015-12-11 22:25
可以考虑一下divide and conquer的解法吧,第一步根据包含的字母divide,比如第一步分为有a组, 和没a组。  ...

我没理解错的话,这方法最坏情况下比不分组还要费时。假设字典中所有单词都恰含有13个不同的字母(但单词长度不一),且所有字母均匀分布在所有单词中。也就是说,以任何字母做标准来分组,字典都会被恰好分成相等的两部分。那么以a分组的话,我们最坏情况下要做(N/2 * N/2) = (1/4) * N^2次比较。对26个字母都如此分组的话,那么总共要做(13/2) * N ^2次比较,这还没有算上把单词按每个字母分组这个过程所需要的额外时间。

所以,我觉得还不如不分组。当然我有可能没正确理解你的意思。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-12 09:22:20 | 显示全部楼层
xiaoniuona 发表于 2015-12-12 07:33
弱弱的问一下,怎么用32位int表示这个单词有哪些字母哈?

设n是个32位int,如果单词w中有'a',那么n的第一位为1,反之为0;如果w中有'b',那么n的第二位为1,反之为0...。比如,单词baad的表示就是(0000....00001011).
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-12-12 09:58:16 | 显示全部楼层
stellari 发表于 2015-12-12 09:18
我没理解错的话,这方法最坏情况下比不分组还要费时。假设字典中所有单词都恰含有13个不同的字母(但单词 ...
. visit 1point3acres.com for more.
以a的分组的话,假设分成两半,n/2有a, n/2无a,其实最后是转换成了n/2个 有(n/2 + 1)个string的问题。 T(n) = n/2 T(n/2) + n. 这样算下来是一个很糟糕的算法。 Thanks for pointing out!
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-12-12 10:17:26 | 显示全部楼层
stellari 发表于 2015-12-12 09:18
我没理解错的话,这方法最坏情况下比不分组还要费时。假设字典中所有单词都恰含有13个不同的字母(但单词 ...
. 1point 3acres 璁哄潧
不过,可以考虑先根据长度排序,用two pointer的方法, point1指向最长的,point2指向第二长的,如果最初这两个满足没有交集那么就是答案了,直接返回。如果有交集的话那么就把point2往右移动,如果在移动过程中有没有交集的两个那么可以先算出作为临时的答案。

加入临时答案是来自index point1,point2. 那么下一次我要做的就是转换到一个更小的问题,check point1+1~point2之间的string, 同样是从two pointer,分别 指向最大,第二大。

停下来的条件是更小的问题的size为0的时候.
. From 1point 3acres bbs
这种方法,最坏的情况还是O(n^2),但是大多数情况可以结束的更早。.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-12-12 10:17:38 | 显示全部楼层
stellari 发表于 2015-12-12 09:18
我没理解错的话,这方法最坏情况下比不分组还要费时。假设字典中所有单词都恰含有13个不同的字母(但单词 ...

不过,可以考虑先根据长度排序,用two pointer的方法, point1指向最长的,point2指向第二长的,如果最初这两个满足没有交集那么就是答案了,直接返回。如果有交集的话那么就把point2往右移动,如果在移动过程中有没有交集的两个那么可以先算出作为临时的答案。

加入临时答案是来自index point1,point2. 那么下一次我要做的就是转换到一个更小的问题,check point1+1~point2之间的string, 同样是从two pointer,分别 指向最大,第二大。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
停下来的条件是更小的问题的size为0的时候.

这种方法,最坏的情况还是O(n^2),但是大多数情况可以结束的更早。
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-12-12 10:17:53 | 显示全部楼层
stellari 发表于 2015-12-12 09:18. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我没理解错的话,这方法最坏情况下比不分组还要费时。假设字典中所有单词都恰含有13个不同的字母(但单词 ...

-google 1point3acres不过,可以考虑先根据长度排序,用two pointer的方法, point1指向最长的,point2指向第二长的,如果最初这两个满足没有交集那么就是答案了,直接返回。如果有交集的话那么就把point2往右移动,如果在移动过程中有没有交集的两个那么可以先算出作为临时的答案。

加入临时答案是来自index point1,point2. 那么下一次我要做的就是转换到一个更小的问题,check point1+1~point2之间的string, 同样是从two pointer,分别 指向最大,第二大。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
停下来的条件是更小的问题的size为0的时候.

这种方法,最坏的情况还是O(n^2),但是大多数情况可以结束的更早。
回复 支持 反对

使用道具 举报

 楼主| crisc3 发表于 2015-12-12 10:43:36 | 显示全部楼层
潇洒走一回 发表于 2015-12-12 10:17
不过,可以考虑先根据长度排序,用two pointer的方法, point1指向最长的,point2指向第二长的,如果最初 ...

不错  这样的想法是一个可行的优化,我没理解错的话,先根据length sort, 然后两个pointeri, j (i<j)从最长到最短loop找最优解。比如说现在找到了最优解 100*4 , 那么s[j].len < 4的时候就不需要再loop了 另外 s < sqrt(400) = 20的时候也不需要再loop了。. 1point3acres.com/bbs
当然 所有的预处理请参考stellari大神. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
所以是
int bestResult = 0, lowb = 0;
for(int i = 0; i<M && s.size() >= sqrt(bestResult) ; i++){
    for(int j = i+1; j < M && s[j].size() >= lowb; j++){. 1point3acres.com/bbs
        //...do something... update bestRes and low
    }
}
回复 支持 反对

使用道具 举报

一路向北~ 发表于 2015-12-13 05:23:20 | 显示全部楼层
弱问一句customsize("aew","wxyz") = 3*4 = 12, 'w'不是同时出现在"aew"和"wxyz"里面了么?是typo还是我理解错了?
回复 支持 反对

使用道具 举报

 楼主| crisc3 发表于 2015-12-13 06:16:45 | 显示全部楼层
一路向北~ 发表于 2015-12-13 05:23
弱问一句customsize("aew","wxyz") = 3*4 = 12, 'w'不是同时出现在"aew"和"wxyz"里面了么?是typo还是我理 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
typo 不好意思。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 11:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表