Thursday, January 7, 2010

Array of 0 and 1, put 0's at even position and 1's at odd position

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 verse 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 }

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.
jigsaw Send private email
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.
jigsaw Send private email
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
Gene Wirchenko Send private email
Thursday, May 15, 2008


:) That's funny. BTW when he said extra memory, he meant variable amt of memory i guess.
jigsaw Send private email
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.
soup
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.
d
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
ved Send private email
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.
sagsriv Send private email
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
ray Send private email
Monday, July 07, 2008


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.

0 comments:

Post a Comment