Find the intersection of ArrayList elements inside an ArrayList
Approaching programming interview questions

One of the most important things during programming interviews is clarifying the problem.
If the task is intersection of lists as opposed to sets,
an important question is how to handle duplicate values.

For example, the current implementation is buggy.
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.
Then again, you should not just assume things,
you should ask for the expected behavior,
or at least state your assumptions loud and clear.

And if there can be no duplicates in the inputs,
then why aren't they sets instead of lists?

Why is ArrayList specified instead of just List?
ArrayList is a specific implementation,
when List is the general concept.

Generic type tokens

String, the name of a common class in the JDK,
and written in PascalCase,
is a terrible choice for a generic type token in this code:


public &lt;String&gt; List&lt;String&gt; intersection(List&lt;String&gt; list1, List&lt;String&gt; list2) {
    List&lt;String&gt; list = new ArrayList&lt;String&gt;();

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

    return list;
}



It should have been written like this:

public static &lt;T&gt; List&lt;T&gt; intersection(List&lt;T&gt; list1, List&lt;T&gt; list2) {
    List&lt;T&gt; list = new ArrayList&lt;&gt;();

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

    return list;
}


Intersection of many lists


  But how do I make it work for multiple ArrayLists inside one ArrayList?


I'm not sure I get what's blocking you.
Perhaps you mean, instead of the intersection of 2 lists,
how to intersect more than 2?

In that case,
that's an interesting question to discuss about,
and consider different alternatives,
starting from simple (brute force) techniques,
and then trying to improve.

Simple solution: if you have n lists, you could intersect the first 2,
then intersect the result with the 3rd,
then intersect the result with the 4th,
and so on, until the last.
The final result will be the intersection of all the lists,
reachable in n - 1 steps.

Is it possible to do better?


Hint 1: consider the concept of divide and conquer.
Hint 2: how does merge sort work?