请教一道Epic的老题目

不是我面到的，是往年翻出来的题：

Suppose N patients and M diseases. N is sufficiently large number and M is relatively small, say 30-ish. Each patient can have possible 0 to M kinds of diseases.

Given one patient’s name, show me a list of similar patients sharing same deseases within 2-3 seconds.


大概要设计一个什么样的data structure来完成这个需求？

M种diease作为hashmap的key， 每种diease的patients作为value，worst case情况下，一个patient有M种diease，查M次O(M)得到M个list，每个list中有N个人，用这M个list提取出uniqte patients的list O(N), 总时间O(MN), 不知道对不对

suonan 发表于 2014-12-8 01:19
M种diease作为hashmap的key， 每种diease的patients作为value，worst case情况下，一个patient有M种diease ...

个人感觉楼上的是对的！
顺便补充一下
其实就是Inverted Index的思想
具体如何建表，以及后面的查找根绝N和M的具体范围有很多不同的方法：
1.最常见的就是直接不排序建表，然后在查找时遍历所有的表项
2.也可以在构建这个表的时候可以先按照patient的编号排序，在查找时采用类似merge的思想
3.在N相对较小的时候可以直接用Bit来存储表项，查找时使用And操作

suonan 发表于 2014-12-8 01:19
M种diease作为hashmap的key， 每种diease的patients作为value，worst case情况下，一个patient有M种diease ...

如何用patient's name 查disease而且每次只需要O(1)，是已经假设patient这个class有disease了?
这道题感觉就是要问清楚提问者上面问题和resource limit如何，假设没有该class，且无resource limit。PS：总觉得类数据库结构B-tree,啥的更省空间，patient name 是单独index，disease是另一个index，entries是patient这个class(含name，diseases)，用logn 时间查patient的disease，然后直接在diseases index上面加patient->set O(nm); 结果也还是 O(nm）。
实际上就是要有个patient的class， 然后一个HashMap<Patient's name, Patient>（浪费n空间也没比patient name as单独index多很多）,然后就按这里说的一个hashmap with disease key对应 30+个List of patients which has the disease as value.一样 O(nm)但少了一些查询时间，平均更好。