一亩三分地论坛

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

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

好像跪了

[复制链接] |试试Instant~ |关注本帖
wowo04 发表于 2015-2-5 04:22:59 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Other

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

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

x
//Write a function that will take in email lists and return a new email list that contains only the email addresses that existed in all lists
// 1: foo@amazon.com, bar@amazon.com
// 2: bar@amazon.com, bar@amazon.com
// o: bar@amazon.com

请大家指点一下 求米求安慰. more info on 1point3acres.com

   
   

评分

1

查看全部评分

ekco 发表于 2015-2-5 05:33:01 | 显示全部楼层
pat pat. 1point3acres.com/bbs

可以用两个rolling hashset,第一个装email lists[0]里的email,然后遍历剩余的每个email list,check该email是不是在第一个set中,如果在就加入到第二个set,遍历结束两个set互换,清空第二个set,然后继续下一个list
回复 支持 2 反对 0

使用道具 举报

lenss 发表于 2015-2-5 04:36:12 | 显示全部楼层
pat pat, 用 hashmap or sort?
回复 支持 反对

使用道具 举报

池大侠 发表于 2015-2-5 05:06:16 | 显示全部楼层
感觉像leetcode 里面求longest prefix
我这样做你看看可以么
def finddup(lists):
    if len(lists)==1:
        return lists[0]
  
    newlist=lists[0]
    for i in range(1,len(lists)):. more info on 1point3acres.com
        for j in newlist:
            if j not in lists[i]:
.鏈枃鍘熷垱鑷1point3acres璁哄潧                newlist.remove(j). more info on 1point3acres.com
                if not newlist:
                    return None
    return newlist. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            
   
        
        
            

def main():
    lists=[['bar@amazon','foo@amazon','cat@amazon'],['bar@amazon','foo@amazon'],['bar@amazon','coo@amazon']]
    finddup(lists)
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
if __name__=="__main__":
    main()
回复 支持 反对

使用道具 举报

池大侠 发表于 2015-2-5 05:36:09 | 显示全部楼层
ekco 发表于 2015-2-4 20:33
pat pat

可以用两个rolling hashset,第一个装email lists[0]里的email,然后遍历剩余的每个email list ...

其实可以check 如果第一个list里面的email 不在下一个 就直接pop 掉 应该也可以哦。。 不过好像不同语言这种删除啊 pop的消耗时间不同
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-2-5 05:43:39 | 显示全部楼层
感觉用两个hashset就可以了,滚动更新
回复 支持 反对

使用道具 举报

ekco 发表于 2015-2-5 05:50:46 | 显示全部楼层
池大侠 发表于 2015-2-4 16:36
其实可以check 如果第一个list里面的email 不在下一个 就直接pop 掉 应该也可以哦。。 不过好像不同语言 ...

用set的话,时间复杂度是O(m*n), m个list,n个email per list。

假如pop都是O(1)的话,查看第一个list中email是不是在下一个list是O(n), 遍历第一个list需要O(n^2), 要check m 个list,总共O(m*n^2)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

池大侠 发表于 2015-2-5 06:24:16 | 显示全部楼层
ekco 发表于 2015-2-4 20:50
用set的话,时间复杂度是O(m*n), m个list,n个email per list。

假如pop都是O(1)的话,查看第一个list ...

对哦。。。那我应该把握的那个list【0】 放到hash里面。。
回复 支持 反对

使用道具 举报

ekco 发表于 2015-2-5 06:32:55 | 显示全部楼层
池大侠 发表于 2015-2-4 17:24
对哦。。。那我应该把握的那个list【0】 放到hash里面。。

假如只是一个set的话,还是要遍历整个set来对其更新,所以复杂度还是O(m*n^2)
回复 支持 反对

使用道具 举报

ChristLee 发表于 2015-2-5 06:50:55 | 显示全部楼层
kurtwang 发表于 2015-2-5 05:43.1point3acres缃
感觉用两个hashset就可以了,滚动更新

你有A家消息了没啊
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-2-5 06:56:54 | 显示全部楼层
ChristLee 发表于 2015-2-5 06:50. 鍥磋鎴戜滑@1point 3 acres
你有A家消息了没啊

还没呢。。估计最快也要下周吧
回复 支持 反对

使用道具 举报

bjik 发表于 2015-2-5 07:02:27 | 显示全部楼层
lz面试官是硬度人吧?
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-2-5 07:53:03 | 显示全部楼层
只有两个list么。。。
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-2-5 08:04:30 | 显示全部楼层
ekco 发表于 2015-2-5 06:32. 1point 3acres 璁哄潧
假如只是一个set的话,还是要遍历整个set来对其更新,所以复杂度还是O(m*n^2)

请教一下N^2怎么来的
回复 支持 反对

使用道具 举报

ekco 发表于 2015-2-5 13:19:19 | 显示全部楼层
甯甯 发表于 2015-2-4 19:04
请教一下N^2怎么来的

因为只有一个set,要对它update的话,要遍历set看每个email是否在下一个list中,不在从set中删除
回复 支持 反对

使用道具 举报

yangbin009 发表于 2015-2-5 17:03:01 | 显示全部楼层
是否可用hashmap+hashset?map存全体email和count。对每一list,用set保证相同email只出现一次,然后把set里所有的元素加到map里同时count+1,然后重置set,进行下一个list。最后遍历map,只有count等于list数量的时候,把这个key加到结果集里面。
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2015-2-6 01:24:36 | 显示全部楼层
  1.         public static ArrayList<String> findEmail(ArrayList<ArrayList<String>> in){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.                 ArrayList<String> res= new ArrayList<String>();
  3.                 if(in.size() == 0) return res;. From 1point 3acres bbs
  4.                 HashSet<String> set = new HashSet<String>();. 1point3acres.com/bbs
  5.                 for(int i=0;i<in.get(0).size();i++) set.add(in.get(0).get(i));
  6.                 for(int i=1;i<in.size();i++){
  7.                         HashSet<String> tmp = new HashSet<String>();
  8.                         ArrayList<String> cur = in.get(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.                         for(int j=0;j<cur.size();j++){
  10.                                 if(set.contains(cur.get(j))) tmp.add(cur.get(j));
  11.                         }
  12.                         set = tmp;. 1point 3acres 璁哄潧
  13.                 }
  14.                 for(String s:set) res.add(s);. from: 1point3acres.com/bbs
  15.                 return res;
  16.         }
复制代码
复杂度就是所有list里面email的个数。.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-3-6 09:09:54 | 显示全部楼层
ekco 发表于 2015-2-5 06:32
. 1point 3acres 璁哄潧假如只是一个set的话,还是要遍历整个set来对其更新,所以复杂度还是O(m*n^2)

不好意思回个老帖。但是现在在准备amazon,这里实在是不理解。
java的hashset remove操作应该是O(1)时间复杂度才对,为什么是O(n)呢?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-3-8 17:33:59 | 显示全部楼层
看楼上讨论复杂度都是m*n^2的,我给一个m*n的吧....类似倒排索引,对每个邮箱建一个hashmap,value是List<Integer>表示他出现在那几行,最后统计所有等于行数的单词
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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