Java: Interleaving multiple arrays into a single array

I found similar question about interleaving two arraylists into one, but its in PHP. I was asked this question in interview as well but could'nt solve it, came back to SO to look if it was addressed already, but i could only find this paper

So any pointers to pseudo code or method definition ?

Big(O) restrictions : O(n) - time cost and O(1) - space cost

Example:

a[]= a1, a2, ..., an

b[]= b1, b2, ..., bn

Rearrange the arraylist to a1, b1, a2, b2, ..., an, bn

Editv1.0 : Arraylists a[] and b[开发者_运维知识库] are of same size

Editv2.0 : What if the question is extended to rearrange in one of given two arrays, but not create a new array ?

For simplicity, assume that the arrays are the same length, and are int arrays.

int[] merge(int[] a, int[] b)
{
    assert (a.length == b.length);

    int[] result = new int[a.length + b.length];

    for (int i=0; i<a.length; i++)
    {
        result[i*2] = a[i];
        result[i*2+1] = b[i];
    }

    return result;
}

I think this is not doable with your given constraints (O(n) time and O(1) space, i.e. no additional space) for an array or array-based list. (Assuming of course, that we can't simply create a new List object delegating to the original ones.)

If you have two linked lists, this is doable - if we assume the garbage collector is fast enough, i.e. deleting an element from one list and adding it to another list does not violate the space limitation.

public <X> void interleaveLists(List<X> first, List<X> second)
{
    ListIterator<X> firstIt = first.listIterator();
    ListIterator<X> secondIt = second.listIterator();
    while(secondIt.hasNext()) {
        fistIt.next();
        firstIt.add(secondIt.next());
        secondIt.remove();
    }
}

This method works for any pair of lists, but is only O(n) for linked lists.

For a custom linked list where we can modify the pointers, we don't have to rely on the garbage collector, we would simply change the nodes. Here for a singly-linked list:

public void interleaveLinkedLists(Node<X> firstList, Node<X> secondList) {
    while(secondList != null) {
        Node<X> nextFirst = firstList.next;
        Node<X> nextSecond = secondList.next;
        firstList.next = secondList;
        secondList.next = nextFirst;
        firstList = nextFirst;
        secondList = nextSecond;
    }
}

For a doubly-linked list, we would also have to adapt the prev-pointers.

Here the wrapping variant mentioned in the first paragraph:

public List<X> interleaveLists(final List<X> first, final List<X> second)
{
   if (first.size() != second.size())
      throw new IllegalArgumentException();
   return new AbstractList<X>() {
      public int size() {
         return 2 * first.size();
      }
      public X get(int index) {
         return index % 2 == 0 ? first.get(index / 2) : second.get(index / 2);
      }
      // if necessary, add a similar set() method.  add/remove are not sensible here.
   };
}

This is actually O(1) in time, too.

I've done up a small solution going on the assumption that you are talking about using the ArrayList (see my comment on the question). I may be oversimplifying the problem based on some of the responses here, but here goes anyway.

The below example takes a and b both of type ArrayList<Integer> and interleaves them by inserting b[0] after a[0], b[1] after a[1] etc. This snippet of course naively assumes that a and b are of the same size as per your Edit v1.0. It also does not create a new ArrayList as per your Edit v2.0.

//a and b are of type ArrayList<Integer>
for (int i = a.size(); i > 0; i--)
{
    a.add(i, b.get(i - 1));
}

No matter what happens if you are combining the ArrayLists you're going to have twice the size.

I believe the mod (%) operations in Matt's answer are incorrect. Under the same assumption (that the arrays are the same length), I'd propose the following solution instead:

static int[] merge(final int[] a, final int[] b)
{
    final int[] result = new int[a.length * 2];

    for (int i=0; i < a.length; i++)
    {
        result[i << 1] = a[i];
        result[(i << 1) + 1] = b[i];
    }

    return result;
}

I tested (very briefly), and it appears to work, but of course makes no attempt to handle error conditions such as null arguments or input arrays mismatched in size.

in the meantime lambda was introduced
O(n) time complexity
O(1) space complexity

int[] merge(int[] a, int[] b) {
    return( IntStream.range( 0, a.length ).flatMap(
        n -> IntStream.of( a[n], b[n] ) ).toArray() );
}

The lists don't have to be the same size:

public class InterleaveTwoLists<X> {

    public List<X> interleaveLists(final List<X> first, final List<X> second) {

        return new AbstractList<X>() {
            private int minSize;
            private int combinedMinSize;
            private int size;
            private List<X>largerList;
            {{
                minSize = Math.min(first.size(), second.size());
                combinedMinSize = minSize*2;
                size = first.size() + second.size();
                largerList = first.size() > minSize ? first : second;
            }}

            public int size() {
                return size;
            }

            public X get(int index) {
                if (index < combinedMinSize) {
                    return index % 2 == 0 
                        ? first.get(index / 2) 
                        : second.get(index / 2);
                }
                else { 
                    return largerList.get(index-minSize);
                }
            }
        };
    }
}

To test this:

public class InterleaveTwoListsTest {

    private static final Logger log = 
        LoggerFactory.getLogger(InterleaveTwoListsTest.class);

    List<String> first = new ArrayList<String>() {
    { 
        add("one"); add("three"); add("five"); 
        add("seven"); add("eight"); add("nine");
    }};

    List<String> second = new ArrayList<String>() {
    { 
        add("two"); add("four"); add("six"); 
    }};


    private InterleaveTwoLists<String> interleaveTwoLists;

    @Before
    public void setUp() throws Exception {
        interleaveTwoLists = new InterleaveTwoLists<>();
    }

    @Test
    public void test() {
        List<String> combinedList = interleaveTwoLists.interleaveLists(first, second);
        for( int i = 0; i < first.size() + second.size(); i++) { 
            log.debug("{}: {}", i, combinedList.get(i));
        }
    }
}