G onsite题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G onsite题目

G onsite题目# JobHunting - 待字闺中

s*i2014-01-09 08:01

1 楼

Given a list of words, find two strings S & T such that:
a. S & T have no common character
b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm
前面有讨论用一个int来决定S和T是否有common character。但S.length() * T.length
() 还需要找出n^2个组合，这个有办法降低吗？

s*t2014-01-09 08:01

2 楼

dp吧

x*g2014-01-09 08:01

3 楼

我很想知道你怎么dp? 请指教，谢谢！

【在 s******t 的大作中提到】

: dp吧

d*b2014-01-09 08:01

4 楼

这个题不用dp。
直接用bitset就搞定了。
每一个字符串对应一个 bitset，或者 32位的整数，如果只是字母的话。
如果有这个字母，相应的位就 mark 1，否则mark 0。
然后以第一个为基准，扫描到逻辑和不为零的全部删掉。
一直这样做下去。直到找到逻辑和为零的。
平均复杂度，应该在 nlog(n) 。
至于第二个，应该是在第一个的基础上，找出两个最大的。
这个不难了。

x*g2014-01-09 08:01

5 楼

“平均复杂度，应该在 nlog(n) 。”
你是怎么想当然算的？

【在 d******b 的大作中提到】

: 这个题不用dp。
: 直接用bitset就搞定了。
: 每一个字符串对应一个 bitset，或者 32位的整数，如果只是字母的话。
: 如果有这个字母，相应的位就 mark 1，否则mark 0。
: 然后以第一个为基准，扫描到逻辑和不为零的全部删掉。
: 一直这样做下去。直到找到逻辑和为零的。
: 平均复杂度，应该在 nlog(n) 。
: 至于第二个，应该是在第一个的基础上，找出两个最大的。
: 这个不难了。

s*t2014-01-09 08:01

6 楼

compare有没有common char当然是o（n）了，这步简单啊，后面求最大长度只能穷举吧
？不然sort之后再穷举？有什么其他办法优化？

f*s2014-01-09 08:01

7 楼

可以建一个inverted index
然后扫面每个string, 并且排除有common character的string
最后如果有其他string生下来了，就找到结果了。
这样建立inverted index时间复杂度是O(n)
扫描时间复杂度是O(n)*O(len of string)

s*t2014-01-09 08:01

8 楼

剩余string再sort出结果？

【在 f******s 的大作中提到】

: 可以建一个inverted index
: 然后扫面每个string, 并且排除有common character的string
: 最后如果有其他string生下来了，就找到结果了。
: 这样建立inverted index时间复杂度是O(n)
: 扫描时间复杂度是O(n)*O(len of string)

f*s2014-01-09 08:01

9 楼

不用sort, 剩余的string都和target string没有common characters.
所以任意一个和target string一起就是一个solution

【在 s******t 的大作中提到】

: 剩余string再sort出结果？

s*t2014-01-09 08:01

10 楼

没太明白，不是得求最大s1.len * s2.len 吗?
按照你的方法可以得到很多符合条件的string pair,但是不sort怎么求最大呢？
我觉得扫描过程中没法存最大吧，因为要不断的要删掉不符合条件的stringpair啊

【在 f******s 的大作中提到】

: 不用sort, 剩余的string都和target string没有common characters.
: 所以任意一个和target string一起就是一个solution

f*s2014-01-09 08:01

11 楼

(⊙o⊙)哦，没有注意maximize len*len的条件。
那就把所有的string都在inverted index中扫一遍，然后选一个符合条件的最长串和他
匹配。
需要事先按照串的长度sort一下。
找符合条件的最长串可以用一个bitset，unset所有不符合条件的串，然后用位操作找
出least significant 1的位置就是最长的串

【在 s******t 的大作中提到】

: 没太明白，不是得求最大s1.len * s2.len 吗?
: 按照你的方法可以得到很多符合条件的string pair,但是不sort怎么求最大呢？
: 我觉得扫描过程中没法存最大吧，因为要不断的要删掉不符合条件的stringpair啊

d*b2014-01-09 08:01

12 楼

