03 May 2010

Compact a given array coding problem

This problem may look very simple and indeed it is because the solution can be arrived at very easily. But to arrive at a clean and an efficient may take sometime. This question is asked to test the cleanliness and simplicity in providing solutions. Enough hype, here is the question.

Given an array of random numbers and -1 placed in-between, compact that array ie., all the -1s are to be removed and the final output should be the last valid index with the fresh array. For example.





You should not swap the values just the last valid index along with the array is enough to decipher the not -1 values.

The solution to this problem is seemingly simple and the same has been implemented in Java below.


Cheers!
Bragaadeesh.

3 comments:

Mathur said...

Hi,
If more values at the starting are valid, copying the same value to the same location isn't worth.

for(int i=0;i<arr.length;i++){
if(arr[i]!=-1)
arr[k++] = arr[i];
}
This part can be improved by using

for(int i=0;i<arr.length;i++){
if(arr[i]!=-1) {
if ( i != k)
arr[k] = arr[i];
k++;
}
}

Regards,
Mathur

Yogesh said...

We may do following to recieve exact output as mentioned in examples above, where we must keep -1 in array if they are more in numers than non -1s. I chose to go this way:

int main()
{
int i=0;
int arr[6]= {-1,-1,-1,3,3,3};
printf("The array is as follows: \n");
for(i=0;i<6;i++)
printf("%d\n",arr[i]);
printf("\n\nTime to compact the array\n\n");
int k=0;
for(i=0,k=0;i<6,k<6;i++)
{
if(arr[i]==-1)
{
while(arr[k]==-1 && k<6){
k++;
};
arr[i]=arr[k++];
}
else
{
k++;
}
}
printf("\n\n The last valid index is :%d\n\n", i-1);
printf("The compacted array is as follows: \n");
for(i=0;i<6;i++)
printf("%d\n",arr[i]);
return 0;
}

Regards,
Yogesh

b said...

@Yogesh - Nice attempt !