2

I was asked in an interview this question

LinkedList A has {1,2,3,4,5,6}

LinkedList B has {1,3,5}

I needed to write a method which would return back a Set which does not contain the duplicate elements in list A and B

result { 2,4,6}

I wrote a solution which would iterate over first list and if it does not exist in the second list then add it to a HashSet. But need a solution which performs better than the suggested Algorithm.

No space constraint mentioned for solving this.

Would definitely like a solution using JDK ,but would prefer a solution which is algorithm based

Thanks a ton

Improve this question
1
  • Take a look at this blog post that has an analysis of the various removeAll() implementations Commented Nov 8, 2011 at 3:57

4 Answers 4

Reset to default
4

The standard solution is to loop through the first list and put everything in a hash table. This is linear time since inserting into a hash table is constant time.

Then loop through the second list and look to see if each element exists in the hash table. If it exists, delete it from the table. Else, add this item to a new list.

Now append everything left in the hash table to the new list.

This second operation is also linear since lookup and deletion are also constant for hash tables. Thus, the overall algorithm is linear.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

It's worth adding that this is not exactly linear time, but the average case is linear time. See: Average Case Complexity
@dahunter Because it depends on the hashing function?
1

The thing is depending on which position you're interviewed. They probably were interested in your logic. One of possible solution is to start with a simple method:

public Set<Integer> killDuplicates(LinkedList<Integer> a0, LinkedList<Integer> a1) {
        Set<Integer> common = new HashSet<Integer>();
        common.addAll(a0); //one could pass thru constructor, no matter
        common.retainAll(a1);
        Set<Integer> result = new HashSet<Integer>();
        result.addAll(a0);
        result.addAll(a1);
        result.removeAll(common);
        return result;
    }

But still this could be dramatically slow in some cases, and there are very many ways to improve speed of this code. One of possible solutions is to use special structures for fast set intersection.

Sorting is good, but since we have data in LL it would use merge sort (additional memory written in pseudo code but feel free to ask questions):

public Set<Integer> killDuplicatesSorted(...) {
    //sort a0
    //sort a1
    Iterator i0 = a0.getIterator();
    Iterator i1 = a1.getIterator();
    while (i0 != end && i1 != end) {
        if (i0.current == i1.current) {
            //skip presented in both
            i0.moveNext();
            i1.moveNext();
        } else if (i0.current < i1.current) {
            result.add(i0.current);
            i0.moveNext();
        } else {
            result.add(i1.current);
            i1.moveNext();
        }
    }
    while (i0 != end) {result.add(i0.current); i0.moveNext();}
    while (i1 != end) {result.add(i1.current); i1.moveNext();}
    return result;
}
Improve this answer

2 Comments

Merge sort takes O(n * log (n) ) time. Sorting in linear time is not possible since the OP did not mention whether or not we could use counting sort or radix sort.
Merge sort is probably the best way to solve this problem. Suppose L1 is composed of very large numbers(ie. 1.XXXX * pow(2, 30+)). Then, any really good hash function will take Order(bit-sizeof(verylargenumber)). So the hashing function solution will take more then O(N) time , rather it take will 0(non-linear time). So, in some cases involving very large numbers the mergesort answer might beat the hashing solution.
0 
    Integer[] a1 = {1,2,3,4,5,6};
    Integer[] a2 = {1,3,5,8};

    LinkedList<Integer> ll1 = new LinkedList(Arrays.asList(a1));
    LinkedList<Integer> ll2 = new LinkedList(Arrays.asList(a2));

    Set<Integer> set1 = new HashSet<Integer>(ll1);
    Set<Integer> set2 = new HashSet<Integer>(ll2);
    set1.removeAll(ll2);
    set2.removeAll(ll1);
    set1.addAll(set2);

    System.out.println(set1);

removeAll() is subsrtaction and addAll() is union of sets.

Improve this answer

4 Comments

This would give me output {1,2,3,4,5,6,8} but i want the output as {2,4,6,8}
@bhargava Sorry, i didn't understand you right away. I fixed code.
So is this a constant time solution? The reason why i think so is that add and remove operations in hashset are constant time assuming hashcode is properly implemented
I'm not sure. Set<Integer> set1 = new HashSet<Integer>(ll1); Use iterator of LinkedList. It's seems that list iterator has O(n). May be i'm wrong.
0

In Scala, as previously described, uses an internal map, then loops

scala> val x = (1 to 6).toList
x: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> val y = (1 to 5 by 2).toList
y: List[Int] = List(1, 3, 5)

scala> val result = x.diff(y).toSet
result: scala.collection.immutable.Set[Int] = Set(2, 4, 6)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.