Using Java Pseudo code or a step by step description of an algorithm answer the

Question

Using Java Pseudo code or a step by step description of an algorithm answer the following

Given document D, which can be viewed as an un-ordered numbered list of words, an inverted file is an ordered list of words L, such that, for each word w in L, we store the indices of the places in D where w appears. Design an efficient algorithm for constructing L from D and an efficient underlying data structure.

Like a map, a multi-map stores entries that are a key-value pair (k, v), where k is the key and v is the value. Whereas a map insists that entries have unique keys, a multi-map allows multiple entries to have the same key, much like an English dictionary, which allows multiple definitions for the same word. That is we will allow a multi-map to contain entries (k, v) and (k, v') having the same key.

Now, design an efficient multi-map data structure for storing n entries whose m distinct keys having a distinct hash code, and m < n. Your data structure should perform the following operation in O(1) time.

get(k) : return a collection of all values associated with key k

put(k, v) add a new entry to your multi-map

remove(k, v) remove an entry

removeAll(k)

Explanation / Answer

//MapClassesDemo.java

import java.util.Collection;

import java.util.HashMap;

import java.util.Iterator;

import java.util.LinkedHashMap;

import java.util.Map;

import java.util.Set;

import java.util.TreeMap;

public class MapClassesDemo

{

public static void main(String args[])

{

HashMap hm = new HashMap();

LinkedHashMap lhm = new LinkedHashMap();

TreeMap tm = new TreeMap();

hm.put("Tom", new Double(4000.00));

hm.put("John", new Double(3500.50));

hm.put("Smith", new Double(2125.25));

lhm.put("Tom", new Double(4000.00));

lhm.put("John", new Double(3500.50));

lhm.put("Smith", new Double(2125.25));

tm.put("Abc", new Double(4000.00));

tm.put("Cbc", new Double(3500.50));

tm.put("Bbc", new Double(2125.25));

System.out.println("hm elements : "+hm);

System.out.println("lhm elements : "+lhm);

System.out.println("tm elements : "+tm);

//Getting the set of keys and getting the iterator

Set set = hm.keySet();

Iterator hmitr = set.iterator();

System.out.println(" The Account balance hm Account holders:");

while(hmitr.hasNext())

{

Object key = hmitr.next();

Object value = hm.get(key);

System.out.println(key +" : "+ value);

}

System.out.println();

System.out.println(" The Account balance of lhm Account holders:");

//Getting the set of Entries and getting Iterator

Collection lhmcol = lhm.values();

Iterator lhmitr = lhmcol.iterator();

while(lhmitr.hasNext())

{

System.out.println(lhmitr.next());

}

System.out.println();

System.out.println(" The Account balance of tm Account holders:");

//Getting the set of Entries and obtaining Iterator

Set tmset = tm.entrySet();

Iterator tmitr = tmset.iterator();

while(tmitr.hasNext())

{

Map.Entry me = (Map.Entry)tmitr.next();

System.out.print(me.getKey() + ": ");

System.out.println(me.getValue());

}

double balance = ((Double)hm.get("John")).doubleValue();

hm.put("John", new Double(balance + 1000));

System.out.println("John's new balance: " + hm.get("John"));

}

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.