Microsoft Interview Question:

write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array?

Submitted by: Administrator

Given the following prototype:
int compact(int * p, int size);

write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array. That is, if p points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 5 returned.


A single loop will accomplish this.

int compact(int * p, int size)
{
int current, insert = 1;
for (current=1; current < size; current++)
if (p[current] != p[insert-1])
{
p[insert] = p[current];
current++;
insert++;
} else
current++;
}
Submitted by: Administrator

int compact(int *array, int size)
{
int current, insert = 1;
for(current = 1; current < size; current++)
{
if(array[current] != array[insert - 1])
{
array[insert++] = array[current];
}
}
return insert;
}
Submitted by: Vjvalor