Can you please help me out of here

Question

0.00/5 (No votes)

See more:

Hi all,

Suppose you need to determine whether two ArrayLists are equal except you don't care whether the orders of the elements in the two lists are the same. Here is one method that purportedly solves this problem:

Java

    public boolean specialArrayListEquals(ArrayList a1, ArrayList a2){
    	boolean result = true;
    	a1 = new ArrayList(a1);  //create a clone of a1
    	a2 = new ArrayList(a2);  //create a clone of a2
if(a1.size() == a2.size()) {
    		for(int i = 0; ((i < a1.size()) && (result == true)); i++){
    			Object o = a1.get(i);
    			result = a2.contains(o);
    			if(result){ // remove the equal elements from both
    				a1.remove(o);
    				a2.remove(o);
    			}
    		}
    	}
    	return result;
    }

Debug this code, list everything you can think of that makes this code inelegant, and then come up with an elegant solution to the problem. Can you come up with an even more elegant solution if you know that there are no duplicate elements (that is, no two equal elements) in each ArrayList?

Thanks
sujan.

Posted 3-Nov-11 18:21pm

V V S GANGA SUJAN

Updated 3-Nov-11 19:08pm

P.Salini

v2

Add a Solution

Comments

nagendrathecoder 4-Nov-11 1:25am

Use question heading related to actual topic.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2011-11-03T18:46:00

The solution you show is also ineffective as the methods remove and contain works at the speed of O(n). (For understanding "Big O Notation", see http://en.wikipedia.org/wiki/Big_O_notation[^].)

Speed considerations and the no-duplicate constrain suggest the use of java.util.Hashtable, see http://download.oracle.com/javase/1.4.2/docs/api/java/util/Hashtable.html[^] at the expense of some memory overhead. For big collections, this class provides the speed about O(1) (no dependency on the size of collection, constant search time for big collections).

You can populate an instance of hash table from one list and try to find the elements of another list one by one. The rest of this algorithm is simple, so I would leave to for your home exercise :-).

—SA