3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Mar 12, 2012 at 23:33
  • \$\begingroup\$ @CarlManaster thanks. for the feedback. Anyone have ideas on how to optimize this code? \$\endgroup\$
    – stevebot
    Mar 13, 2012 at 0:20

2 Answers 2

3
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

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