How can I improve by optimizing this piece of Java Code

Question

I have been trying to figure out if I can use some other sort of Data Structures for this problem. I managed to somehow solve it, but still lacking a lot of good quality code.

I was asked in an interview the other day: Given an Input String like:

String[] inputString = { "a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"};

Convert this to output String:

String[] outputString = { "a1", "b1", "a2", "b2", "a3", "b3", "a4", "b4", "a5", "b5" };

I tried the following, and so far I feel this needs some improvement:

public class ArrayApp {
    public static void main(String[] args) {

        String[] inputString = { "a1", "a2", "a3", "a4", "a5", "b1", "b2",
                "b3", "b4", "b5" };
        // String[] outputString = { "a1", "b1", "a2", "b2", "a3", "b3", "a4",
        // "b4", "a5", "b5" };

        String[] str1 = new String[5];
        System.arraycopy(inputString, 0, str1, 0, 5);
        System.out.println("String Array str1");
        for (int i = 0; i < str1.length; i++) {
            System.out.print(str1[i]);
        }
        System.out.println();
        String[] str2 = new String[5];
        System.arraycopy(inputString, 5, str2, 0, 5);
        // System.out.println(str2.length);
        System.out.println("String Array str2");

        for (int i = 0; i < str2.length; i++) {
            System.out.print(str2[i]);
        }

        String temp = "";
        int i = 0, j = 0;

        for (i = 0; i < str1.length; i++) {
            temp = temp + str1[i];
            for (j = i; j < str2.length; j++) {
                if (j > i) {
                    break;
                }
                temp = temp + str2[j];
            }
        }
        System.out.println("\nFinal String " + temp);

        System.out.println();

    } // end main()
} // end class ArrayApp

Question is - Can this be improved by using Sets? I tried iterating over sets, but that did not work for me. Is there any other collection class I need to use here?

Thanks for your time.

BTW here is the O/P

String Array str1 a1a2a3a4a5 String Array str2 b1b2b3b4b5 Final String a1b1a2b2a3b3a4b4a5b5

Answer 1

You have to tell us the rationale behind the conversion:

It is simply rearranging the array by picking up every 5th element, til the end, and then start again at next element, repeat for 5 times? i.e. rearrange as arr[0], arr[5], arr[10]..., arr[1], arr[6], arr[11], .... arr[2], arr[7], arr[12]...

Or it is rearranging by sorting by the 2nd char and then 1st?

for example, if you are given an array ["z9", "y2", "a2", "b1", "c4", "t7", "s6"]

What should be the final result?

["z9", "t7", "y2", "s6", "a2", "b1", "c4"]

or

[ "b1", "a2", "y2", "c4", "s6", "t7", "z9"] ?

This can lead to a very different way of "optimization"

The first one can simply be done as

for (int i = 0; i < 5; ++i) {
  for (int j = i; j < arr.length; j+=5) {
    resultArrayList.add(arr[j]);
  }
}

The second one is simply

Arrays.sort(arr, new Comparator<String> {
  int compare(String s1, String s2) {
    return ("" + s1.charAt(1) + s1.charAt(0)).compareTo("" + s1.charAt(1) + s1.charAt(0));
  }
}

For latter case, you can further optimize by giving a more effective compare function.

Answer 2

It sounds like you just want:

String[] outputString = new String[inputString.length];
for (int i = 0; i < inputString.length / 2; i++) {
    outputString[i * 2] = inputString[i];
    outputString[i * 2 + 1] = inputString[i + inputString.length / 2];
}

But its not clear whether it's really just this interleaving that you want...

(For micro-optimization you could try computing i * 2 just once per iteration, and take inputString.length / 2 out of the loop. I suspect the JIT compiler will do all of that for you though...)

Anyway, this has reduced it from O(n²) to O(n). It's not really clear why your current code is coming up with a String instead of a String[] to start with, mind you. (The question is unclear too, as you talk about a string, but then provide a string array...)

Full code:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        String[] inputString = { "a1", "a2", "a3", "a4", "a5", 
            "b1", "b2", "b3", "b4", "b5"};
        String[] outputString = new String[inputString.length];
        for (int i = 0; i < inputString.length / 2; i++) {
            outputString[i * 2] = inputString[i];
            outputString[i * 2 + 1] = inputString[i + inputString.length / 2];
        }

        System.out.println(Arrays.toString(inputString));
        System.out.println(Arrays.toString(outputString));
    }
}

Output:

[a1, a2, a3, a4, a5, b1, b2, b3, b4, b5]
[a1, b1, a2, b2, a3, b3, a4, b4, a5, b5]

That looks exactly like your specification...

Answer 3

Maybe something like the following, it will give you the desired output.

public class Test {
    public static void main(String[] args) {

        String[] inputString = { "a1", "a2", "a3", "a4", "a5", "b1", "b2",
                "b3", "b4", "b5" };

        Arrays.sort(inputString, new Comparator<String>() {

            private String reverse(String s) {
                return new StringBuilder(s).reverse().toString();
            }

            @Override
            public int compare(String arg0, String arg1) {
                return reverse(arg0).compareTo(reverse(arg1));
            }
        });

        System.out.println(Arrays.toString(inputString));
    }

}

Answer 4

An obvious way to do it would be to simply sort the array (perhaps with insertion sort, due to its length -- or just Arrays.sort() to re-use API code).

Alternatively, you could use a loop with two indices, i and j, starting at 0 and 5 respectively, and just put the ith element in a new array, then the jth, and so on, incrementing each index each time, until you've filled the entire resulting array. The latter is probably more computationally efficient (since it is O(n) in the worst case), but it is perhaps less obvious what it is supposed to do.

Or, you could even unroll the loop entirely, and just do something like:

String[] newArray = new String[]
{
    inputString[0], inputString[5],
    inputString[1], inputString[6],
    inputString[2], inputString[7],
    inputString[3], inputString[8],
    inputString[4], inputString[9]
}

That actually make be the most computationally efficient way to do it - although the least general.