Given large set of files, design a system to efficiently handle a query like:
Find all files that have these words and doesn’t have these words.
Followup optimization question:
Can you make it efficient for queries that involve words which are common across most files (not all) and not frequently queried.
先clarify一下题意并加上自己的一些假设：1. 文件都是是按数字编号的，内容完全由英文单词构成 2. 一个query包含一个或多个单词，并以AND逻辑连接 3. 符合query的结果按文件编号全部返回（剩下的就是不包含这些word的）
单机版：
存放查询所需的数据结构：用类似HashMap的结构，key是单词字符串，value是存放文件编号的list，对每个文件，用HashSet存放出现过的单词，再遍历hashset中元素来update HashMap中的value。 假设N为文件数量，M为平均一个文件包含的单词，再假设单词数为W ，则总共需要的空间最多为O(W * N) , 建HashMap的时间复杂度为： 遍历文件的时间 + 遍历HashSet 并update HashMap value的时间O(N * M)
查询算法： 对query中包含的每个单词（假设query中有Q个单词），在hashmap中查询其对应的value分别得到一个list，假设平均长度为L，对这些list求公共的intersection 得到最后的文件编号的list (可以两两一求)需要的时间为O(Q * L), 每次求intersection需要的额外空间之和是O（Q * L）
需求变化：1. 如果query中出现的单词，只要包含一个或以上就返回，则把intersection那一步改成求并集，空间时间复杂度不变。 2. 如果要求返回排名前K（比如前100）条结果，则不仅需要每个单词出现的文件编号还需要出现频率，可以直接去掉上面建HashMap过程中用HashSet存放出现过的单词这一步，每出现一次就记录一次文件编号。（如果一个单词出现频率很高，这样的存储过于低效，可以考虑类似string compression的方法对value list重新编码。）
分布式方案：文件数量很多时，采用map-reduce的方法，在map阶段切分文件集，如果按照固定长度切割，切割点有可能落在某个文件中间，导致文件中不同单词出现在不同的chunk里，reduce结果的时候需要先按单词汇总，再对各个单词的list做并集或者交集
follow up：对于大多数文件中都出现但又不是经常被搜索到的单词(e.g. “the”, “and”, etc)，可以改为存不包含该词的文件编号
你的答案比较可惜的是我没看到 bloom filter 的提出，这个我们在第一课讲了，可以去看下
可以认为文件有ID的，如果这是你的意思。 ID 也可以是 String，即 UUID，不一定是数字。
我们第一课说到了checksum或digest的概念，D老师也重复提了。这个点也很重要。
这题似乎单机版意义不大 
感觉答偏了，你说的是文件系统的存储，但这里重点是查询
可以增加缓存，存的其实是不出现这些单词的文件，即补集。因为不太会变，这个存储是static的。
把文件存储在一个分布式文件系统里面。然后在一个host或者数据库上build一个索引来存储word->FileUUID的Mapping，这个mapping是map所有的file和word的
查询的时候先通过找到这几个需要存在的word对应的文件，在这些文件里面再用bloomfilter筛掉存在那些不应该存在的words
这个细节是什么？