current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

Problem: Find the intersection of two Object arrays without creating any new classes (no anonymous classes either) and without using any native Java classes in the solution (so no ArrayList implementations etc., but Object can be used)

My solution:

public Object[] handleArrayIntersection(Object[] array1, Object[] array2) {
    if(array1.length == 0 || array2.length == 0){
        return new Object[0];
    }
    // the maximum possible number of intersections is the smaller array's size
    int maxPossibleLength = array1.length < array2.length ? array1.length : array2.length;
    Object[] intersectionValues = new Object[maxPossibleLength];
    int itemCount = 0;
    for(int i = 0; i < array1.length; i++){
        Object arr1Val = array1[i];
        if(contains(array2, arr1Val) && !contains(intersectionValues, arr1Val)){
            intersectionValues[itemCount] = arr1Val;
            itemCount++;
        }
    }

    // reduce the array down to only contain the intersections
    Object[] intersection = new Object[itemCount];
    for(int i = 0; i < itemCount; i++){
        intersection[i] = intersectionValues[i];
    }
    return intersection;
}


public boolean contains(Object[] newArr, Object arr1Val) {
        boolean contains = false;
        for(int i = 0; i < newArr.length; i++){
            Object val = newArr[i];
            if((val == null && arr1Val == null) || (val != null && val.equals(arr1Val))){
                contains = true;
                break;
            }
        }
        return contains;
}

I haven't tried to solve this type of problem for awhile and I am really curious what people think of this solution in terms of efficiency, robustness and readability. I arrived at this solution by using TDD (Test Driven Development), but I'm not including the test because I'm more interested in people reviewing the solution.

share|improve this question
2  
Except for renaming the parameters of contains(), this looks OK to me. I would also simply "return true" from inside the loop and "return false" after the loop completes, instead of keeping the contains variable around; it's not really serving much of a purpose. –  Carl Manaster Mar 12 '12 at 23:33
    
@CarlManaster thanks. for the feedback. Anyone have ideas on how to optimize this code? –  stevebot Mar 13 '12 at 0:20
add comment

2 Answers

up vote 3 down vote accepted

If you want to optimize you can : Use arrayCopy() from the System Class to create the final array and reduce variable. Here is my "solution" : 

public static Object[] handleArrayIntersection(Object[] array1, Object[] array2) {
    Object[] dest;

    int itemCount = 0;
    Object[] intersect = new Object[array1.length < array2.length ? array1.length : array2.length];

    for(int i = 0; i < array1.length; i++) {
        Object arr1Val = array1[i];
        if(contains(array2, arr1Val) && !contains(intersect, arr1Val)) {
            intersect[itemCount++] = arr1Val;
        }
    }

    dest = new Object[itemCount];
    if(itemCount > 0) {
        System.arraycopy(intersect, 0, dest, 0, itemCount);
    }

    return dest;
}
share|improve this answer
add comment
up vote 2 down vote

You should iterate through the smallest array. If array1 is very much larger than array2 then most of the elements are unlikely to be in array2 and the contains test is more likely to be false.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.