you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.
input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }
input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }
Thursday, May 15, 2008
This is similar to an implementation of partition method of quick sort.
oddInd==0;
evenInd=1;
while(true)
{
while(oddInd
if(oddInd>=strLen) break;
while(evenInd
if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}
Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.
oddInd==0;
evenInd=1;
while(true)
{
while(oddInd
if(oddInd>=strLen) break;
while(evenInd
if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}
Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.
jigsaw 
Thursday, May 15, 2008
Thursday, May 15, 2008
OOPS!!! There was a big mistake in the above code.
This is similar to an implementation of partition method of quick sort.
oddInd==0;
evenInd=1;
while(true)
{
while(oddInd if(oddInd>=strLen) break;
while(evenInd if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}
Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.
This is similar to an implementation of partition method of quick sort.
oddInd==0;
evenInd=1;
while(true)
{
while(oddInd
while(evenInd
swap(str[evenInd], str[oddInd]);
}
Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.
jigsaw
Thursday, May 15, 2008
Thursday, May 15, 2008
Perish the thought that anyone should use extra memory!
BTW, the indexes into the array are extra memory.
Too many of these questions are isomorphic with:
"Oh, so you can type in your code? How about if we tie one arm behind your back? YANK! Still typing? How about if we keep hitting you with this baseball bat? Whack, whack, whack! Still at it, huh? Well, at least we got him down to 2 WPM."
Sincerely,
Gene Wirchenko
BTW, the indexes into the array are extra memory.
Too many of these questions are isomorphic with:
"Oh, so you can type in your code? How about if we tie one arm behind your back? YANK! Still typing? How about if we keep hitting you with this baseball bat? Whack, whack, whack! Still at it, huh? Well, at least we got him down to 2 WPM."
Sincerely,
Gene Wirchenko
Gene Wirchenko 
Thursday, May 15, 2008
Thursday, May 15, 2008
:) That's funny. BTW when he said extra memory, he meant variable amt of memory i guess.
jigsaw
Friday, May 16, 2008
Friday, May 16, 2008
That seems to be what they mean when they say no extra memory. Heck making a function call allocates a frame on the stack so does that mean no function calls either?
I always took it to mean no building a data structure. Which can be a valid restriction if data is going to be changing often(high rebuild costs) or you have a truly large dataset. It can be hard to get a std::vector to hit 100mb if you already have a number of other 100mb chunks floating around.
I always took it to mean no building a data structure. Which can be a valid restriction if data is going to be changing often(high rebuild costs) or you have a truly large dataset. It can be hard to get a std::vector to hit 100mb if you already have a number of other 100mb chunks floating around.
soup
Friday, May 16, 2008
Friday, May 16, 2008
soup,
The usual complexity-theoretic definition of "no extra memory" is that the program can use a constant number of registers just large enough to index the input.
The usual complexity-theoretic definition of "no extra memory" is that the program can use a constant number of registers just large enough to index the input.
d
Friday, May 16, 2008
Friday, May 16, 2008
I tried JigSaw's solution in to java(http://pastebin.com/f41fe39d1). I might have mis-understood the code but the resulting array is
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
ved
Monday, May 26, 2008
Monday, May 26, 2008
I think there is a problem in jigsaw's solution.His solution says:
oddInd==0;
evenInd=1;
while(true)
{
while(oddInd if(oddInd>=strLen) break;
while(evenInd if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}
First of all.it will produce an an arrangement of 10101010 type of string.But that can be solved by using str[oddInd]==0 and str[evenInd]==1. But more serious problem is if the array is such that it has even no. of elements and each even positions are correctly filled with 0s and there are some extra 0s in odd positions because in that case the first inner while loop executes and then the outer while loop terminates by break statement.
oddInd==0;
evenInd=1;
while(true)
{
while(oddInd
while(evenInd
swap(str[evenInd], str[oddInd]);
}
First of all.it will produce an an arrangement of 10101010 type of string.But that can be solved by using str[oddInd]==0 and str[evenInd]==1. But more serious problem is if the array is such that it has even no. of elements and each even positions are correctly filled with 0s and there are some extra 0s in odd positions because in that case the first inner while loop executes and then the outer while loop terminates by break statement.
sagsriv
Friday, June 13, 2008
Friday, June 13, 2008
@sagsriv
i guess the depend on understanding of "and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched"
e.g., input array:
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
output array should be:
a)
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
since in the question, it states
"if 0s exceed no. of 1s or vice versa then keep them untouched"
or
b)
{0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 }
to move "0s" to the end.which should can be also done in one pass.
which looks better..lol
i guess the depend on understanding of "and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched"
e.g., input array:
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
output array should be:
a)
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
since in the question, it states
"if 0s exceed no. of 1s or vice versa then keep them untouched"
or
b)
{0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 }
to move "0s" to the end.which should can be also done in one pass.
which looks better..lol
Add all the numbers in the array to get the sum. The sum equals to number of ONEs in the array? Then prepare the sequence of 0,1,0,1 ... based on the no. of ONEs using a simple for loop.
