问个Google的面经问题

原帖地址:mitbbs

大家好,问个Google问题,List> lists,Pair有两个属性,id和String型
的value,不同lists相同id的Pair可能value不同,最后要求在所有lists都出现的id的
List,相当于求intersection。所以返回类型是List>>,每个Pair对应id和a list of values。然后follow up是如果这个
intersection function如果call多次的话怎么优化?然后这个follow up加了额外的条
件是,有billions of lists,每次intersection求的是其中的subset的intersection
。我想到的方法是cache住已经计算过的subset的intersection,但是怎么设计key,然
后怎么通过key来lookup cache。但是感觉这个key也太难设计了,不知道大家有什么方
法?多谢啦