Interleave array in constant space

arrays algorithm permutation
Matt picture Matt · Nov 22, 2009 · Viewed 9k times · Source

I ran across the following sample job interview question. How can I solve it?

Suppose we have an array a1, a2,... , an, b1, b2, ..., bn.

The goal is to change this array to a1, b1, a2, b2, ..., an, bn in O(n) time and in O(1) space. In other words, we need a linear-time algorithm to modify the array in place, with no more than a constant amount of extra storage.

Answer

Anony picture Anony · Jan 17, 2010

This problem is not as trivial as people make out to be. Homework? LOL.

The following link has a solution: http://arxiv.org/abs/0805.1598

Related questions

Print out all permutations of an Array

I am working on a program, and I have a function that swaps the positions in an Array of length that is input by a user. However, I am trying to figure out how to print out this function call …

Read More
Find all subsets of length k in an array

Given a set {1,2,3,4,5...n} of n elements, we need to find all subsets of length k . For example, if n = 4 and k = 2, the output would be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. I am not even able to figure out how to start. We don't have …

Read More
How can I generate all permutations of an array in Perl?

What's the best (elegant, simple, efficient) way to generate all n! permutations of an array in perl? For example, if I have an array @arr = (0, 1, 2), I want to output all permutations: 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 It should probably be a function that returns an …

Read More