Question

public static BagInterface<String> intersection (BagInterface<String> bagA, BagInterface bagB)

This method must return a new bag which is the intersection of the two bags: bagA and bagB. An element appears in the intersection of two bags the minimum of the number of times it appears in either. For example, {1,1,2} ∩{1,1,2,2,3}= {1,1,2}. Do not forget to state the big Oof your method implementation.

two file java main and test

by netbeans java

data structure and algorithem

Answer 1

Please find the code below,

BagInterface.java

import java.util.*;

public class BagInterface {

    private List<Integer> data;

    public BagInterface(){
        data = new ArrayList<>();
    }

    public void addItem(int item){
        data.add(item);
    }

    public void addAllItems(List<Integer> items){
        data.addAll(items);
    }

    public BagInterface intersection(BagInterface bagA){
        BagInterface bagB = this;
        Map<Integer, Integer> freqMap = new HashMap<>();
        for(Integer item : bagA.data){
            freqMap.put(item, freqMap.getOrDefault(item, 0)+1);
        }
        BagInterface result = new BagInterface();
        for(Integer item : bagB.data){
            if(freqMap.containsKey(item)){
                result.data.add(item);
                freqMap.put(item, freqMap.get(item)-1);
                if(freqMap.get(item) == 0) freqMap.remove(item);
            }
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder output = new StringBuilder();
        for(int i=0; i<data.size(); i++){
            output.append(data.get(i));
            if(i != data.size()-1) output.append(",");
        }
        output.insert(0, "{");
        output.append("}");
        return output.toString();
    }
}

RunnerTest.java

import java.util.*;

public class RunnerTest {

    // Testing code
    public static void main(String[] args) {
        BagInterface bagA = new BagInterface();
        bagA.addAllItems(Arrays.asList(1,1,2));

        BagInterface bagB = new BagInterface();
        bagB.addAllItems(Arrays.asList(1,1,2,2,3));

        BagInterface result = bagA.intersection(bagB);
        System.out.println(bagA + " ∩ " + bagB + " = " + result);
    }

}

OUTPUT:

If you have any doubts put in the comments, also do upvote the solution.