i*********e
发帖数: 21 | 1 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
时间已经不够写代码了。
想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
我的感觉是没有的。当然，我可能是错的。
教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
，至少也知道你想到了一个方法。最忌讳闷头苦想，而面试官根本不知道你在想啥。
==========
去年还面了FB的onsite，挂在把二叉树转为双向链表上，吐血。当时昏了头拼了命要写
个functional style的，结果把自己绕进去了。其实搞个全局变量记录上次访问的节点
的话很简单。
今年想再试试linkedin和twitter两家。因为G和F的recruiter之前联系过了，就不找人
内推了。求帮忙！如果之前有人发过提供内推的贴，给个链接也好。 |
w****a
发帖数: 710 | 2 这题在n个地方看到过了。也是一直没太好的想法，求大神指导 |
l*****a
发帖数: 14598 | 3 BT==>DLL不是recursion就可以了吗
看起来你准备用in-order traverse做，然后每次跟前面的node link...
【在 i*********e 的大作中提到】
: 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
: 一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
: 上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
: 。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
: 想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
: 了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
: 时间已经不够写代码了。
: 想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
: 我的感觉是没有的。当然，我可能是错的。
: 教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
|
l*****a
发帖数: 14598 | 4 sort by the length of those strings ,start from biggest
a[0] a[1] ... a[n-1]
check whether no dup between a[0]a[1] , if no dup, return
then check a[0]a[2].
then a[0]a[3] or a[1]a[2]...
put pair in a heap, eachtime popup the smallest, insert one/two new pairs...
worst case的复杂度比O(n2)大，但是考虑到能尽快得到结果,amortized复杂度是不是
还可以呢
【在 w****a 的大作中提到】
: 这题在n个地方看到过了。也是一直没太好的想法，求大神指导
|
i*********e
发帖数: 21 | 5
..
实际应用应该不错。但是如果所有长度一样，任何按长度的排序都是无用功。
【在 l*****a 的大作中提到】
: sort by the length of those strings ,start from biggest
: a[0] a[1] ... a[n-1]
: check whether no dup between a[0]a[1] , if no dup, return
: then check a[0]a[2].
: then a[0]a[3] or a[1]a[2]...
: put pair in a heap, eachtime popup the smallest, insert one/two new pairs...
: worst case的复杂度比O(n2)大，但是考虑到能尽快得到结果,amortized复杂度是不是
: 还可以呢
|
i*********e
发帖数: 21 | 6
嗯？难道不是这么干的？
【在 l*****a 的大作中提到】
: BT==>DLL不是recursion就可以了吗
: 看起来你准备用in-order traverse做，然后每次跟前面的node link...
|
l*****a
发帖数: 14598 | 7 那不也是第一个满足no dup的就是结果
不用像O(n2)那样都做一遍，找最大的
【在 i*********e 的大作中提到】
:
: 嗯？难道不是这么干的？
|
h****t
发帖数: 69 | |
l*****a
发帖数: 14598 | 9 写recursion更简洁吧
除非不让你写
【在 i*********e 的大作中提到】
:
: 嗯？难道不是这么干的？
|
S********0
发帖数: 5749 | 10
in_order 也是recursion吧， 这题主要麻烦就是in order时处理好首尾相连的问题
【在 l*****a 的大作中提到】
: 写recursion更简洁吧
: 除非不让你写
|
|
|
r****7
发帖数: 2282 | 11 把当前的节点记成prevs不就行了么？
【在 S********0 的大作中提到】
:
: in_order 也是recursion吧， 这题主要麻烦就是in order时处理好首尾相连的问题
|
o****n
发帖数: 937 | 12 message me your resume for l
【在 i*********e 的大作中提到】
: 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
: 一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
: 上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
: 。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
: 想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
: 了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
: 时间已经不够写代码了。
: 想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
: 我的感觉是没有的。当然，我可能是错的。
: 教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
|
i*********t
发帖数: 16 | 13 第一题可以加大难度。
求最大edit distant两个字符串，小于n^2.
【在 i*********e 的大作中提到】
: 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
: 一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
: 上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
: 。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
: 想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
: 了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
: 时间已经不够写代码了。
: 想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
: 我的感觉是没有的。当然，我可能是错的。
: 教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
|
i*********e
发帖数: 21 | 14
谢了！
里面提到的基于bitmask的优化我倒也想到了。不过最多upvote的那个确实不错，关键
是dp的第二步。这个方向我面试时也想过，不过无果。
看下来觉得只有基于小字符集的优化可以优于O(n^2),尤其是n足够大的时候。看来确实
没有可以在所有情况下优于O(n^2)的解法。
【在 h****t 的大作中提到】
: http://www.quora.com/Given-a-dictionary-of-words-how-can-we-eff
|
f**********t
发帖数: 1001 | 15 // Given a dictionary of words, how can we efficiently find a pair words s.t
. they don't have characters in common and sum of their length is maximum?
size_t MaxLengthSumOfDistinctPairs(vector vs) {
vector char2str[26];
for (size_t i = 0; i < vs.size(); ++i) {
for (char c : vs[i]) {
char2str[c - 'a'].push_back(i);
}
}
size_t res = 0;
for (size_t i = 0; i < vs.size(); ++i) {
unordered_set dups;
for (char c : vs[i]) {
for (size_t k : char2str[c - 'a']) {
dups.insert(k);
}
}
for (size_t j = i + 1; j < vs.size(); ++j) {
if (dups.find(j) == dups.end()) {
res = max(res, vs[i].size() + vs[j].size());
}
}
dups.clear();
}
return res;
}
void MaxLengthSumOfDistinctPairsTest() {
cout << MaxLengthSumOfDistinctPairs({ "abc", "cde", "f", "efh"})
<< ' ' << MaxLengthSumOfDistinctPairs({ "abcd", "cde", "f", "efh"})
<< ' ' << MaxLengthSumOfDistinctPairs({"aaa", "bb","abcd"}) << endl;
} |
d******w
发帖数: 2213 | 16 我还面试过小人在迷宫里找出口。面试官说不能track位置，因为位置信息不知道。我
就告诉他，把小人醒来的地方作为0，0， 不就有位置信息了么，他不做声。我只好暴
力破解，然后人给评语写的太差了。。。
没办法，面试就是个运气过程，实力一半。。。。
【在 i*********e 的大作中提到】
: 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
: 一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
: 上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
: 。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
: 想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
: 了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
: 时间已经不够写代码了。
: 想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
: 我的感觉是没有的。当然，我可能是错的。
: 教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
|
p**********3
发帖数: 127 | |
M**********7
发帖数: 378 | 18 这道题研究了一下，大概上说的确没有优于O(n^2)的方法。
但是在alphabet的size (记为|a|)不大的时候可以用这个方法：
http://www.quora.com/Given-a-dictionary-of-words-how-can-we-eff
优化点：我们只关心两个串间的重复字符，不关心同串里字符重复，所以同字符越多越
占便宜，所以对于同一个字符集，总有最大的word，这个就是老大，其他的可以忽略。
Trick点：第二步，求longest word that consists of at most those letters。这样
使得字符集之间的运算成为可能。
之后就是一般人很怕的2^|a| 的dp逐渐从size为1的build起来。
但在|a|不大and/or字母组合多了以后逐渐稀疏 (例如同时用到7个不同字母的单词数远
远小于 |a|^7) 的时候，一般达不到2^|a|这么多。
这个已经是最优了，因为实际上是数据挖掘中Apriori 算法 http://en.wikipedia.org/wiki/Apriori_algorithm 的经典款 （有paper会改进有小提高，但是面试中如果要求就有点过分了。）
同意楼主说的，面试一定要交流。个人感觉嘴里不要有超过5秒的停留。想啥说啥，这
个如果不习惯的话自己多练练，个人感觉练白板的一个重要部分是练习这个。例如原帖
里面说提示了剪枝，个人感觉比较好的方法是顺着这个思路想：好的，我们考虑剪枝，
然后试验列举几个自己想到的剪枝方案，然后说出来，这时候面试官会和你进行讨论，
我们不要怕说错了， 只不要是常识性错误。面试官可能会在你接近的时候给个提示，
有的时候会看似给你个反例，其实是在引导你的思路，你要做的是顺着这个思路去分析
，如果觉得不可能，则提出为什么不可能，并给出分析。要知道面试官顶多预先准备过
一些方法，他们也不会把所有的情况都知道了，而不同的人解决问题思路肯定会有不同
，所以只能靠交流来了解你的思路， 是如果能把想法说清楚，面试官觉得可行也会同
意。当然，这里说的不是遇到故意黑的情况。
另外有点，就是感觉有的面试者太执着于最差复杂度，或理论复杂度，但实际应用中的
情况和优化可能是公司更重视的。类似的有game of life，其实优化后复杂度差不多，
但是考虑实际情况就差很多。
祝大牛找工顺利！
【在 i*********e 的大作中提到】
: 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
: 一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
: 上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
: 。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
: 想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
: 了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
: 时间已经不够写代码了。
: 想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
: 我的感觉是没有的。当然，我可能是错的。
: 教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
|
M**********7
发帖数: 378 | 19 啊， 好奇怪，我进来以后没显示全部回帖，现在看到前面提到了解法。
好在我的回帖也不是全部重复。 |
M**********7
发帖数: 378 | 20 难道是考这个：
http://en.wikipedia.org/wiki/Maze_solving_algorithm#Pledge_algo
这个没见过挺难想到的。
【在 d******w 的大作中提到】
: 我还面试过小人在迷宫里找出口。面试官说不能track位置，因为位置信息不知道。我
: 就告诉他，把小人醒来的地方作为0，0， 不就有位置信息了么，他不做声。我只好暴
: 力破解，然后人给评语写的太差了。。。
: 没办法，面试就是个运气过程，实力一半。。。。
|
|
|
i*********e
发帖数: 21 | 21 是，有啥说啥很重要。
【在 M**********7 的大作中提到】
: 这道题研究了一下，大概上说的确没有优于O(n^2)的方法。
: 但是在alphabet的size (记为|a|)不大的时候可以用这个方法：
: http://www.quora.com/Given-a-dictionary-of-words-how-can-we-eff
: 优化点：我们只关心两个串间的重复字符，不关心同串里字符重复，所以同字符越多越
: 占便宜，所以对于同一个字符集，总有最大的word，这个就是老大，其他的可以忽略。
: Trick点：第二步，求longest word that consists of at most those letters。这样
: 使得字符集之间的运算成为可能。
: 之后就是一般人很怕的2^|a| 的dp逐渐从size为1的build起来。
: 但在|a|不大and/or字母组合多了以后逐渐稀疏 (例如同时用到7个不同字母的单词数远
: 远小于 |a|^7) 的时候，一般达不到2^|a|这么多。
|
b******i
发帖数: 914 | 22 谢谢详细的解释，
但是真的面试的时候遇到这题，难道就要上这个方法吗，比如2^a长度的数组怎么写法？
【在 M**********7 的大作中提到】
: 这道题研究了一下，大概上说的确没有优于O(n^2)的方法。
: 但是在alphabet的size (记为|a|)不大的时候可以用这个方法：
: http://www.quora.com/Given-a-dictionary-of-words-how-can-we-eff
: 优化点：我们只关心两个串间的重复字符，不关心同串里字符重复，所以同字符越多越
: 占便宜，所以对于同一个字符集，总有最大的word，这个就是老大，其他的可以忽略。
: Trick点：第二步，求longest word that consists of at most those letters。这样
: 使得字符集之间的运算成为可能。
: 之后就是一般人很怕的2^|a| 的dp逐渐从size为1的build起来。
: 但在|a|不大and/or字母组合多了以后逐渐稀疏 (例如同时用到7个不同字母的单词数远
: 远小于 |a|^7) 的时候，一般达不到2^|a|这么多。
|
M**********7
发帖数: 378 | 23 感觉面试就是观察一个人工作中实战的过程。所以就要多秀点和少漏洞。
个人感觉这道题秀点不多。
就这几个：
1. 想到用字符集判断交互；
2. 想到求反的字符集求法和运算方法；
3. 想到逐步拼接的方法。（这里考一个实际应用中exp(k)的复杂度不一定坏）。
所以估计上这个方法还是有必要的。也可以只用1写，然后后面的在完成以后说说2,3。
其实这题1的主循环不难写，估计也就10行左右，所以再加写个3好像不是很难。
2^a的数组的写法就按Quora上的就可以了，没什么花俏，难度上远没有LIS和KMP大：没
细节没trick就是简单的DP向上累记。
法？
【在 b******i 的大作中提到】
: 谢谢详细的解释，
: 但是真的面试的时候遇到这题，难道就要上这个方法吗，比如2^a长度的数组怎么写法？
|
e********2
发帖数: 495 | 24 有个优化就是，如果当前串distinct字母数是n，那么就找distinct字母数<=26-n的串，
而不用和所有的串比较。
【在 i*********e 的大作中提到】
: 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
: 一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
: 上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
: 。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
: 想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
: 了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
: 时间已经不够写代码了。
: 想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
: 我的感觉是没有的。当然，我可能是错的。
: 教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
|
e********2
发帖数: 495 | 25 This should be the optimal:
Map[] maps = new Hashmap[26];
for(String s : strings){
// aabbcd then n = 4
int n = distinct characters in s;
// aabbcd then binary representation is 0b111100000000000000
int m = s's bit pattern;
// maps[n-1].get(m) stores the longest string with the same set
// of distinct chars
Integer maxlength = maps[n-1].get(m);
maps[n - 1].put(m, maxlength == null ? s.size() : Math.max(s.size(), max
length));
}
for(String s : strings ){
int n = distinct characters in s;
for(int i = 0; i <= 26 - n; ++i)
find s.size() * maps[i].keySet() and max value;
}
串，
【在 e********2 的大作中提到】
: 有个优化就是，如果当前串distinct字母数是n，那么就找distinct字母数<=26-n的串，
: 而不用和所有的串比较。
|
