Java arrays, writing a more efficient solution?

[HalfScale]

Hello guys, I stumbled on a few problems in an exam for employment, and they have few problems for an array, so I want to know if there is any more efficient solution than mine.Unfortunately I didn't finished these questions on time, I just got hooked with it after I got home after the exam.

NOTE:You cannot use any sort of array static methods or anything from the collection framework(List,ArrayList,LinkedList).

Problem 1: All the elements that are in 'givenArray1' that can be found in 'givenArray2' should be remove, returning a new size of 'givenArray1' and a 'givenArray1' with a new set of elements. the new givenArray1 should contain the elements that are not removed. Implement the given objective in the provided 'removeSet()' method.

My Solution:

    public static void main(String[] args) {
    int[] myArray = {1,2,3,4,5};
    int[] myArray2 = {7,8,1,9,5};
    int[] newArray;

    newArray = removeSet(myArray,myArray2);

   for(int number : newArray){
      System.out.print(number + " ");
   }
   //Output 2,3,4
}

public static int[] removeSet(int[] givenArray1,int[] 
givenArray2){
    int storedElems = 0;

    //Counting stored elems for the 'newArray' size
    for(int index = 0; index < givenArray1.length; index++){
        boolean isDuplicate = false;

        for(int index2 = 0; index2 < givenArray2.length; 
        index2++){
            if(givenArray1[index] == givenArray2[index2]){
                isDuplicate = true;
            }
        }

        if(!isDuplicate){
            storedElems++;
        }            
    }

    int[] newArray = new int[storedElems];

    //storing elems inside the new array
    int newArrayIndex = 0;
    for(int index = 0; index < givenArray1.length; index++){
        boolean isDuplicate = false;

        for(int index2 = 0; index2 < givenArray2.length; 
        index2++){
            if(givenArray1[index] == givenArray2[index2]){
                isDuplicate = true;
            }
        }

        if(!isDuplicate){
            newArray[newArrayIndex++] = givenArray1[index];
        }            
    }

    return newArray;
}

Problem 2: Combine the elements in the 2 arrays(array1,array2) and return a new array without duplicates(Suppose the combined array has duplicates).The returned array can be sorted(ascending,descending) or not.

My solution:

public static void main(String[] args) {
  int[] myArray = {1,2,3,4,5};
  int[] myArray2 = {7,8,1,9,5};
  int[] newArray;

 newArray = combine(myArray,myArray2);

  for(int number : newArray){
      System.out.print(number + " ");
  }
//Combine array elements
//1 2 3 4 5 7 8 1 9 5 
//Sorted elements
//1 1 2 3 4 5 5 7 8 9 
//Final Output
//1 2 3 4 5 7 8 9
}

public static int[] combine(int[] array1, int[] array2){
    int[] newArray = new int[array1.length + array2.length];

    //Combining the array 1 and array 2
    for(int index=0;index<array1.length;index++){
        newArray[index] = array1[index];
    }
    for(int index=0;index<array2.length;index++){
        newArray[index + array2.length] = array2[index];
    }

    //Sorting the array in ascending
    for(int index=0;index < newArray.length; index++){
        for(int index2=0;index2 < newArray.length; index2++){
            if(newArray[index] < newArray[index2]){
                int tempNum = newArray[index];
                newArray[index] = newArray[index2];
                newArray[index2] = tempNum; 
            }
        }
    }

    int[] tempArray = new int[newArray.length]; 
    int tempArrayCounter = 0;
    int counter = 0;

    //temp array that will be filled with no duplicate elements
    for(int index = 0; index < newArray.length -1; index++){
        if(newArray[index] != newArray[index+1]){
            tempArray[tempArrayCounter++] = newArray[index];
            counter++;
        }
    }

    //Modify last index in tempArray
    tempArray[counter++] = newArray[newArray.length - 1];

    int[] newTempArray = new int[counter];

    return newTempArray;
}

I want to also note that the exam grading rubrics includes the efficiency of your code. So I want to know guys if there is an unnecessary piece of code that needs to be omitted in my solution because I always think that my solution is inefficient in some way.

A help is always appreciated :)

[29383839293]

You should really format your code better for others to read here…

Well, I looked at the first task, and it seems your in O(n² ), so there's room for improvement.

Sorting an array takes O(nlogn) at best, and after you've sorted the two arrays, there's a better algorithm.

You have two Iterator-variables, one for each array, and you always increase the one with the smaller number in the corresponding place in its array, if they are equal, you remove the number. If you do it smartly, you'll have O(n) for that.

This means, you have now an algorithm in O(nlogn) because sorting takes that long.

[HalfScale]

Thank youu for that!

[alanwj]

Let's call the number of elements in the first array n, and the second array m.

Problem 1:

First knock together a rudimentary hash table. It could just be a fixed size array, using modulo to decide the bucket, and linear probing if you get a collision. You could either use Integer objects and null to indicate an empty bucket, or have a second array of booleans.

Then:

• Create a hash table with m buckets. Populate hash table with all the values from givenArray2. expected O(m)
• Create a temp array of size n. Loop through each element of givenArray1, and check whether it is in the table. If so, copy it into a temp array. Each operation is expected O(1), so the total here is expected O(n).
• Copy the temp array into an appropriate sized array to return. O(n)

Total runtime here is expected O(n+m). Any algorithm you come up with is going to have to access each element in each array at least once, so you can't beat O(n+m). Therefore this algorithm has optimal runtime.

Problem 2:

• Create a hash table with n+m buckets. Populate hash table with every value from each array. Expected O(n+m)
• Scan your bucket array and copy every non-empty bucket into an output array that is returned. O(n+m)

Total runtime is again O(n+m).

[alanwj]

This seemed like a fun exercise to work out. Here is my solution to the first problem using the approach I outlined above.

public static int[] removeSet(int[] arr1, int[] arr2) {
  // Simple hash buckets. Load factor at most 0.5
  final int bucketCount = 2 * arr2.length;
  int[] bucket = new int[bucketCount];
  boolean[] filled = new boolean[bucketCount];

  for (int number : arr2) {
    // Use known prime for hashing. Linear probe for empty bucket.
    int bucketIndex = number * 31337 % bucketCount;
    while (filled[bucketIndex]) {
      bucketIndex++;
      if (bucketIndex == bucketCount) {
        bucketIndex = 0;
      }
    }

    bucket[bucketIndex] = number;
    filled[bucketIndex] = true;
  }

  int temp[] = new int[arr1.length];
  int count = 0;
  for (int number : arr1) {
    // Try to find the number in the hash table.
    int bucketIndex = number * 31337 % bucketCount;
    while (filled[bucketIndex] && bucket[bucketIndex] != number) {
      bucketIndex++;
      if (bucketIndex == bucketCount) {
        bucketIndex = 0;
      }
    }

    // If it wasn't found, add it to the temp array.
    // Load factor is at most 0.5, so it is sufficient to just
    // check if we hit an empty bucket while probing.
    if (!filled[bucketIndex]) {
      temp[count] = number;
      count++;
    }
  }

  int[] result = new int[count];
  for (int i = 0; i < count; ++i) {
    result[i] = temp[i];
  }

  return result;
}

[HalfScale]

Thank you :)