CODEWITHSUNDEEP
javaarraylist
coderWorld
coderWorld

Reputation: 642

Instead of intersecting two lists how to intersect more than two?

So the structure is {{Dog,Cat,Human},{Human,Dog,Whale,rabbit,Cow},{Monkey,Human,Dog}}.

Output should be: Dog,Human.

I have to find the intersection of List elements inside the bigger List. Previously, I have seen codes of finding the intersection of separate ArrayLists, but not sure how I could do it inside the same ArrayList (more than two).

For separate ArrayLists a code like the following works. But how do I make it work for multiple ArrayLists inside one bigger ArrayList? I was asked this in an interview. Worked for separate lists, but couldn't chalk it out for the same ArrayList.

The interviewer explicitly stated to work only with Strings, so I modified my Generic type tokens from {<T>} to {<String>} after the clarification.

public class Test {

    public <String> List<String> intersection(List<String> list1, List<String> list2) {
        List<String> list = new ArrayList<>();

        for (String t: list1) {
            if(list2.contains(t)) {
                list.add(t);
            }
        }

        return list;
    }
public static void main(String[] args) throws Exception {

        List<String> list1 = new ArrayList<String>(Arrays.asList("Dog", "Cat", "Human"));
        List<String> list2 = new ArrayList<String>(Arrays.asList("Human", "Dog", "Whale", "rabbit", "Cow"));

        System.out.println(new Test().intersection(list1, list2));

    }
}

This produces correct output for two separate ArrayLists. However, in case the input is slightly modified, for e.g., the intersection method will return a,a,a for the input a,a,a and a,a, but it will give a,a for the input a,a and a,a,a. The logical assumption would be that it should always return a,a regardless of the order of parameters.

Any suggestions as to how I could fix this irrespective of the input order? And how I could find the intersection of several lists (more than two) inside a single bigger list?

Upvotes: 2

Views: 317

Answers (4)

PotatoManager
PotatoManager

Reputation: 1775

All you need to do is call the intersection method repeatedly in this fashion-

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
public class HelloWorld{

 public static void main(String []args){
    List<String> list1 = new ArrayList<String>(Arrays.asList("Dog", "Cat", "Human"));
    List<String> list2 = new ArrayList<String>(Arrays.asList("Human", "Dog", "Whale", "rabbit", "Cow"));

    List<List<String>> lists=new ArrayList<List<String>>();

    lists.add(list1);
    lists.add(list2);
    Iterator<List<String>> iterator=lists.iterator();
    List<String>intersect=null;
    while(iterator.hasNext()){
        List<String> current=iterator.next();
            if(intersect==null){
              intersect=current;
            }
            else{
                intersect=intersection(intersect,current);
            }
    }
    System.out.println(intersect);
}

public static List<String> intersection(List<String> list1, List<String> list2) {
    List<String> list = new ArrayList<>();

    for (String t: list1) {
        if(list2.contains(t)) {
            list.add(t);
        }
    }

    return list;
}

}

Upvotes: 1

Nir Alfasi
Nir Alfasi

Reputation: 53565

You can intersect the lists using Stream and filter:

List<String> list1 = new ArrayList<String>(Arrays.asList("Dog", "Cat", "Human"));
List<String> list2 = new ArrayList<String>(Arrays.asList("Human", "Dog", "Whale", "rabbit", "Cow"));
System.out.println(list1.stream()
            .filter(list2::contains)
            .collect(Collectors.toList()));

OUTPUT:

[Dog, Human]

Upvotes: 2

Carcigenicate
Carcigenicate

Reputation: 45836

Assuming intersection works, just fold the list of lists using intersection:

List<ArrayList<String>> lists = /* Lists of lists here */;

List<String> finalIntersection =
    lists.stream()
        .reduce(intersection)
        .collect(Collectors.toList())

Untested, but providing the type of intersection matches what reduce expects, and reduce has an overload that allows for the accumulator to start as the first element, it should work.

Unfortunately, this solution is bloated due to Java only having a reduce method for streams. In Clojure (another JVM language), a roughly equivalent snippet of code would simply be:

(reduce intersection lists)

Which is just lovely.

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727137

Intersection is associative, you can implement intersection of two lists, and then apply the same algorithm repeatedly to the remaining lists.

Java provides a built-in way of doing an intersection through retainAll operation:

List<String> a = ...
List<String> b = ...
List<String> c = ...
List<String> intersection = new ArrayList<>(a);
intersection.retainAll(b);
intersection.retainAll(c);

Upvotes: 6

Related Questions