mardi 17 septembre 2019

Design pattern for Data Structure - Double sided Map

I have a data structure problem that I am looking for alternative optimal solutions.

I have diseases and their equivalent tablets that form the cure.

List of Diseases - A, B, C, D, E ..

List of Tablets - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...

Each disease has a specified ORDERED list of tablets that form the cure.

Example:

A - 1, 3, 7

B - 9, 2

C - No Tablet can Cure

D - 10, 9, 8, 5

E - 4

These are the ordered cures for the diseases.

Problem statements -

  1. Given any disease, the Data Structure needs to find the list of tablets that form the cure. Example from above: Given,

A - 1, 3, 7

C - No Cure.

  1. Given any tablet, the Data Structure needs to find the list of diseases it can cure (with any order). Example from above: Given,

9 - B, D

4 - E

6 - No disease.

Since the design might be based on the number of tablets and diseases, there can be any number of tablets or diseases, we will for now assume that both are the same number . 10 Tablets and 10 diseases.

The Query patterns are equal for number of tablets and number of diseases.

Solutions I have thought about:

I have thought about having 2 maps with lists. 1 Map for Tablets to Diseases it can cure, and 1 Map for Diseases to Tablets it needs to be cured.

Are there any more efficient solutions that can utilise lesser space than 2 Maps and have the same time complexity or be more efficient than traversing the entire list for either of tablet or disease query.

Any other efficient way to solve using Bin Trees, Graphs, Trie?

Aucun commentaire:

Enregistrer un commentaire