首先，有上界 O(n^2)
其次，有下界O(n)
还有再想想，每次扫描都会有一部分的bitset被删掉。
如果一个都没有被删那就是答案。
每次扫描都是在上次扫描被删的基础上，
所以我说应该在 O(nlogn)，当然你要说想当然也行。

【在 x****g 的大作中提到】

: “平均复杂度，应该在 nlog(n) 。”
: 你是怎么想当然算的？

x*g2014-01-09 08:01

13 楼

我就是想弄明白你怎么想的，呵呵。
怎么能删掉呢？
当前A,你扫描把和A相交的都删掉？这样有遗漏啊.....
你下次扫B,但和A相交的可能和B不相交已经被你删掉了？

【在 d******b 的大作中提到】

: 首先，有上界 O(n^2)
: 其次，有下界O(n)
: 还有再想想，每次扫描都会有一部分的bitset被删掉。
: 如果一个都没有被删那就是答案。
: 每次扫描都是在上次扫描被删的基础上，
: 所以我说应该在 O(nlogn)，当然你要说想当然也行。

s*t2014-01-09 08:01

14 楼

不错，我还想用matrix，费空间，bitset好

【在 f******s 的大作中提到】

: (⊙o⊙)哦，没有注意maximize len*len的条件。
: 那就把所有的string都在inverted index中扫一遍，然后选一个符合条件的最长串和他
: 匹配。
: 需要事先按照串的长度sort一下。
: 找符合条件的最长串可以用一个bitset，unset所有不符合条件的串，然后用位操作找
: 出least significant 1的位置就是最长的串

d*b2014-01-09 08:01

15 楼

你说的对，拍脑袋想出来的果然有问题。

【在 x****g 的大作中提到】

: 我就是想弄明白你怎么想的，呵呵。
: 怎么能删掉呢？
: 当前A,你扫描把和A相交的都删掉？这样有遗漏啊.....
: 你下次扫B,但和A相交的可能和B不相交已经被你删掉了？

s*t2014-01-09 08:01

16 楼

dp=穷举

【在 x****g 的大作中提到】

: 我很想知道你怎么dp? 请指教，谢谢！

g*g2014-01-09 08:01

17 楼

不确定是否有 nLog(n)的解，不过 n^2的解法是可以调优的。
首先先把数组sort了，按长度降序
string s[];//
int signature[];//
int length[];// length of each string
int n; // length of s
int max = 0;
for(int i=0; i{
for(int j=i+1; j{
if (length[i] * length[j] <= max)
{
break; // optimize 1, early stop
}
if (signature[i] & signature[j] == 0)
{
max = max(length[i] * length[j], max);
break;// optimize 2, no need to test rest
}
}
}

length

【在 s*****i 的大作中提到】

: Given a list of words, find two strings S & T such that:
: a. S & T have no common character
: b. S.length() * T.length() is maximized
: Follow up: how to optimize and speed up your algorithm
: 前面有讨论用一个int来决定S和T是否有common character。但S.length() * T.length
: () 还需要找出n^2个组合，这个有办法降低吗？

b*s2014-01-09 08:01

18 楼

可以做到 O( l*n + a*2^a), 其中n是单次个数，a是字符范围个数（所有小写字母的话
a就是26），l 是单词长度
下面Quora这个链接说的是求最大S.length() + T.length()的，改成S.length() * T.
length()算法是一样的，就最后一步把求最大和改成最大积而已
http://www.quora.com/Algorithms/Given-a-dictionary-of-words-how

s*i2014-01-09 08:01

19 楼

没有quora帐号，楼主可否直接copy色鲁迅过来。
谢谢！

【在 b*********s 的大作中提到】

: 可以做到 O( l*n + a*2^a), 其中n是单次个数，a是字符范围个数（所有小写字母的话
: a就是26），l 是单词长度
: 下面Quora这个链接说的是求最大S.length() + T.length()的，改成S.length() * T.
: length()算法是一样的，就最后一步把求最大和改成最大积而已
: http://www.quora.com/Algorithms/Given-a-dictionary-of-words-how

D*d2014-01-09 08:01

20 楼

2^{26} = 64M
计算 64M 个组合的 max_length
扫描一遍，binary tree 分支统计 branch 最长长度，
维持 current maximum value