Hi,

I would like to get variety of solutions for this problem:

Let us suppose there are several elements in the array consisting of 1 s and 0 s in any different order. The problem is to sort the 1s to one side and 0s to another side, without violating the precondition that one can traverse the array only once (Only Single pass allowed).


-- Karthikeyan
INDIA

I cannot help, because I do not fully understand how the program is supposed to work. Could you give more details about the 1's and 0's?

I just need the algorithm for this problem :

Let us presume there is an Integer array holding only 1s and 0s. Eg.

10001101000111001110101010001111

Now i need to sort this array as this :

11111111111111111000000000000000

or

00000000000000011111111111111111


But i need to perform this on a single pass. ie. I can traverse through the entire array of elements only once.

Hope the problem is clear now.

--- Karthikeyan

What's not clear is: is this a contest or a homework assignment?

Regards,

Dave

This was a typical Interview question asked by a top notch IT company.

Regards,
Karthikeyan

Then I have to ask a couple of questions:

1. By "traverse the array once" do you mean that a single counter is allowed to go from one end of the array to the other, so that each element is accessed only once? Or can we have two counters in a single loop, and one of the counters can be used read all of the elements and write some and the other can write some?

2. Is it required that the array be sorted "in place"? That is, are we required to have only the given array, which will hold the sorted values, or can we have another array to hold the sorted values, whereas the original array remains unchanged?

There are a couple of "easy" ways that I can think of if the answer to either is "no".

Regards,

Dave

Answers for your question:

1. By "traverse the array once" do you mean that a single counter is allowed to go from one end of the array to the other, so that each element is accessed only once? Or can we have two counters in a single loop, and one of the counters can be used read all of the elements and write some and the other can write some?

You may have any number of counters,but the case is, once if you have accessed that element,you may no more access the same.
A simple case is : If you try counting the total number of 1s or 0s in the array, you have not performed your operation in single pass.

2. Is it required that the array be sorted "in place"? That is, are we required to have only the given array, which will hold the sorted values, or can we have another array to hold the sorted values, whereas the original array remains unchanged?

You are supposed to sort only the given array.That means, you need to sort the original array.

Regards,
Karthikeyan

OK. I understand 2. Actually allowing two arrays leads to a very practical generalizationwhere we are leaving the original database intact, but creating a new database for some particular purpose. If it's not allowed, OK. They created the problem; they made the rules.


Then for 1, I think you are saying:

Each element can be read only once and written only once. And, given that is an array, the elements can be accessed only by using an array index or the equivalent pointer arithmetic. Is this correct?

I would like to see a solution that meets this requirement and also requirement number 2.

There are four reasons why I think questions like this are asked:

1. This is kind of a puzzle, with no known practical application, but tests the interviewee's ability to think under fire. Maybe there is some simple way that requires a certain kind of ingenuity on the part of the interviewee. Maybe there is some way that requires knowledge of some rather esoteric features of the programming language. Maybe there is some way that is commonly known among the denizens of "top notch IT" companies. Maybe there is a way, but it requires the interviewee to analyze and ask questions about terminology. (What does "traverse only once" mean.) Maybe the interviewer doesn't know a way to do it and wants to see if you can come up with a way, or to see how long it takes you to admit that you don't see how to do it. Maybe it's a test to see whether prospective interviewees have done web searches of "typical interview questions asked by top-notch IT companies".

2. This is an abstraction of something that is very practical and may or may not be difficult to apply. Knowledge of this requires either very creative thinking on your part, or, perhaps, direct experience, in depth, with the principles implied by the question. You have to know how to answer this question right now in order to be considered for employment. Or, if you don't know the answer, it's a point that will be brought up when you are negotiating your salary.

3. The interviewer has his/her own agenda and interviewing style which is forever unkown and unknowable.

4. If it's not one of the three previous reasons, it's probably something else.

Regards,

Dave

If this is the case, there must be a solution for this kind of question?
There are several questions of this kind asked in the interviews.So the logic is the most sort one and not syntax and formats.

I am also thinking on the logic and if i get to know i will let the forum know.

Regards,
Karthikeyan
INDIA

There are two principles that I always follow in my journey on Spaceship Earth:

1. I never tell everything that I know.


Regards,

Dave