一亩三分地论坛

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

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

[算法题] 请教一道Epic的老题目

[复制链接] |试试Instant~ |关注本帖
willran168 发表于 2014-12-8 00:38:42 | 显示全部楼层 |阅读模式

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

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

x
不是我面到的,是往年翻出来的题:

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来完成这个需求?


suonan 发表于 2014-12-8 01:19:46 | 显示全部楼层
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), 不知道对不对
回复 支持 反对

使用道具 举报

LiamZhu 发表于 2014-12-8 10:25:57 | 显示全部楼层
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操作

回复 支持 反对

使用道具 举报

babysor 发表于 2014-12-8 13:44:53 | 显示全部楼层
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)但少了一些查询时间,平均更好。


回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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