S*******C
发帖数: 822 | 1 //Write a function that takes in email lists and results in a new email list
that contains only the email addresses that are in all lists
// List1(kindle) : [email protected]
/* */
// List2(aws) : [email protected]
/* */, [email protected]
/* */
// List3(videogames): [email protected]
/* */, [email protected]
/* */, [email protected]
/* */
// Output : {}
//[email protected]
/* */ == [email protected]
/* */
//foo=FOO?
//String.ToLowerCase();
//[email protected]
/* */ => [email protected]
/* */, [email protected]
/* */ => [email protected]
/* */ |
h******i
发帖数: 282 | 2 Brute force 的方法是不是就用循环依次比较是否相同，在比较时先全转为lower case
的String.
这比较慢，O（nm)
还可以用Map Reduce 平行查找 |
S*******C
发帖数: 822 | 3 循环比较的话是多重循环，而不是双层循环，这样时间复杂度很高
case
【在 h******i 的大作中提到】
: Brute force 的方法是不是就用循环依次比较是否相同，在比较时先全转为lower case
: 的String.
: 这比较慢，O（nm)
: 还可以用Map Reduce 平行查找
|
s********l
发帖数: 998 | 4 用2个hash set
所有的list都走一遍就好了
【在 S*******C 的大作中提到】
: 循环比较的话是多重循环，而不是双层循环，这样时间复杂度很高
:
: case
|
S*******C
发帖数: 822 | 5 你要用set.retainAll方法？
【在 s********l 的大作中提到】
: 用2个hash set
: 所有的list都走一遍就好了
|
s********l
发帖数: 998 | 6 我没想用这个啊~
【在 S*******C 的大作中提到】
: 你要用set.retainAll方法？
|
S*******C
发帖数: 822 | 7 那能具体说一下你的思路吗
【在 s********l 的大作中提到】
: 我没想用这个啊~
|
k*******q
发帖数: 5493 | 8 两个HASHSET 一个叫LAST 一个叫CUR
把第一个LIST放进LAST
然后遍历 2 - N 的LIST，每次把 LAST 里出现在新LIST里的 加进 CUR SET
每次循环结束时 LAST = CUR 这样LAST里面的内容会越来越少
到最后就是出现在所有LIST里的邮件了
边吃早饭边想的，如果有问题，麻烦指出
list
/* */
/* */, [email protected]
/* */
/* */, [email protected]
/* */, [email protected]
/* */
/* */ == [email protected]
/* */
/* */ => [email protected]
/* */, [email protected]
/* */ => [email protected]
/* */
【在 S*******C 的大作中提到】
: //Write a function that takes in email lists and results in a new email list
: that contains only the email addresses that are in all lists
: // List1(kindle) : [email protected]
: /* */
: // List2(aws) : [email protected]
: /* */, [email protected]
: /* */
: // List3(videogames): [email protected]
: /* */, [email protected]
: /* */, [email protected]
|
S*******C
发帖数: 822 | 9 这个不对啊
【在 k*******q 的大作中提到】
: 两个HASHSET 一个叫LAST 一个叫CUR
: 把第一个LIST放进LAST
: 然后遍历 2 - N 的LIST，每次把 LAST 里出现在新LIST里的 加进 CUR SET
: 每次循环结束时 LAST = CUR 这样LAST里面的内容会越来越少
: 到最后就是出现在所有LIST里的邮件了
: 边吃早饭边想的，如果有问题，麻烦指出
:
: list
: /* */
: /* */, [email protected]
|
s******7
发帖数: 1758 | 10 map reduce平行两两合并，合并成原来两个list共有的email, mlogn |
|
|
S*******C
发帖数: 822 | 11 这只是intern面试题，不用map reduce怎么解？
【在 s******7 的大作中提到】
: map reduce平行两两合并，合并成原来两个list共有的email, mlogn
|
s******7
发帖数: 1758 | 12 不考虑parallel, 那就O(mn), 依次合并就行了，space上建一个hashset,O(m)
【在 S*******C 的大作中提到】
: 这只是intern面试题，不用map reduce怎么解？
|
S*******C
发帖数: 822 | 13 依次合并怎么实现？
我这里有个解法，但需要用API才可以
【在 s******7 的大作中提到】
: 不考虑parallel, 那就O(mn), 依次合并就行了，space上建一个hashset,O(m)
|
S*******C
发帖数: 822 | 14 我要是实现时间O(N)的算法是不是最优的？
期中N表示所有list中Email的总数
【在 s******7 的大作中提到】
: 不考虑parallel, 那就O(mn), 依次合并就行了，space上建一个hashset,O(m)
|
k*******q
发帖数: 5493 | 15 我写了一下, 可以用的啊
public List findEmails(List> emails) {
List ret = new ArrayList();
if (emails == null || emails.size() == 0) {
return ret;
}
Set last = new HashSet();
for (String s : emails.get(0)) {
last.add(s.toLowerCase());
}
for (int i = 1;i < emails.size(); i++) {
Set cur = new HashSet();
for (String s : emails.get(i)) {
if (last.contains(s.toLowerCase())) {
cur.add(s.toLowerCase());
}
}
last = cur;
}
for (String s : last) {
ret.add(s);
}
return ret;
}
【在 S*******C 的大作中提到】
: 这个不对啊
|
S*******C
发帖数: 822 | 16 可以用，这解法很好
【在 k*******q 的大作中提到】
: 我写了一下, 可以用的啊
:
: public List findEmails(List> emails) {
: List ret = new ArrayList();
: if (emails == null || emails.size() == 0) {
: return ret;
: }
: Set last = new HashSet();
: for (String s : emails.get(0)) {
: last.add(s.toLowerCase());
|
