## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
Suppose we have an array
a1,a2....an,b1,b2....bn How to change this array to a1,b1,a2,b2....an,bn in O(n)/O(nlgn) time using O(1) space This question has appeared in the forum before also http://discuss.techinterview.org/default.asp?interview.11.484934.10 But still it doesnt have a proper answer. Can anyone come up with O(nlgn) algorithm for this ? O(n) solution will be a bonus.
tryhard Friday, June 29, 2007
@Magician (if he still checks the forum)
Can you please share the answers.
tryhard Friday, June 29, 2007
Given all the effort that has gone into this question, if I were asked this question in an interview, I would say that it is too prone to error and that I would go with a simple O(n) space algorithm.
The obvious approach is two loops with one assignment in each. The loops could be condensed into one. I (and pretty much anyone else here) could dash off the answer in a little longer than for FizzBuzz. Or you can try draining the swamp: your call. Sincerely, Gene Wirchenko
what about this ?
suffle(int a[], int start, int n) { // we need to swap these many numbers // int ns = (n + 1) / 2 + n % 2; for (int i = 0; i < ns; i ++ ) swap(a, start + n/2 + i, start + n + i) suffle(a, start, n / 2); suffle(a, start + n + n % 2, n / 2); } for n = 5 1 2 3 4 5 6 7 8 9 10 ns = 4 after swapping, it becomes 1 2 6 7 3 8 4 5 9 10 then we will suffle 1 2 6 7 and 4 5 9 10 seperately
// Return the location of element that should be placed in
// the given index in the final array. int loc(int n, int idx) { // 'b' portion of the array. if (idx & 1) { return (idx / 2) + n; } // 'a' portion of the array return (idx / 2); } // Assuming first array item is index 0. // Rearrange the buffer. idx = 1; temp = buff[idx]; // -3 because a1 and bn don't move for (count = 0; count < 2n - 3; count++) { buff[idx] = buff[loc(idx)]; idx = loc[idx]; } buff[idx] = temp; O(n) time, O(1) space. May need debugging.
I think we've beaten the prime number/ prime factorization approach to death already.
In case anyone cares here's a link to a postscript paper on the power of 2 approach. There are on-line postscript reader. http://www.cs.uvic.ca/~jellis/Publications/merge.ps I found it as link from this site http://www.cs.uvic.ca/~jellis/perfect.html
@Zekaric: Your algorithm does not work for all n.
Here is an O(nlogn) time O(1) space algorithm, which is perhaps what pvncad was talking about. For O(nlogn) we use a divide an conquer algorithm: a1 a2 .... an b1 b2 ... bn Now say k = n/2 (integral part of n/2) Consider: A : a1 a2 ... ak a(k+1) ... an b1 b2 .... bk b(k+1) ... bn Now imagine if the array looked like A' : a1 a2 ....ak b1 b2 ... bk a(k+1) .... an b(k+1) .... bn We could do a shuffle of the first 2k elements of the array and a shuffle of the remaining 2(n-k) elements. Now in order to get from A to A', all we need to do is a cyclic shift of the middle elements a(k+1) ... an b1 b2 ... bk! Cyclic shift is a standard interview question and can be done in O(n) time and O(1) space! Thus with a divide and conquer approach, we can do an O(nlogn) time and O(1) space algorithm. Note, even thought it looks to be recursive, we can do away with the recursion and do it iteratively, thus maintaining the O(1) spaceness.
Tapori Friday, June 29, 2007
#include<stdio.h>
#include<conio.h> void print(char ar[]) { for(int i=0;i<2*n;++i) printf("%c\t",ar[i]); } void shuffle(char ar[],int m){ int k=n; char temp='\0'; for(int i=1;i<n;i=i+2) { temp=ar[i]; k=i*2; temp^=ar[k]^=temp^=ar[k]; while(i!=k) { if(k<n) { k=2*k; temp^=ar[k]^=temp^=ar[k]; } else { k=2*(k-n+1)-1; temp^=ar[k]^=temp^=ar[k]; } } } print(ar); } int main(){ char a[]={'a','b','c','d','e','1','2','3','4','5'}; int n=5; shuffle(a,n); getch(); } O(n) solution from me
And now for an O(n) time and O(1) space algorithm, which uses concepts of number theory!
(Warning: long post) For this we consider a slightly different problem: That of converting the array a1 a2 ... an b1 b2 ... bn to b1 a1 b2 a2 .... bn an (instead of the one given in the problem statement) Note if we can get an O(n) time O(1) space algorithm for one, then we have an O(n) time O(1) space time algorithm for the other. Now assume the elements are c1 c2 ... cn c(n+1) .. c2n In the resulting array (which is a permutation of the original) The ith element from the original goes to 2i modulo 2n+1. Thus index 1 goes to 2, 2 goes to 4, 4 goes to 8 ... ultimately comes back to 1 (all working modulo 2n+1) Note that, it is a permutation which is composed of "cycles" like the ones described above (I think Zekaric made the mistake of assuming there is just one cycle) For instance consider the case when n=4 1 2 3 4 5 6 7 8 It should become 5 1 6 2 7 3 8 4 so 1 -> 5 -> 7 -> 8 -> 4 -> 2 -> 1 (-> means goes to) and 3 -> 6 -> 3 So the cycles are (1 5 7 8 4 2) and (3 6) Assume you had an oracle which told you one element from each cycle. Can you come up with an O(n) time and O(1) space algorithm? If we do not have such an oracle, trying to come up with elements from distinct cycles becomes hard. This is where number theory comes in: In case 2n+1 is a power of 3 = 3^m say, using number theory, we can show that the cycles are exactly (1, 2, 2^2, ... ) (powers of 2) (In fact these are all the numbers relatively prime to 3^m, note, working modulo 2n+1, i.e modulo 3^m) (3, 3*2, 3*2^2, ...) (numbers of the form 3 * 2^j (3^2, 3^2 *2 ,....) numbers of the form 3^2 * 2^j ... (3^(m-1),....) numbers of the form 3^(m-1) * 2^j (will post a proof of this later if someone is interested) Thus the "number theory oracle" has told us that the powers of 3 are guaranteed to be in different cycles! That is all we need! So in the special case of 2n+1 being a power of 3, we can give an O(n) time and O(1) space algorithm. Given the special case (power of 3) algorithm, we can now make this work for any n: In the O(nlogn) solution I gave above, instead of k = n/2, pick k to be a power of 3 close to n and use the special knowledge of cycles to shuffle that left partial array in O(n) time. Now for the right partial array, we have a new n' = (n-k) and repeat finding a k' which is a power of 3 etc. Overall, time is O(n) and space is O(1).
Tapori Friday, June 29, 2007
@K Ashwin Kumar: you algorithm does not work for all n.
Here is a thread in a forum which discusses this as well as has a proof of the number theory result I was stating in the O(n) time and O(1) space algo: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1084733627
Tapori Friday, June 29, 2007
Considering that the problem has an easy solution if you are can spend some extra memory, all this mumbo jumbo above looks somewhat crazy IMO.
Just create a new 2n array and start writing elements of the first and the second array alternating. int newarray[2n]; int oldarray[2n] = { a1, a2, ..ab, b1, b2, ... bn } int j=0; for (int i =0; j < n; i++, j++) { newarray[i] = oldarray[j]; newarray[++i] = oldarray[j+n]; }
Bytheway Friday, June 29, 2007
I'll rather use file IO if I don't have enough memory than mess with the number theory to solve in essence a trivial problem made into an extremelly complex one by memory requirements.
No offense to beautiful number theory.
Bytheway Friday, June 29, 2007
With O(n) space , things are a bit easier. For example, for six elements there are 2 cycles. The main objective is to mark a given cycle has already visited. So, we keep a flag with each element and mark it is touched/untouched.
Winner Friday, June 29, 2007
@bytheway,
Using O(n) space is trivial, where is the fun in that? Seriously though, do you really think it is a waste of effort? You never know where this might come in useful. For instance, consider an embedded device with _very_ little memory and no hard-disk. This algorithm might come in useful there. Also, even though it looks intimidating, it is pretty easy to implement. Also, I was just responding to the question which was asked: O(n) time and O(1) space, and (no offense), but to discuss an O(n) space time algorithm (which is pretty trivial to boot) is just wasting people's time and polluting this thread with unsolicited comments.
Tapori Saturday, June 30, 2007
I do apologize Tampori. Learning something new and solving the problem in a different way is always good and fun.
Bytheway Saturday, June 30, 2007
Below link may give some more direction to the discussion
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1094241218
Gene,
Really, I didn't expect such a comment from you. The main purpose of this thread was to ask for an O(n) time and O(1) space algorithm... which was answered, and IMHO the algorithm I gave is the simplest I have seen for this. The proof of the algorithm might be hard to understand, but the code is really simple and would be pretty easy to debug (See Ashwin's link, which has the code). If you think this would be hard to debug, you must be really working with simple programs, like tic-tac-toe or adding two numbers or something. Anyway, I hope the original poster is happy with the response.
Tapori Saturday, June 30, 2007
Thanks to all the guys especially Tapori for his solutions...
Learning something is never a waste of time, you never know what constraints you face when and where. Thanks once again !!
tryhard Sunday, July 01, 2007
"Gene,
Really, I didn't expect such a comment from you. The main purpose of this thread was to ask for an O(n) time and O(1) space algorithm... which was answered, and IMHO the algorithm I gave is the simplest I have seen for this." Look at how many responses there have been. Look at how many wrong answers. How much time should someone put into such a routine? "The proof of the algorithm might be hard to understand, but the code is really simple and would be pretty easy to debug (See Ashwin's link, which has the code)." You are contradicting yourself. If the algorithm is hard to understand, then debugging the code would be difficult, too. Sure, if the code is correct, there is no problem (also no debugging needed), but what if it is not? Debugging is going to require understanding the algorithm (or being an extremely good guesser). "If you think this would be hard to debug, you must be really working with simple programs, like tic-tac-toe or adding two numbers or something." Difficulty in debugging is related to the difficulty of the algorithm. Consider an RW environment. How much time do you think should be spent on this? At what point should you chuck it and go with the simple algorithm? An O(n) space solution is trivial. This problem has been a time sink. I have noted a number of requests for O(n) time, O(1) space algorithms. There is also the time involved in coming up with such an algorithm. This time might not be trivial and might be better spent elsewhere. "Anyway, I hope the original poster is happy with the response." Likewise. Sincerely, Gene Wirchenko Monday, July 02, 2007
>>The proof of the algorithm might be hard ... <snip>
>You are contradicting yourself. If the algorithm is hard >to understand... <snip> I never said that the algorithm is hard to understand. I said "the _PROOF_ of the algorithm is hard to understand". Two very different things. >I have noted a number of requests for O(n) time, O(1) >space algorithms. There is also the time involved in >coming up with such an algorithm. This time might not be >trivial and might be better spent elsewhere. Yes, the time _might_ be better spent elsewhere. Depends on the situation. There might be situations where O(n) space and O(1) time algorithms are absolutely required. For instance consider this shuffling issue. I believe doing a shuffle is an integral part of FFT. Perhaps this algorithm will simplify the hardware devices' complexity which do FFT. Who knows. You never know where this might be useful, and I doubt anyone (and that includes you) is clarivoyant enough see if such a thing will not be useful. Claiming that it is a waste of time for everyone just shows one's short sighted thinking. If you think it is a waste time for you, don't spend any time on it. Just don't try to force your opinion in threads which are specifically meant for discussing these. On a side note, I am in no way suggesting that this is a good interview question if that is where you are coming from. In fact asking for the O(n) time and O(1) space algorithm in an interview is unfair. Monday, July 02, 2007
>>The proof of the algorithm might be hard ... <snip>
>You are contradicting yourself. If the algorithm is hard >to understand... <snip> "I never said that the algorithm is hard to understand. I said "the _PROOF_ of the algorithm is hard to understand". Two very different things." True. I stand corrected on that part. BUT. If the problem is so difficult that it has a number of incorrect solutions posted, it is maybe a bad choice for inclusion in code and as an interview question. >I have noted a number of requests for O(n) time, O(1) >space algorithms. There is also the time involved in >coming up with such an algorithm. This time might not be >trivial and might be better spent elsewhere. "Yes, the time _might_ be better spent elsewhere. Depends on the situation. There might be situations where O(n) space and O(1) time algorithms are absolutely required." True again, but I am looking at the practicality in general. "Claiming that it is a waste of time for everyone just shows one's short sighted thinking." I did not make such a claim. "If you think it is a waste time for you, don't spend any time on it. Just don't try to force your opinion in threads which are specifically meant for discussing these." It is my job as moderator to force my opinion sometimes. Is this question suitable as an interview question? I think that the reasonable answer has now been shown to be no. "On a side note, I am in no way suggesting that this is a good interview question if that is where you are coming from. In fact asking for the O(n) time and O(1) space algorithm in an interview is unfair." But it is the main note! What is the purpose of this forum? Discussing interview questions perhaps? I think the question is a waste of time as an interview question. Sincerely, Gene Wirchenko techInterview Moderator
> <snip>
>But it is the main note! What is the purpose of this >forum? Discussing interview questions perhaps? I think >the question is a waste of time as an interview question. Yes, as an interview question (I think) it is a ridiculous question. BUT. Discussing it (here or eleswhere) is not a waste of time, as you seemed to imply. Moreover, this might actually have been asked by some company in an interview, hence the reason people post it here so many times. So it could still be relevant to this forum. No?
Tapori Monday, July 02, 2007
#include<stdio.h>
#include<conio.h> #include<string.h> char* arrShuffle(char* str) { int midStr=strlen(str)/2; for(int i=1;i<midStr;i++) for(int j=i;j<midStr;j++) str[j]^=str[midStr+j-i]^=str[j]^=str[midStr+j-i]; return str; } void main() { char str[]="abcdef123456"; printf("Shuffled array is:%s",arrShuffle(str)); getche(); } |

Powered by FogBugz