## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
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
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.
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)
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 |

Powered by FogBugz