Java: interleaving multiple arrays into one array

Question

I found a similar question about alternating two arraylists into one, but in PHP. I was also asked this question in an interview, but he could not solve it, returned to SO to see if this was fixed, but I could only find this paper

So, any pointers to pseudocode or method definition?

Big (O) restrictions: O (n) is the cost of time and O (1) is the volume cost

Example:
a [] = a1, a2, ..., an
b [] = b1, b2, ..., bn
Regroup arraylist to a1, b1, a2, b2, ..., an, bn

Editv1.0 : Arraylists a [] and b [] are the same size

Editv2.0 : what if the question is expanded to reorder in one of the given two arrays but not create a new array?

Answer 1

For simplicity, suppose 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; } 

Answer 2

I think this is not feasible with your restrictions ( O(n) time and O(1) space, i.e. without extra space) for an array or array. (Assuming, of course, that we cannot just create a new List object, delegating the original one.)

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

 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 it is only O (n) for linked lists.

For a custom linked list where we can change pointers, we don’t need to rely on the garbage collector, we will just 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 will also have to adapt the pre-pointers.

Here's the packaging option 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 also O(1) .

Answer 3

I made a small decision based on the assumption that you are talking about using ArrayList (see my comment on the question). I can simplify the problem based on some answers here, but here it doesn't matter.

Below is an example of a and b of both types of ArrayList<Integer> and alternates them by inserting b [0] after [0], b [1] after [1], etc. This snippet, of course, naively assumes that a and b are the same size as in your v1.0 editor. It also does not create a new ArrayList according to your v2.0 editor.

 //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 combine ArrayLists, you will have twice as much.

Answer 4

I believe the mod (%) actions in Matt's answer are incorrect. Under the same assumption (that arrays are the same length), I would suggest the following solution:

 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 seems to work, but of course it does not try to handle error conditions such as null arguments or input arrays that are inconsistent in size.

Answer 5

Lists must not 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 check 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)); } } }