techInterview Discussion

Answers to technical interview questions. A part of TechInterview.org

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

interleave array

you are given an array a1 a2 ... an b1 b2 ... bn c1 c2 ... cn of 3n elements.

you need to interleave it as

a1 b1 c1 a2 b2 c2 ... an bn cn

you have to do this with constant extra space. Looking for a better than O(n^2) algorithm.
High Troller
Tuesday, April 20, 2010
 
 
Let A1 A2 A3 stand partitionins of a1 ... an, and similarly for B and C, where the partitioning is done by thirds.

The sequence of length 3n is then
 A1 A2 A3 B1 B2 B3 C1 C2 C3
rearrange this to be
 A1 B1 C1 A2 B2 C2 A3 B3 C3
by swapping partitions.

Recurse.

The partition swap algorithms will have poor constant performance when the partitions are not the same size, but the 3 swaps are still O(n), so overall it's O(log(n)).
Skorj
Wednesday, April 21, 2010
 
 
@Skorj.

Why should n be divisible by 3?

Did you mean O(nlogn)? As Omega(n) is a trivial lower bound.
Anonical
Wednesday, April 21, 2010
 
 
There's probably an O(n) solution that exploits the structure of the permutation

pi : Z/(3n-1) -> Z/(3n-1)
pi(x) = 3*x
d Send private email
Wednesday, April 21, 2010
 
 
The question doesn't say anything about the space complexity.

1) Create 3 arrays of size n each.
2) Put all the a1...an in the first array , similarly for b and c.
3) Fill the original sequence with the sequence you want.

O(n) , but I am sure the interviewer would not want such a bad space complexity [ie O(n)].  Skroj's one looks good and I could not understand d's approach.
Rahul.b Send private email
Thursday, April 22, 2010
 
 
Space complexity is mentioned: O(1).
High Troller
Thursday, April 22, 2010
 
 
Yes, O(n) is possible.
Anonical
Thursday, April 22, 2010
 
 
The idea in this paper works for this problem: http://arxiv.org/abs/0805.1598

but it gives
c1 b1 a1 c2 b2 a2 ... cn bn an

Use powers of 5 (the paper has powers of 3 for 2n element array).

O(n) time, O(1) space.

Friday, April 23, 2010
 
 
A1..AnB1..BnC1..Cn
break B1..Bn into 2 parts and swap B1..Bn/2 with An/2..An and Bn/2..Bn with C1..Cn/2

now array looks like
A1..An/2 B1..Bn/2 An/2..An C1..Cn/2 Bn/2..Bn Cn/2..Cn

now swap parts in middle part
An/2..An with C1..Cn/2.

Now array looks like
A1..An/2 B1..Bn/2 C1..Cn/2 An/2..An Bn/2..Bn Cn/2..Cn

all halfs are together.. above looks like two sub-problems
A1..An/2 B1..Bn/2 C1..Cn/2
An/2..An Bn/2..Bn Cn/2..Cn

Follow the same process until division size is equal to 1.

Analysis:
-----------
T(n) = 2T(n/2) + O(n/3) + O(n/6)
looks like complexity is O(n Logn)
subbu Send private email
Saturday, May 01, 2010
 
 
@subbu: Why should n be divisble by 2 or 3?
Anonical
Monday, May 03, 2010
 
 
It's not necessary that N be divisible by 3 - you just have to do some shifting of the elements in between.

So, as a first step, to transform

A1 A2 A3 B1 B2 ...

to

A1 B1 [A3] A2 B2 ...

All the elements in A3 may have to shift one left or one right, but that doesn't change the asmyptotic efficiency.  (And yes, I meant O(n * log(n)) above - log n passes, each O(n)).
Skorj
Tuesday, May 04, 2010
 
 
It is not the simple Skorj.

The O(nlogn) divide and conquer (and the O(n) algo) both require the 'cyclic shift array by k places in O(n) time and O(1) space' as a subroutine.
Anonical
Thursday, May 06, 2010
 
 
void transposesort(int input[], int n)
{
    if(n < 2)
        return;

    int k = n/2;

    rotate(input, k, n+k-1, k);

    transposesort(input, k);
    transposesort(input+2*k, n-k);
}

where "rotate" will rotate elements starting from k to n+k-1 and by rotation distance = k.
Sesh
Monday, May 10, 2010
 
 
/* divide N conquer, O(nlogn) runtime */
void reverse(char a[], int start, int end)
{
    while (start < end) {
        int temp = a[start];
        a[start] = a[end];
        a[end] = temp;
        start++;
        --end;
    }
}
void cyclicshift(char a[], int start, int n)
{
    reverse(a, start, start + n -1);
    reverse(a, start, start + n/2 - 1);
    reverse(a, start + n/2, start + n - 1);
}
/* shuffle(array, 0, n) */
void shuffle(char a[], int start, int n)
{
    if (n == 1) {
        return;
    }
    int k = n /2;
    cyclicshift(a, start + k, n + n %2);
    if ( n % 2) {
        int temp = a [start + n-1];
        a[start + n-1] = a[start + n];
        a[start + n] = temp;
        shuffle(a, start, n/2);
        shuffle(a, start + n+1, n/2);
        return;
    } else {
        shuffle(a, start, n/2);
        shuffle(a, start + n, n/2);
    }
}
Nagesh Ayyagari
Tuesday, May 11, 2010
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz