|
Given an array of balls, which can be one of two colors (RED or BLUE) .....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given an array of balls, which can be one of two colors (RED or BLUE) .....
Question:
Given an array of balls, which can be one of two colors (RED or BLUE), write a function that partitions the array in-place such that on exit from the function all the balls of the same color are contiguous. It does not matter whether the red or blue balls come first. The return value from the function is the index of the first ball of the second color. If there is only one color of balls in the array then the return value should be 0. It is not legal to change the color of a ball. They must be moved. Consider performance, memory utilization and code clarity and elegance of the solution when implementing the function.
C++ Prototype
class Ball
{
public:
enum BallColor { RED, BLUE };
BallColor Color() const { return _color; }
private:
BallColor _color;
// Other data in class (unrelated to assignment)
};
unsigned Partition( Ball aBalls[], unsigned cBalls )
{
//your code goes here
}
maybe an answer:
balls can be arranged in-place only by just swapping:
a[] -- array containing balls
n is the length of the array
0 -- blue color ball
1 -- red color ball
int partition(int *a,int n){
j=n-1
for(i=1;ilt;=j;i++){
if(a[i]!=a[i-1]){
while((a[j]==a[i])&&(j>i)){
j--;
}
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else{
break; //break the for loop, reached a point where balls are of same color on both the sides.
}
if(i==n-1)
return 0;
else return i;
Time complexity -- o(n) each ball is check for once only.
Spac complexity o(1) no extra memory is used.
(Continued on next question...)
Other Interview Questions
| 