0
\$\begingroup\$

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 ArrayList elements (Strings, for now. Could be integers as well) inside the bigger ArrayList. Previously, I have seen codes of finding the intersection of separate ArrayLists, but not sure how I could do it inside the same ArrayList.

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

public class Test {

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

        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.

\$\endgroup\$
4
  • \$\begingroup\$ As it appears, if each element of a List is a List itself, you can call intersection in a loop like you might calculate the sum of elements in a List<Integer>. \$\endgroup\$ Commented Jul 15, 2017 at 13:04
  • \$\begingroup\$ Also, your question looks to be about code not yet written, and this site is not for coding advice in general. You might want to try StackOverflow. \$\endgroup\$ Commented Jul 15, 2017 at 13:05
  • \$\begingroup\$ Plus, are you sure you wanted intersection's type parameter to be named String? \$\endgroup\$ Commented Jul 15, 2017 at 13:06
  • \$\begingroup\$ BTW, I'm pretty sure the idea behind the question is an application of Mathematical Induction. \$\endgroup\$ Commented Jul 15, 2017 at 13:08

1 Answer 1

Reset to default
1
\$\begingroup\$

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 <String> List<String> intersection(List<String> list1, List<String> list2) {
    List<String> list = new ArrayList<String>();

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

    return list;
}

It should have been written like this:

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

    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?
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.